Contributor: Robin Lougee-Heimer
Maintainer: Robin Lougee-Heimer, robinlh@…
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.
- Try to generate a violated minimal cover greedily from fractional vars.
- 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).
- A variation on findJohnAndEllisCover.
- Use an exact algorithm to find the most violated (minimal) cover.
- Use an lp-relaxation to find the approximately most violated (minimal) cover.
- Sequence-dependent lifting
- Sequence-independent lifting
Exact solvers for Knapsack Problems:
- 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.