Explicit-Constraint Branching for Solving Mixed-Integer Programs
Appleget, Jeffrey A.
Wood, R. Kevin
MetadataShow full item record
This paper develops a new generalized-branching technique called "explicit constraint branching" (ECB) to improve the performance of branch-and-bound algorithms for solving mixed-integer programs (MIPs). ECB adds structure to a MIP, in the frm of auxiliary constraints and auxiliary integer variables, to allow branching on groups of (original) integer variables that would not otherwise be possible. Computational tests on three sets of real-world MIPs demonstrate that ECB often improves solution times over standard branch and bound, sometimes dramatically.
Showing items related by title, author, creator and subject.
Appleget, Jeffrey A. (Monterey, California. Naval Postgraduate School, 1997-06);Enhanced solution techniques are developed for solving integer programs (IPs) and mixed-integer programs (MIPs). Previously unsolvable problems can be solved with these new techniques. We develop knapsack cut-finding ...
Riedel, Jeffery Scott (Monterey, California. Naval Postgraduate School, 1993-06);The ability of a submarine to maintain ordered depth, especially during periscope depth operations at low speeds, is vital for the vessel to perform its mission and avoid detection. Modern submarines exhibit an inherent ...
McMillian, Scott; Orin, David E.; McGhee, Robert B. (1996);This paper presents a computational framework for efficiently simulating the dynamics and hydrodynamics of Underwater Robotic Vehicle (URV) systems. Through the use of object-oriented mechanisms, a very general yet ...