A Branch-Cut-And-Price Algorithm for a Combined Buy-at-Bulk Network Design Facility Location Problem
Please always quote using this URN:urn:nbn:de:0296-matheon-12832
- In the combined buy-at-bulk network design facility location problem we are given an undirected network with a set of potential facilities and a set of clients with demands. In addition, we are also provided a set of cable types with each cable type having a capacity and cost per unit length. The cost to capacity ratio decreases from large to small cables following economies of scale. A network planner is expected to determine a set of facilities to open and install cables along the edges of the network in order to route the demands of the clients to some open facility. The capacities of the installed cable must be able to support the demands of the clients routed along that edge.The objective is to minimize the cost that is paid for opening facilities and installing cables. We model the problem as an integer program and propose a branch-cut-and-price algorithm for solving it. We study the effect of two family of valid inequalities that naturally emerge from the model. We present the results of our implementation that were tested on a set of large real world instances.
Author: | Ashwin Arulselvan, Mohsen Rezapour, Wolfgang Welz |
---|---|
URN: | urn:nbn:de:0296-matheon-12832 |
Referee: | Martin Skutella |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2014/05/05 |
Release Date: | 2014/05/05 |
Institute: | Technische Universität Berlin |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods |
Preprint Number: | 1057 |