Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka (2002) and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results.
First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords.
The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.
Citation
ZIB-Report 03-10, Konrad-Zuse-Zentrum für Informationstechnik Berlin