The Complexity of Extended Formulations

Abstract

Combinatorial optimization plays a central role in complexity theory, operations research, and algorithms. Extended formulations give a powerful approach to solve combinatorial optimization problems: if one can find a concise geometric description of the possible solutions to a problem then one can use convex optimization to solve the problem quickly. Many combinatorial optimization problems have a natural symmetry. In this work we explore the role of symmetry in extended formulations for combinatorial optimization, focusing on two well-known and extensively studied problems: the matching problem and the traveling salesperson problem. In his groundbreaking work, Yannakakis [1991, 1988] showed that the matching problem does not have a small symmetric linear extended formulation. Rothvoß [2014] later showed that any linear extended formulation for matching, symmetric or not, must have exponential size. In light of this, we ask whether the matching problem has a small semidefinite extended formulation, since semidefinite programming generalizes linear programming. We show that the answer is no if the formulation is also required to be symmetric. Put simply, the matching problem does not have a small symmetric semidefinite extended formulation. We next consider optimization over the copositive cone and its dual, the completely positive cone. Optimization in this setting is NP-hard. We present a general framework for producing compact symmetric copositive formulations for a large class of problems. We show that, in contrast to the semidefinite case, both the matching and traveling salesperson problems have small copositive formulations even if we require symmetry.