Succinct Relaxations for Some Discrete Problems.pdf.pdf' (156.55 kB)
Download fileSuccinct Relaxations for Some Discrete Problems
journal contribution
posted on 1992-04-01, 00:00 authored by John N. Hooker, Hak-Jin KimA 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.