Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs

Binyuan Chen (), Simge Küçükyavuz () and Suvrajeet Sen ()
Additional contact information
Binyuan Chen: Department of Systems and Industrial Engineering, University of Arizona, Tucson, Arizona 85721
Simge Küçükyavuz: Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210
Suvrajeet Sen: Department of Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210

Operations Research, 2011, vol. 59, issue 1, 202-210

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.

Keywords: mixed-integer programming; disjunctive programming; convex hull; finite convergence (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0882 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:1:p:202-210

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().