Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Juan Pablo Vielma ()
Additional contact information
Juan Pablo Vielma: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Management Science, 2018, vol. 64, issue 10, 4721-4734

Abstract: It is well known that selecting a good mixed-integer programming (MIP) formulation is crucial for effectively obtaining a solution with state-of-the art solvers. Although best practices and guidelines for constructing good formulations abound, there is rarely a single systematic construction approach that leads to the best possible formulation. Here, we introduce embedding formulations and complexity as a new MIP formulation paradigm for systematically constructing formulations for disjunctive constraints that are optimal with respect to size. More specifically, they yield the smallest possible ideal formulation (i.e., one whose LP relaxation has integral extreme points) among all formulations that only use 0-1 auxiliary variables. We use the paradigm to characterize optimal formulations for special ordered sets of type 2 and certain piecewise linear functions of two variables. We also show that the resultant formulations can provide a significant computational advantage over all known formulations for piecewise linear functions.

Keywords: integer programming; mixed-integer programming; mixed-integer modeling; strong formulation; piecewise linear (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.287/mnsc.2017.2856 (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:ormnsc:v:64:y:2018:i:10:p:4721-4734

Access Statistics for this article

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