Article ID: | iaor20002348 |
Country: | Germany |
Volume: | 86 |
Issue: | 1 |
Start Page Number: | 17 |
End Page Number: | 39 |
Publication Date: | Jan 1999 |
Journal: | Mathematical Programming |
Authors: | Gnlk O. |
Keywords: | programming: branch and bound |
We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities, are used as cutting planes. To choose the branching variable, we use a new rule called ‘knapsack branching’. We also report on our computational experience using real-life data.