Abstract
The capacitated facility location problem (CFLP) 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. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.
| Original language | English |
|---|---|
| Journal | European Journal of Operational Research |
| Volume | 179 |
| Issue | 3 |
| Pages (from-to) | 1109-1125 |
| Number of pages | 17 |
| ISSN | 0377-2217 |
| DOIs | |
| Publication status | Published - 16 Jun 2007 |
Keywords
- Capacitated facility location; Mixed-integer programming; Lagrangean relaxation; Column generation; Branch-and-price