Compact formulations as a union of polyhedra

Michele Conforti and Laurence A. Wolsey

No 2005062, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We explore one method for finding the convex hull of certain mixed integer sets. The approach is to break up the original set into a small number of subsets, find a compact polyhedral description of the convex hull of each subset, and then take the convex hull of the union of these polyhedra. The resulting extended formulation is then compact, its projection is the convex hull of the original set, and optimization over the mixed integer set is reduced to solving a linear program over the extended formulation. The approach is demonstrated on three different sets: a continuous mixing set with an upper bound and a mixing set with two divisible capacities both arising in lot-sizing, and a single node flow model with divisible capacities that arises as a subproblem in network design.

Keywords: mixed integer sets; convex hull; unions of polyhedra; lot-sizing (search for similar items in EconPapers)
Date: 2005-09
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2005.html (text/html)

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:cor:louvco:2005062

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS (alain.gillis@uclouvain.be).