Two-connected networks with rings of bounded cardinality

Bernard Fortz (fortzpoms.ucl.ac.be)
Martine Labbé (mlabbesmg.ulb.ac.be)

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. 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.

Keywords: Branch-and-cut, network design

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Citation: IAG Working Paper 68/02, Université Catholique de Louvain, 2002.

Download: [PDF]

Entry Submitted: 07/03/2002
Entry Accepted: 07/03/2002
Entry Last Modified: 07/03/2002

Modify/Update this entry