Article ID: | iaor20032475 |
Country: | Germany |
Volume: | 93 |
Issue: | 1 |
Start Page Number: | 27 |
End Page Number: | 54 |
Publication Date: | Jan 2002 |
Journal: | Mathematical Programming |
Authors: | Labb M., Fortz B. |
We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a ‘ring’) does not exceed a given length K. We present here a new formulation of the problem and derive facet results for different classes of valid inequalities. We study the separation problems associated to these inequalities and their integration in a Branch-and-Cut algorithm, and provide extensive computational results.