Knapsack cuts and explicit-constraint branching for solving integer programs
Appleget, Jeffrey A.
Wood, R. Kevin
MetadataShow full item record
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 procedures for minimal cover cuts, and convert existing cut-strengthening theory into practical procedures that lift and tighten violated minimal cover valid inequalities to violated knapsack facets in polynomial time. We find a new class of knapsack cuts called 'non-minimal cover cuts' and a method of lifting them called 'deficit lifting.' Deficit lifting enables all of these cuts to be lifted and tightened to facets as well. Extensions of these techniques enable us to find cuts for elastic knapsack constraints and cuts for non-standard knapsack constraints. We also develop the new technique of 'explicit-constraint branching' (ECB). ECB enables the technique of constraint branching to be used on IPs and MIPs that do not have the structure required for known 'implicit constraint branching' techniques. When these techniques are applied to 84 randomly generated generalized assignment problems, the combination of knapsack cuts and explicit-constraint branching were able to solve 100% of the problems in under 1000 CPU seconds. Explicit constraint branching alone solved 94%, and knapsack cuts solved 93%. Standard branch and bound alone solved only 38%. The benefits of these techniques are also demonstrated on some real-world generalized assignment and set-partitioning problems
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Appleget, Jeffrey A.; Wood, R. Kevin (2000);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 ...
Acceleration of the implicit-explicit non-hydrostatic unified model of the atmosphere (NUMA) on Manycore processors Abdi, Daniel S.; Giraldo, Francis X.; Constantinescu, Emil M.; Carr, Lester E., III; Wilcox, Lucas C.; Warburton, Timothy C. (Sage, 2017);We present the acceleration of an IMplicit-EXplicit (IMEX) non-hydrostatic atmospheric model on manycore processors such as GPUs and Intel’s MIC architecture. IMEX time integration methods sidestep the constraint imposed ...
Ryoo, Moo Bong (Monterey, California: Naval Postgraduate School, 1990-03);This thesis compares the efficiency of a constraint branch-and-bound method against the conventional variable branch-and-bound method in solving set partitioning problems. Because of the difficulties encountered in writing ...