Adaptive Branch and Bound for Efficient Solution of Mixed-Integer Programs Formulated with Big-M

Download
Author
Gan, Eng Kiat Russell
Date
2012-09Advisor
Wood, Kevin
Salmeron, Javier
Second Reader
Dimitrov, Nedialko
Metadata
Show full item recordAbstract
This 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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Star Tracker Attitude Estimation for an Indoor Ground-Based Spacecraft Simulator
Tappe, J.; Kim, J.J.; Jordan,A.; Agrawal, B.N. (2011);This paper presents a study of star tracker attitude estimation algorithms and implementation on an indoor ground-based Three Axis Spacecraft Simulator (TASS). Angle, Planar Triangle, and Spherical Triangle algorithms are ... -
Dynamic platform-independent meta-algorithms for graph-partitioning
Schwartz, Victor Scott (Monterey, California. Naval Postgraduate School, 1998-09-01);A dynamic platform-independent solver is developed for use with network and graph algorithms of operations research. This solver allows analysts to solve a large variety of problems without writing code. Algorithms from a ... -
Optimization models for placing nurse recruiters
Matuszewski, Douglas F. (Monterey, California. Naval Postgraduate School, 1994-09);This thesis addresses the problem of placing active duty nurse recruiters at recruiting stations for the United States Army Recruiting Command (USAREC). The problem can be formulated as an integer programming problem which ...