Adaptive Branch and Bound for Efficient Solution of Mixed-Integer Programs Formulated with Big-M
Abstract
This thesis describes three specialized branch-and-bound (B&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&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 M's. 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% for the uncapacitated k-median problem and 99% 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2012
- Accession Number
- ADA570830
Entities
People
- Eng K. Gan
Organizations
- Naval Postgraduate School