|
Abstract : |
We study a version of the capacity expansion problem (CEP) that arises in telecommunication network design. Given a capacitated network and a traffic demand matrix, the objective in the CEP is to add capacity to the edges, in batches of various modularities, and route traffic, so that the overall cost is minimized. We study the polyhedral structure of a mixed-integer formulation of the problem and develop a cutting-plane algorithm using facet defining inequalities. The algorithm produces an extended formulation providing both a very good lower bound and a starting point for branch and bound. The overall algorithm appears effective when applied to problem instances using real-life data. 1 Introduction and Formulation. In this paper we study the polyhedral structure of a mixed-integer programming formulation of the capacity expansion problem (CEP) and present computational results related with a cutting-plane algorithm which uses facet defining inequalities, |
