Knapsack cuts and explicit-constraint branching for solving integer programs
Loading...
Authors
Appleget, Jeffrey A.
Subjects
Optimization
Integer Programming
Knapsack facets
Constraint branching
Generalized Assignment Problem
Integer Programming
Knapsack facets
Constraint branching
Generalized Assignment Problem
Advisors
Wood, R. Kevin
Date of Issue
1997-06
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 129 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.