The projected faces property and polyhedral relations

DOI10.1007/S10107-015-0882-5MaRDI QIDQ263204zbMATH OpenOpenAlexFDO

Authors Michele Conforti, Kanstantsin Pashkovich

Publication date 4 April 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.3782

zbMATH Keywords

projectionspolyhedral combinatoricsextended formulationsextensionspolyhedral relationprojected faces property

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) (n)-dimensional polytopes (52B11)

Abstract: 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 studied in this paper 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 (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.

Recommendations

• Constructing extended formulations from reflection relations
• Constructing extended formulations from reflection relations
• An algebraic approach to symmetric extended formulations
• On the dimension of projected polyhedra
• scientific article; zbMATH DE number 764212

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 764212 (Why is no real title available?)
• Constructing extended formulations from reflection relations
• Extended formulations in combinatorial optimization
• On certain polytopes associated with graphs
• On defining sets of vertices of the hypercube by linear inequalities
• The traveling salesman problem in graphs with 3-edge cutsets

Cited in

(11)

• Recognizing Cartesian products of matrices and polytopes
• On decomposability of multilinear sets
• Projective splitting of quadric faces
• A strong formulation for the graph partition problem
• Constructing extended formulations from reflection relations
• Extension complexity of formal languages
• On the central projections of the faces of a simplex with centres of projection at its vertices
• Extension complexity, MSO logic, and treewidth
• On the dimension of projected polyhedra
• On permuting some coordinates of polytopes
• Constructing extended formulations from reflection relations

This page was built for publication: The projected faces property and polyhedral relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263204)