@inproceedings{bdd3a7e5842b4660aad6c45cb9b2e9e9,
title = "Lower bounds on the sizes of integer programs without additional variables",
abstract = "For a given set X ⊆ Z d of integer points, we investigate the smallest number of facets of any polyhedron whose set of integer points is conv(X) ∩ Z d . This quantity, which we call the relaxation complexity of X, corresponds to the smallest number of linear inequalities of any integer program having 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.",
keywords = "auxiliary variables, integer programming, relaxations, tsp",
author = "Volker Kaibel and Stefan Weltge",
year = "2014",
doi = "10.1007/978-3-319-07557-0_27",
language = "English",
isbn = "9783319075563",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "321--332",
booktitle = "Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings",
note = "17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 ; Conference date: 23-06-2014 Through 25-06-2014",
}