90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Refine
Year of publication
- 2014 (2) (remove)
Document Type
- ZIB-Report (2)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Branch-and-Cut (1)
- DIMACS Challenge (1)
- Mixed-Integer Programming (1)
- Steiner Tree Problem (1)
- facet (1)
- hypergraph (1)
- inequality (1)
- matching (1)
- set packing (1)
In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.
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.