90-08 Computational methods
A Branch-Cut-And-Price Algorithm for a Combined Buy-at-Bulk Network Design Facility Location Problem
(2014)
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.
The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor.
This paper proposes a slight modification of the algorithm in order to find better solutions.
Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.