Higher-order cover cuts from zero–one knapsack constraints augmented by two-sided bounding inequalities

Higher-order cover cuts from zero–one knapsack constraints augmented by two-sided bounding inequalities

0.00 Avg rating0 Votes
Article ID: iaor20091387
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 270
End Page Number: 289
Publication Date: May 2008
Journal: Discrete Optimization
Authors: ,
Keywords: knapsack problem
Abstract:

Extending our work on second-order cover cuts, we introduce a new class of higher-order cover cuts that are derived from the implications of a knapsack constraint in concert with supplementary two-sided inequalities that bound the sums of sets of variables. The new cuts can be appreciably stronger than the second-order cuts, which in turn dominate the classical knapsack cover inequalities. The process of generating these cuts makes it possible to sequentially utilize the second-order cuts by embedding them in systems that define the inequalities from which the higher-order cover cuts are derived. We characterize properties of these cuts, design specialized procedures to generate them, and establish associated dominance relationships. These results are used to devise an algorithm that generates all non-dominated higher-order cover cuts, and, in particular, to formulate and solve suitable separation problems for deriving a higher-order cut that deletes a given fractional solution to an underlying continuous relaxation.

Reviews

Required fields are marked *. Your email address will not be published.