Discrete Relaxations of Combinatorial Programs. (rev.Vers.JUN00)
Rev. vers. appeared in: Discrete Appl. Math. 112 (2001) 11-26
| SC 97-54 | Ralf Borndörfer, Robert Weismantel
Discrete Relaxations of Combinatorial Programs. (rev.Vers.JUN00) Rev. vers. appeared in: Discrete Appl. Math. 112 (2001) 11-26 | |
Original Version: Relations Among Some Combinatorial Programs
Abstract: This paper investigates relations among
combinatorial optimization problems. To establish such relations we introduce a
transformation technique --aggregation-- that allows to relax an
integer program by means of another integer program.
We prove that various families of prominent inequalities for the acyclic
subdigraph problem, the multiple knapsack problem, the max cut, graph, and the
clique partitioning problem, the set covering problem, and the set packing
problem can be derived and separated in polynomial time in this way. Our
technique is algorithmic. It has been implemented and used in a set partitioning
code.