Treffer: On cycles and the stable multi-set polytope

Abstract: Stable multi-sets are an integer extension of stable sets in graphs. In this paper, we continue our investigations started by Koster and Zymolka [Stable multi-sets, Math. Methods Oper. Res. 56(1) (2002) 45–65]. We present further results on the stable multi-set polytope and discuss their computational impact. The polyhedral investigations focus on the cycle inequalities. We strengthen their facet characterization and show that chords need not weaken the cycle inequality strength in the multi-set case. This also helps to derive a valid right hand side for clique inequalities. The practical importance of the cycle inequalities is evaluated in a computational study. For this, we revisit existing polynomial time separation algorithms. The results show that the performance of state-of-the-art integer programming solvers can be improved by exploiting this general structure. [Copyright &y& Elsevier]