Solving the Two-Connected Network with Bounded Meshes Problem

Bernard Fortz, Martine Labbé and Francesco Maffioli
Additional contact information
Bernard Fortz: Institut de Statistique et de Recherche Opérationnelle, SMG, Université Libre de Bruxelles, Belgium
Martine Labbé: Institut de Statistique et de Recherche Opérationnelle, SMG, Université Libre de Bruxelles, Belgium
Francesco Maffioli: DEI, Politecnico di Milano, Italy

Operations Research, 2000, vol. 48, issue 6, 866-877

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

Keywords: Communication: survivable network design/model for communication network design, Programming; integer: cutting plane and heuristics/ILP: branch-and-cut heuristics (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.6.866.12390 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:6:p:866-877

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().