TY - JOUR
T1 - A note on critical-set and lifted surrogate inequalities for cardinality-constrained linear programs
AU - Kozyreff, E.
AU - De Farias, I. R.
N1 - Publisher Copyright:
© 2015, Elsevier Ltd. All rights reserved.
PY - 2015/4
Y1 - 2015/4
N2 - We study the polyhedral approach to the cardinality-constrained linear programming problem (CCLP). First, we generalize Bienstock's critical-set inequalities. We find necessary and sufficient conditions for the generalized inequalities to define facets of the convex hull of CCLP's feasible set. Then, we show how to derive lifted surrogate cutting planes on-the-fly. We test the use of both families of inequalities on branch-and-cut to solve difficult instances of CCLP to proven optimality. Our computational results indicate that the use of the inequalities can reduce the time required to solve CCLP by branch-and-cut considerably.
AB - We study the polyhedral approach to the cardinality-constrained linear programming problem (CCLP). First, we generalize Bienstock's critical-set inequalities. We find necessary and sufficient conditions for the generalized inequalities to define facets of the convex hull of CCLP's feasible set. Then, we show how to derive lifted surrogate cutting planes on-the-fly. We test the use of both families of inequalities on branch-and-cut to solve difficult instances of CCLP to proven optimality. Our computational results indicate that the use of the inequalities can reduce the time required to solve CCLP by branch-and-cut considerably.
KW - Branch-and-cut lifting
KW - Cardinality constraint
KW - Disjunctive programming
KW - Mixed-integer programming
KW - Polyhedral combinatorics
UR - http://www.scopus.com/inward/record.url?scp=84922023687&partnerID=8YFLogxK
U2 - 10.1016/j.cie.2014.08.014
DO - 10.1016/j.cie.2014.08.014
M3 - Article
AN - SCOPUS:84922023687
SN - 0360-8352
VL - 82
SP - 1
EP - 7
JO - Computers and Industrial Engineering
JF - Computers and Industrial Engineering
ER -