Capacitated Network Design—Polyhedral Structure and Computation

TLDR

The paper investigates a capacity expansion problem in telecommunication network design, aiming to add capacity to edges in multiples of modularities and route traffic to minimize overall cost. The authors analyze the polyhedral structure of a mixed‑integer formulation and propose a cutting‑plane algorithm that generates an extended formulation, yielding strong lower bounds and a branch‑and‑bound starting point. Experiments on real‑life data show the algorithm performs effectively.

Abstract

We study a capacity expansion problem that arises in telecommunication network design. Given a capacitated network and a traffic demand matrix, the objective is to add capacity to the edges, in multiples 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 vary 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.