Second-order cover inequalities
成果类型：
Article
署名作者：
Glover, Fred; Sherali, Hanif D.
署名单位：
University of Colorado System; University of Colorado Boulder; Virginia Polytechnic Institute & State University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-007-0098-4
发表日期：
2008
页码：
207-234
关键词：
摘要：
We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0-1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and -1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one.