Set Packing Relaxations of Some Integer Programs
Appeared in: Mathematical Programming, 88,425-450, 2000
| SC 97-30 | Ralf Borndörfer, Robert Weismantel
Set Packing Relaxations of Some Integer Programs Appeared in: Mathematical Programming, 88,425-450, 2000 | |
Abstract: This paper is about set packing relaxations of
combinatorial optimization problems associated with acyclic digraphs and linear
orderings, cuts and multicuts, and vertex packings themselves. Families of
inequalities that are valid for such a relaxation as well as the associated
separation routines carry over to the problems under investigation.