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
##### Clone this wiki locally
You can’t perform that action at this time.