Two-connected networks with rings of bounded cardinality
(2004) Computational Optimization and Applications : an international journal — Vol. 27, p. 123-148 (2004)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877, 2000). In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem is strongly NP-complete for any fixed K, and we derive a new class of facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem.
- Affiliations
Louvain School of Management Operations and Information
Citations
Fortz, B., & Labbé, M. (2004). Two-connected networks with rings of bounded cardinality. Computational Optimization and Applications : an international journal, 27, 123-148. https://doi.org/10.1023/B:COAP.0000008649.61438.6b (Original work published 2004)