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 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.
Similar content being viewed by others
References
Margot, F.: Composition de polytopes combinatoires: une approche par projection. Thesis École polytechnique fédérale de Lausanne (1994)
Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR, 8(1), 1–48 (2010)
Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2–7 (2011)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)
Kaibel, V., Pashkovich, K.: Constructing extended formulations from reflection relations. In: Proceedings of the 15th international conference on Integer programming and combinatoral optimization, pp. 287–300. New York (2011)
Jeroslow, R.: On defining sets of vertices of the hypercube by linear inequalities. Discrete Math. 119–124 (1975)
Carr, R.D., Konjevod, G.: Polyhedral combinatorics. In: Greenberg, H.J. (ed) Tutorials on emerging methodologies and applications in operations research. International Series in Operations Research & Management Science, vol. 76, pp. 2–1–2–46. Springer, New York (2005)
Chvátal, V.: On certain polytopes associated with graphs. J. Comb Theor B 18, 138–154 (1975)
Cornuéjols, G., Naddef, D., Pulleyblank, W.: The traveling salesman problem in graphs with 3-edge cutsets. J. ACM. 32(2), 383–410 (1985)
Radon, J.: Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen 83(1–2), 113–115 (1921)
Acknowledgments
We thank the referees for their comments and suggestions, which increased the readability of the present paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by “Progetto di Eccellenza 2008–2009” of “Fondazione Cassa di Risparmio di Padova e Rovigo” and Fonds de la Recherche Scientifique de Belgique (FRS-FNRS).
Rights and permissions
About this article
Cite this article
Conforti, M., Pashkovich, K. The projected faces property and polyhedral relations. Math. Program. 156, 331–342 (2016). https://doi.org/10.1007/s10107-015-0882-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-015-0882-5
Keywords
- Polyhedral combinatorics
- Extended formulations
- Extensions
- Projections
- Polyhedral relation
- Projected faces property