A Generalization of Odd Set Inequalities for the Set Packing Problem
Please always quote using this URN: urn:nbn:de:0297-zib-51010
- The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
Download full text files
Additional Services
| Author: | Olga Heismann, Ralf BorndörferORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | facet; hypergraph; inequality; matching; set packing |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
| Date of first Publication: | 2014/07/16 |
| Series (Serial Number): | ZIB-Report (14-28) |
| ISSN: | 1438-0064 |
| Published in: | Appeared in: Operations Research Proceedings 2013 pp 193-199 |
| DOI: | https://doi.org/10.1007/978-3-319-07001-8_26 |
