The projected faces property and polyhedral relations

DOI10.1007/S10107-015-0882-5zbMATH Open1335.90115arXiv1305.3782OpenAlexW2115563735MaRDI QIDQ263204FDOQ263204

Authors: Michele Conforti, Kanstantsin Pashkovich 

Publication date: 4 April 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On defining sets of vertices of the hypercube by linear inequalities
• On certain polytopes associated with graphs
• Constructing extended formulations from reflection relations
• The traveling salesman problem in graphs with 3-edge cutsets
• Title not available (Why is that?)
• Extended formulations in combinatorial optimization

Cited In (10)

• Recognizing Cartesian products of matrices and polytopes
• On permuting some coordinates of polytopes
• Constructing extended formulations from reflection relations
• Title not available (Why is that?)
• On the dimension of projected polyhedra
• On decomposability of multilinear sets
• On the central projections of the faces of a simplex with centres of projection at its vertices
• Extension complexity of formal languages
• A strong formulation for the graph partition problem
• Projective splitting of quadric faces

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)