zbMATH — the first resource for mathematics

Combinatorial bounds on nonnegative rank and extended formulations. (English) Zbl 1259.90111
Summary: An extended formulation of a polytope \(P\) is a system of linear inequalities and equations that describe some polyhedron which can be projected onto \(P\). Extended formulations of small size (i.e. number of inequalities) are of interest, as they allow to model corresponding optimization problems as linear programs of small sizes. In this paper, we describe several aspects and new results on the main known approach to establish lower bounds on the sizes of extended formulations, which is to bound from below the number of rectangles needed to cover the support of a slack matrix of the polytope. Our main goals are to shed some light on the question how this combinatorial rectangle covering bound compares to other bounds known from the literature, and to obtain a better idea of the power as well as of the limitations of this bound. In particular, we provide geometric interpretations (and a slight sharpening) of M. Yannakakis’ [J. Comput. Syst. Sci. 43, No. 3, 441–466 (1991; Zbl 0748.90074)] result on the relation between minimal sizes of extended formulations and the nonnegative rank of slack matrices, and we describe the fooling set bound on the nonnegative rank (due to M. Dietzfelbinger, J. Hromkovič and G. Schnitger [Theor. Comput. Sci. 168, No. 1, 39–51 (1996; Zbl 0874.68150)]) as the clique number of a certain graph. Among other results, we prove that both the cube as well as the Birkhoff polytope do not admit extended formulations with fewer inequalities than these polytopes have facets, and we show that every extended formulation of a \(d\)-dimensional neighborly polytope with \(\Omega (d^{2})\) vertices has size \(\Omega (d^{2})\).

90C27 Combinatorial optimization
Full Text: DOI arXiv