Sequence independent lifting for mixed integer programs with variable upper bounds

S. Shebalov*, D. Klabjan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We investigate the convex hull of the set defined by a single inequality with continuous and binary variables with variable upper bound constraints. We extend the traditional flow cover inequality, and show that it is valid for a restriction of the set in which some variables are fixed. We also give conditions under which this inequality is facet-defining and, when it is not, we show how it can be lifted to obtain valid inequalities for the entire set using sequence independent lifting. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. Finally, we show how these results imply and extend known results about the single node fixed charge flow polyhedron.

Original languageEnglish (US)
Pages (from-to)523-561
Number of pages39
JournalMathematical Programming
Volume105
Issue number2-3
DOIs
StatePublished - Feb 1 2006

Keywords

  • Mixed integer programming
  • Polyhedral theory

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Sequence independent lifting for mixed integer programs with variable upper bounds'. Together they form a unique fingerprint.

Cite this