wiki:liftCoverCut

Lift Cover Cut

This is an implementation of the method described in "Sequence independent lifting of cover inequalities" by Zong Gu, George Nemhauser, and Martin Savelsbergh, Integer Programming and Combinatorial Optimization, 4th International IPOC Proceedings, Copenhagen, Denmark May 1995, pgs 452-416.

There is a typo in the paper in the definition of the super additive lifting function "g." In the 5th occurence of rho, 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] <something fancy>
muMinusLamba[1] + rho[1]muMinusLamba[2] one
muMinusLamba[2]muMinusLamba[2] + rho[2] <something fancy>
muMinusLamba[2] + rho[2]muMinusLamba[3] two
muMinusLamba[3]muMinusLamba[3] + rho[3] <something fancy>
muMinusLamba[3] + rho[3]muMinusLamba[4] three (end of function domain)
Last modified 14 years ago Last modified on Dec 10, 2007 1:31:32 PM