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.
Rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
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 ...
George, Robert Tyler (Monterey, California. Naval Postgraduate School, 1996-12);The problem of scheduling parallel program tasks on multiprocessor systems is known to be NP-complete in its general form. When non-determinism is added to the scheduling problem through loops and conditional branching, ...