Finite disjunctive programming characterizations for general mixed-integer linear programs

Binyuan Chen*, Simge Kucukyavuz, Suvrajeet Sen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm that constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard notion of sequential cutting planes with ideas underlying the convex hull tree algorithm to help guide the choice of disjunctions to use within a cutting plane method. This algorithm, which we refer to as the cutting plane tree algorithm, is shown to converge to an integral optimal solution in finitely many iterations. Finally, we illustrate the proposed algorithm on three well-known examples in the literature that require an infinite number of elementary or split disjunctions in a rudimentary cutting plane algorithm.

Original languageEnglish (US)
Pages (from-to)202-210
Number of pages9
JournalOperations Research
Volume59
Issue number1
DOIs
StatePublished - Jan 2011

Keywords

  • Convex hull
  • Disjunctive programming
  • Finite convergence
  • Mixed-integer programming

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Finite disjunctive programming characterizations for general mixed-integer linear programs'. Together they form a unique fingerprint.

Cite this