INFORMS journal on computing · 1996 · 204 citations · 0 references
Natural SciencesComputer ScienceOperations ManagementCapacity PlanningDesign OptimizationOptimizationBranch And BoundCombinatorial OptimizationInteger ProgrammingNetwork Capacity PlanningNetwork Flow AlgorithmsNetwork OptimizationCapacitated Network DesignMixed-integer OptimizationMixed-integer ProgrammingNetwork Cost OptimizationNetwork Design ProblemsNetwork Flow ProblemsPolyhedral TheoryTelecommunications Network Design
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.
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.