A branch-and-price algorithm for the capacitated facility location problem

A branch-and-price algorithm for the capacitated facility location problem

0.00 Avg rating0 Votes
Article ID: iaor2009131
Country: Netherlands
Volume: 179
Issue: 3
Start Page Number: 1109
End Page Number: 1125
Publication Date: Jun 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer, lagrange multipliers
Abstract:

The capacitated facility location problem is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly.

Reviews

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