Fortz, Bernard
[UCL]
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´e and Maffioli
[6]. 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 new classes of
facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using
these inequalities show their effectiveness for solving the problem.
Bibliographic reference |
Fortz, Bernard. Two-connected networks with rings of bounded cardinality. IAG - LSM Working Papers ; 02/68 (2002) 24 pages |
Permanent URL |
http://hdl.handle.net/2078/18241 |