An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
- Additional Document Info
- View All
© 2015 INFORMS. 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 d 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 4k1 d5D421 151 421 251 431 351 441 45 are provided as well.
author list (cited authors)
Buchanan, A., Sung, J. S., Butenko, S., & Pasiliao, E. L.