Knapsack cuts and explicit-constraint branching for solving integer programs
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1997
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 129
Subjects: OPTIMIZATION; INTEGER PROGRAMMING
Description: 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.
Notes: Dissertation supervisor, R. Kevin Wood.

AD-A331 891.

Dissertation (Ph.D. in Operations Research) Naval Postgraduate School, June 1997.

Includes bibliographical references (p. 115-120)

dk/dk cc:9116 11/12/97.