An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets

作者：Buchanan Austin^*; Sung Je Sang; Butenko Sergiy

来源：INFORMS Journal on Computing, 2015, 27(1): 178-188.

DOI：10.1287/ijoc.2014.0619

• connected dominating set
• k-connected m-dominating set
• integer programming
• fault-tolerant

This paper considers the minimum k -connected d -dominating set problem, which is a fault-tolerant generalization of the minimum connected dominating set ( MCDS) problem. Three integer programming formulations based on vertex cuts are proposed ( depending on whether d < k, d D k, or d > k) and their integer hulls are studied. The separation problem for the vertex-cut inequalities is a weighted vertex-connectivity problem and is polytime solvable, meaning that the LP relaxation can be solved in polytime despite having exponentially many constraints. A new class of valid inequalities-r-robust vertex-cut inequalities-is introduced and is shown to induce exponentially many facets. Finally, a lazy-constraint approach is shown to compare favorably with existing approaches for the MCDS problem ( the case k = d = 1), and is in fact the fastest in literature for standard test instances. A key subroutine is an algorithm for finding an inclusion-wise minimal vertex cut in linear time. Computational results for (k, d) =(2, 1), (2, 2), (3, 3), (4, 4) are provided as well.

• 出版日期2015