Expressing combinatorial optimization problems by Linear Programs

AbstractMany combinatorial optimization problems call for the optimization of a linear function over a certain polytope. Typically, these polytopes have an exponential number of facets. We explore the problem of finding small linear programming formulations when one may use any new variables and constraints. We show that expressing the matching and the Traveling Salesman Problem by a symmetric linear program requires exponential size. We relate the minimum size needed by a LP to express a polytope to a combinatorial parameter, point out some connections with communication complexity theory, and examine the vertex packing polytope for some classes of graphs