Circuits in Extended Formulations

MaRDI QIDQ6407538zbMATH OpenFDO

Authors Steffen Borgwardt, Matthias Brugger

Publication date 10 August 2022

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: We study the connection between the circuits of a polyhedron $P$ and those of an extended formulation of $P$, i.e., a description of a polyhedron $Q$ that linearly projects onto $P$. Circuits and extended formulations are classical concepts in linear programming. The circuits of a polyhedron are the elementary difference vectors between feasible points, and form the directions in circuit- and edge-augmentation schemes such as the Simplex method. Extended formulations are a powerful tool to obtain compact linear programs for problems in combinatorial optimization. It is known that the edge directions of any linear projection $P$ of a polyhedron $Q$ are images of edge directions of $Q$. We are interested in when this `inheritance' under projections extends to the more general set of circuits. We provide counterexamples, both bounded and unbounded, with a provably minimal number of facets, vertices, and extreme rays. We further show that, whenever every circuit of $P$ has a circuit of $Q$ sent to it under some projection $pi$, this is not a property of any single one of $P$, $Q$, or $pi$ - unless $P$ and $Q$ are linearly isomorphic or unless all circuits of $P$ are actual edge directions. Our characterizations are best possible in the sense that there are combinations of $P$, $Q$ and $pi$ that do not fall into these categories, but do guarantee inheritance of all circuits. Our proofs are constructive and build on a range of simple classes of polyhedra, including simplices and zonotopes, and standard constructions such as homogenization, disjunctive programming, and Cartesian products. We add a discussion of the class of fixed-shape partition polytopes, projections of transportation polytopes under a geometric embedding of a data set. Despite the many promising properties of this example, the set of circuits is not inherited.

This page was built for publication: Circuits in Extended Formulations

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