The projected faces property and polyhedral relations

Margot ( 1994 ) in his doctoral dissertation studied extended formulations of combinatorial polytopes that arise from “smaller” polytopes via some composition rule. He introduced the “projected faces property” of a polytope and showed that this property suffices to iteratively build extended formula...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2016-03, Vol.156 (1-2), p.331-342
Main Authors: Conforti, Michele, Pashkovich, Kanstantsin
Format: Article
Language:English
Subjects:
Calculus of Variations and Optimal Control
Optimization
Combinatorial analysis
Combinatorics
Computer programming
Construction
Equivalence
Full Length Paper
Hulls (structures)
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Parity
Polytopes
Reflection
Studies
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Margot ( 1994 ) in his doctoral dissertation studied extended formulations of combinatorial polytopes that arise from “smaller” polytopes via some composition rule. He introduced the “projected faces property” of a polytope and showed that this property suffices to iteratively build extended formulations of composed polytopes. For the composed polytopes, we show that an extended formulation of the type defined by Margot is always possible only if the smaller polytopes have the projected faces property. Therefore, this produces a characterization of the projected faces property. Affinely generated polyhedral relations were introduced by Kaibel and Pashkovich (Optima 85:2–7, 2011 ) to construct extended formulations for the convex hull of the images of a point under the action of some finite group of reflections. In this paper we prove that the projected faces property and affinely generated polyhedral relation are equivalent conditions.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-015-0882-5