Succinct Relaxations for Some Discrete Problems

A discrete problem can be relaxed by taking the continuous relaxation of an integer programming formulation. An equivalent relaxation is obtained by projecting this relaxation onto the original continuous variables. The projection is simple for piecewise linear functions, fixed charge problems and some disjunctive constraints. This allows one to solve much smaller relaxations without sacrificing the quality of bounds. In particular the projected relaxations for some classical network design and warehouse location problems are minimum cost network ow problems, a fact that can dramatically accelerate their solution.