A Generalization of Odd Set Inequalities for the Set Packing Problem

Olga Heismann () and Ralf Borndörfer ()
Additional contact information
Olga Heismann: Zuse Institute Berlin
Ralf Borndörfer: Zuse Institute Berlin

A chapter in Operations Research Proceedings 2013, 2014, pp 193-199 from Springer

Abstract: Abstract 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.

Keywords: Valid Inequalities; Polytope; Bipartite Hypergraphs; Edge Clique; Arbitrary Hypergraph (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-07001-8_26

Ordering information: This item can be ordered from
http://www.springer.com/9783319070018

DOI: 10.1007/978-3-319-07001-8_26

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().