Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/52920
Type: Artigo de periódico
Title: A column generation approach for SONET ring assignment
Author: Macambira, EM
Maculan, N
de Souza, CC
Abstract: In this article we consider the SONET ring assignment problem (SRAP) presented in [7]. The authors pointed out the inadequacy of solving SRAP instances using their integer programming formulation and commercial linear programming solvers. Similar experiences with IP models for SRAP are reported in [1]. In this article we reformulate SRAP as a set partitioning model with an additional knapsack constraint. This new formulation has an exponential number of columns and, to solve it, we implemented a branch-and-price/column generation algorithm. Extensive computational experiments showed that the new algorithm is orders of magnitude faster than standard branch-and-bound codes running on compact IP models introduced earlier. Instances taken from [1,7], which could not be solved there in hours of computation were solved here to optimality in just a few seconds. (c) 2006 Wiley Periodicals, Inc.
Subject: telecommunication network design
SONET ring
integer programming
column generation
branch-and-price algorithm
Country: EUA
Editor: John Wiley & Sons Inc
Rights: fechado
Identifier DOI: 10.1002/net.20102
Date Issue: 2006
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000236740000004.pdf181.39 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.