Explicit-Constraint Branching for Solving Mixed-Integer Programs
Abstract
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.
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Knapsack cuts and explicit-constraint branching for solving integer programs
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 ... -
Pitchfork bifurcations and dive plane reversal of submarines at low speeds
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 ... -
Static scheduling of conditional branches in parallel programs
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, ...