A note on critical-set and lifted surrogate inequalities for cardinality-constrained linear programs

E. Kozyreff, I. R. De Farias

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1-7
Number of pages7
JournalComputers and Industrial Engineering
Volume82
DOIs
StatePublished - Apr 2015

Keywords

  • Branch-and-cut lifting
  • Cardinality constraint
  • Disjunctive programming
  • Mixed-integer programming
  • Polyhedral combinatorics

Fingerprint Dive into the research topics of 'A note on critical-set and lifted surrogate inequalities for cardinality-constrained linear programs'. Together they form a unique fingerprint.

  • Cite this