Capacitated network design—polyhedral structure and computation

Capacitated network design—polyhedral structure and computation

0.00 Avg rating0 Votes
Article ID: iaor19982964
Country: United States
Volume: 8
Issue: 3
Start Page Number: 243
End Page Number: 259
Publication Date: Jun 1996
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: programming: integer
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 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.

Reviews

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