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: | Klose Andreas, Grtz Simon |
Keywords: | programming: integer, lagrange multipliers |
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.