A branch-and-cut algorithm for capacitated network design problems

A branch-and-cut algorithm for capacitated network design problems

0.00 Avg rating0 Votes
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:
Keywords: programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.