Compact vs. exponential-size LP relaxations (Q1612003)

The authors illustrate by means of examples a technique for formulating compact (polynomial-size) linear programming relaxations in place of exponential-size models requiring separation algorithms. They state the equivalence of compact separation and compact optimization. They also introduce a new formulation for the traveling salesman problem whose relaxation is equivalent to subtour elimination relaxation.