Publications Details

Compact vs. Exponential-Size LP Relaxations

Carr, Robert D.; Lancia, G.

In this paper we introduce by means of examples a new technique for formulating compact (i.e. polynomial-size) LP relaxations in place of exponential-size models requiring separation algorithms. In the same vein as a celebrated theorem by Groetschel, Lovasz and Schrijver, we state the equivalence of compact separation and compact optimization. Among the examples used to illustrate our technique, we introduce a new formulation for the Traveling Salesman Problem, whose relaxation we show equivalent to the subtour elimination relaxation.