Show simple item record

dc.contributor.advisorWood, Kevin
dc.contributor.advisorSalmeron, Javier
dc.contributor.authorGan, Eng Kiat Russell
dc.dateSep-12
dc.date.accessioned2012-11-14T00:02:32Z
dc.date.available2012-11-14T00:02:32Z
dc.date.issued2012-09
dc.identifier.urihttp://hdl.handle.net/10945/17370
dc.description.abstractThis thesis describes three specialized branch-and-bound (B and B) algorithms for solving a mixed-integer program (MIP) that incorporates standard big-M constructs. The goal is to identify valid values for M that also lead to short solution times. One algorithm initializes large instances of M (giving a weak relaxation of the MIP), and decreases these as required to increase efficiency of the standard B and B. Two algorithms initialize small and possibly invalid instances of M, and subsequently increase those values in an attempt to ensure solution validity. Each algorithm requires a model-specific test condition to detect weak or invalid Ms. We test all algorithms on an uncapacitated k-median problem (a variant of the uncapacitated facility location problem), and one algorithm on a shortest-path interdiction problem (SPIP). We observe substantial reduction in run times in almost all cases tested. When solving for exact solutions, computational results show that the proposed algorithms may reduce solution times by up to 75 per cent for the uncapacitated k-median problem and 99 per cent for the SPIP. When the algorithms yield marginally suboptimal solutions, substantial solution-time improvements are also recorded. While testing is limited, this thesis serves as a proof-of-concept that the proposed adaptive algorithms can be effective in reducing solution times and producing optimal or nearly optimal solutions.en_US
dc.description.urihttp://archive.org/details/adaptivebranchnd1094517370
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.titleAdaptive Branch and Bound for Efficient Solution of Mixed-Integer Programs Formulated with Big-Men_US
dc.typeThesisen_US
dc.contributor.secondreaderDimitrov, Nedialko
dc.contributor.departmentOperations Research (OR)
dc.subject.authorBig-Men_US
dc.subject.authorbound coefficientsen_US
dc.subject.authoruncapacitated facility location problemen_US
dc.subject.authorshortest-path interdiction problemen_US
dc.subject.authorbranch-and-bounden_US
dc.subject.authoruncapacitated k-median problem.en_US
dc.description.serviceMajor, Singapore Armyen_US
etd.thesisdegree.nameMaster of Science In Operations Researchen_US
etd.thesisdegree.levelMastersen_US
etd.thesisdegree.disciplineOperations Researchen_US
dc.description.distributionstatementApproved for public release; distribution is unlimited.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record