Polyhedral results for two-connected networks with bounded rings

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

Abstract: We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a ``ring'') does not exceed a given length K. We present here a new formulation of the problem and derive facet results for different classes of valid inequalities. We study the separation problems associated to these inequalities and their integration in a Branch-and-Cut algorithm, and provide extensive computational results.

Keywords: branch-and-cut, network design

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

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

Category 3: Combinatorial Optimization (Polyhedra )

Citation: IAG Working Paper 03/01, Université Catholique de Louvain, 2001. To appear in Mathematical Programming.

Download:

Entry Submitted: 05/22/2001
Entry Accepted: 05/22/2001
Entry Last Modified: 07/03/2002

Modify/Update this entry