Optimization Online


Two-connected networks with rings of bounded cardinality

Bernard Fortz (fortz***at***poms.ucl.ac.be)
Martine Labbé (mlabbe***at***smg.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society