On cutting planes for cardinality-constrained linear programs

Jinhak Kim, Mohit Tawarmalani, Jean Philippe P. Richard

Research output: Contribution to journalArticle

Abstract

We derive cutting planes for cardinality-constrained linear programs. These inequalities can be used to separate any basic feasible solution of an LP relaxation of the problem, assuming that this solution violates the cardinality requirement. To derive them, we first relax the given simplex tableau into a disjunctive set, expressed in the space of nonbasic variables. We establish that coefficients of valid inequalities for the closed convex hull of this set obey ratios that can be computed directly from the simplex tableau. We show that a transportation problem can be used to separate these inequalities. We then give a constructive procedure to generate violated facet-defining inequalities for the closed convex hull of the disjunctive set using a variant of Prim’s algorithm.

Original languageEnglish (US)
Pages (from-to)417-448
Number of pages32
JournalMathematical Programming
Volume178
Issue number1-2
DOIs
StatePublished - Nov 1 2019
Externally publishedYes

Keywords

  • Complementarity/cardinality constraints
  • Concavity cuts
  • Disjunctive sets
  • Equate-and-relax procedure
  • Prim’s algorithm
  • Tableau cuts

Fingerprint Dive into the research topics of 'On cutting planes for cardinality-constrained linear programs'. Together they form a unique fingerprint.

  • Cite this