We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on @math vertices, with a polynomial number of constraints, requires @math many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first non-trivial lower bound on the number of integer variables needed in such settings.
Let @math X be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is @math X. This quantity, which we call the relaxation complexity of @math X, corresponds to the smallest number of linear inequalities of any integer program having @math X as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in many relevant cases. In particular, we provide asymptotically tight exponential lower bounds on the relaxation complexity of the integer points of several well-known combinatorial polytopes, including the traveling salesman polytope and the spanning tree polytope. In addition to the material in the extended abstract Kaibel and Weltge (2014) we include omitted proofs, supporting figures, discussions about properties of coefficients in such formulations, and facts about the complexity of formulations in more general settings.