Running summarizing tools on a new article

Check the paper below, then start its synthesis.


Circuits in Extended Formulations

Steffen Borgwardt, Matthias Brugger

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 $π$, this is not a property of any single one of $P$, $Q$, or $π$ - 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 $π$ 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.

Submitted to arXiv on 10 Aug. 2022