wiki:CglKnapsackCover

CglKnapsackCover

Contributor: Robin Lougee-Heimer
Maintainer: Robin Lougee-Heimer, robinlh@…

Introduction

CglKnapsackCover generates "knapsack cover cuts" <reference needed here>. It looks for a series of different types of minimal covers. If a minimal cover is found, it lifts the associated minimal cover inequality and adds the lifted cut to the cut set.

CglKnapsackCover has a variety of methods for finding and lifting covers. You can re-use the various cover-finding methods and cover-lifting methods to build your own variations of this classic cut.

Cover-finding methods:

  • findGreedyCover
    • Try to generate a violated minimal cover greedily from fractional vars.
  • findJohnAndEllisCover
    • Try to generated a violated minimal cover using "John and Ellis" logic (i.e., my understanding of some of what John Forrest and Ellis Johnson used in OSL).
  • findPseudoJohnAndEllisCover
    • A variation on findJohnAndEllisCover.
  • findExactMostViolatedMinCover
    • Use an exact algorithm to find the most violated (minimal) cover.
  • findLPMostViolatedMinCover
    • Use an lp-relaxation to find the approximately most violated (minimal) cover.

Cover-lifting methods:

  • liftUpDownAndUncomplementAndAdd
  • seqLiftAndUncomplementAndAdd
    • Sequence-dependent lifting
  • liftCoverCut
    • Sequence-independent lifting

Exact solvers for Knapsack Problems:

  • exactSolveKnapsack
    • A goto-less implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem. Reference: Martello and Toth, Knapsack Problems, Wiley, 1990, p30-31.

Papers, Presentations, and References

  • S. Martello, and P. Toth, Knapsack Problems, Wiley, 1990, p30.

Documentation and Bug Reports

See the section "Project Links" on the Cgl main Trac page.

Last modified 11 years ago Last modified on Dec 10, 2007 1:14:32 PM