| Foundation-Penalty Cuts for Mixed-Integer Programs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract — We propose a new class of Foundation-Penalty (FP) cuts for GUBconstrained (and ordinary) mixed-integer programs, which are easy to generate by exploiting standard penalty calculations that are routinely employed in branch-andbound contexts. The FP cuts are derived with reference to a selected integer variable or GUB set, and a foundation function that is typically a reduced cost function corresponding to an optimal linear programming basis. The concept behind the generation of these cuts generalizes the lifting process, and as we demonstrate, bears relationships with other classical cuts such as disjunctive cuts, lift-and-project cuts, convexity cuts, Gomory cuts, and mixed-integer rounding cuts. For example, the easily derived but often useful cutting planes at the level of Gomory cuts and mixed integer rounding cuts are subsumed by related FP cuts that simply ‘plug in ’ penalty values from standard calculations (where the penalties are allowed to go beyond those from the first primitive mixed-integer programming codes). In general, the strength of these FP cuts can be varied according to the trade-offs between the strengths of alternative penalty calculations and the effort required to compute them, by virtue of the | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||