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.

Compact formulations as a union of polyhedra

CONFORTI, MICHELANGELO;
2008

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/1772815
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 15
  • OpenAlex ND
social impact