Skip to content

CglKnapsackCover

Stefan Vigerske edited this page Mar 9, 2019 · 3 revisions

Contributor and Maintainer: Robin Lougee-Heimer

CglKnapsackCover generates "knapsack cover cuts" . 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

    • This is an implementation of the method described in Gu, Nemhauser, and Savelsbergh (1995). There is a typo in the paper in the definition of the super additive lifting function g. In the 5th occurence of ρ, the subscript should be h+1 (not h). The function g is implemented as a "while" loop, dividing the domain of the lifting function into segments. For the example given in the reference, here are the segments used in the code:

      endpoint endpoint function value
      zero muMinusLamba[1] zero
      muMinusLamba[1] muMinusLamba[1] + rho[1]
      muMinusLamba[1] + rho[1] muMinusLamba[2] one
      muMinusLamba[2] muMinusLamba[2] + rho[2]
      muMinusLamba[2] + rho[2] muMinusLamba[3] two
      muMinusLamba[3] muMinusLamba[3] + rho[3]
      muMinusLamba[3] + rho[3] muMinusLamba[4] three (end of function domain)

Exact solvers for Knapsack Problems:

  • exactSolveKnapsack
    • A goto-less implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem, see Martello and Toth (1990)

References:

  • S. Martello, and P. Toth, Knapsack Problems, Wiley, 1990, p30.
  • Zong Gu, George Nemhauser, and Martin Savelsbergh, Sequence independent lifting of cover inequalities, Integer Programming and Combinatorial Optimization, 4th International IPOC Proceedings, Copenhagen, Denmark May 1995, pgs 452-416