Polyhedral results for two-connected networks with bounded rings

被引：17

作者：

Fortz, B

Labbé, M

机构：

[1] Univ Catholique Louvain, Inst Adm & Gest, B-1348 Louvain, Belgium

[2] Free Univ Brussels, Serv Math Gest, Inst Stat & Rech Operationnelle, B-1050 Brussels, Belgium

来源：

MATHEMATICAL PROGRAMMING | 2002年 / 93卷 / 01期

关键词：

D O I：

10.1007/s10107-002-0299-9

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：27 / 54

页数：28

共 16 条

[1]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3] SEPARATING FROM THE DOMINANT OF THE SPANNING TREE POLYTOPE [J].