Solving the two-connected network with bounded meshes problem

Solving the two-connected network with bounded meshes problem

0.00 Avg rating0 Votes
Article ID: iaor20021509
Country: United States
Volume: 48
Issue: 6
Start Page Number: 866
End Page Number: 877
Publication Date: Nov 2000
Journal: Operations Research
Authors: , ,
Keywords: programming: integer, programming: branch and bound
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.

Reviews

Required fields are marked *. Your email address will not be published.