Circuits play a fundamental role in the theory of linear programming. They are the directions that the Simplex method and other circuit augmentation schemes for linear programming follow in each iteration. The performance of these methods depends on the size of the linear program. However, for many problems in combinatorial optimization, compact formulations only exist when we are allowed to introduce additional variables, which can be projected out to obtain the original polyhedron. Such a formulation in higher-dimensional space, which linearly projects to the original one, is a so-called extended formulation. Suppose that we observe the behavior of a circuit augmentation algorithm on such an extended formulation. Is there anything that our observations tell us for the behavior of the algorithm when the original formulation is the input?

In this talk, I will focus on one of the most fundamental questions in this context: Is every circuit of the original polyhedron the projection of a circuit of the lifted polyhedron (the one that is described by the extended formulation)? While this is known to be true for all edge directions, I will show that the set of circuits does not have this property in general. I will further characterize those polyhedra for which we obtain a positive answer no matter which extended formulation we consider.

This is joint work with Steffen Borgwardt.