Constructing Extended Formulations from Reflection Relations

Volker Kaibel () and Kanstantsin Pashkovich ()
Additional contact information
Volker Kaibel: Otto-von-Guericke Universität Magdeburg, Fakultät für Mathematik
Kanstantsin Pashkovich: Universitá del Padova, Dipartimento di Matematica

A chapter in Facets of Combinatorial Optimization, 2013, pp 77-100 from Springer

Abstract: Abstract There are many examples of optimization problems whose associated polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhedra than this would be possible in the original space. However, currently not many general tools to construct such extended formulations are available. In this paper, we develop the framework of polyhedral relations that generalizes inductive constructions of extended formulations via projections, and we particularly elaborate on the special case of reflection relations. The latter ones provide polynomial size extended formulations for several polytopes that can be constructed by iteratedly forming convex hulls of polytopes and (slightly modified) reflections of them at hyperplanes. We demonstrate the use of the framework by deriving small extended formulations for the G-permutahedra of all finite reflection groups G (generalizing both Goemans’ extended formulation of the permutahedron of size O(nlogn) and Ben-Tal and Nemirovski’s extended formulation with O(k) inequalities for the regular 2 k -gon) and for Huffman-polytopes (the convex hulls of the weight-vectors of Huffman codes). This work is an extension of an extended abstract presented at IPCO XV (2011).

Keywords: Convex Hull; Extended Formulation; Fundamental Domain; Affine Generator; Reflection Group (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-3-642-38189-8_4

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().