Solving the two-connected network with bounded meshes problem
成果类型：
Article
署名作者：
Fortz, B; Labbé, M; Maffioli, F
署名单位：
Universite Libre de Bruxelles; Polytechnic University of Milan
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.6.866.12390
发表日期：
2000
页码：
866-877
关键词：
摘要：
We study the problem of designing at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a mesh) does not exceed a given length K. This problem arises in the design of fiber-optic-based backbone telecommunication networks. A Branch-and-Cut approach to this problem is presented for which we introduce several families of valid inequalities and discuss the corresponding separation algorithms. Because the size of the problems solvable to optimality by this approach is too small, we also develop some heuristics. The computational performances of these exact and approximate methods are then thoroughly assessed both on randomly generated instances as well as instances suggested by real applications.