@techreport{TR-IC-05-26,
  number = {IC-05-26},
  author = {Elder M. Macambira and Nelson Maculan and Cid C. de Souza},
  title = {Integer  programming models for the {SONET} ring  assignment
           problem},
  month = {October},
  year = {2005}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 31 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       In this paper we consider the SONET ring assignment problem
       (SRAP) presented by Goldschmidt et al. in (SONET/SDH ring
       assignment with capacity constraints, Discrete Applied
       Mathematics, 129:99--128, 2003).  The authors pointed out to
       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 by Aringhieriand Dell'Amico (Comparing metaheuristic
       algorithms for sonet network design problems, Journal of
       Heuristics, 11(1):35--57, 2005).  In this paper we presented
       some variants of IP formulations for SRAP and tested the
       performance of standard branch-and-bound algorithms implemented
       in a commercial code when computing those models.  The results
       are significantly better than those reported earlier in the
       literature.  Moreover, we also reformulate the problem as a set
       partitioning model amended 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 with our algorithm showed that it is
       orders of magnitude faster than its competitors.  Hundreds of
       instances taken from both Aringhieri's and Goldschmidt's papers
       which were not solved by these authors in hours of computation
       are solved here to optimality in just a few seconds.
  }
}