Two-Connected Networks with Rings of Bounded Cardinality |
| |
Authors: | B. Fortz M. Labbé |
| |
Affiliation: | (1) Institut d'Administration et de Gestion, Université Catholique de Louvain, Place des Doyens 1, B-1348 Louvain-la-Neuve, Belgium;(2) Institut de Statistique et de Recherche Opérationnelle, SMG, CP 210/01, Univ. Libre de Bruxelles, Bd du Triomphe, B-1050 Bruxelles, Belgium |
| |
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. |
| |
Keywords: | network design combinatorial optimization branch-and-cut |
本文献已被 SpringerLink 等数据库收录! |
|