Implementing Lagrangean Decomposition Technique to Acquire an Adequate Lower Boundon the Facility Location Problem Solution


In this work, the Lagrangean Relaxation method has been discussed to solve different sizes of capacitated facility location problem (CFLP). A good lower bound has been achieved on the solution of the CFLP considered in this paper. This lower bound has been improved by using the Volume algorithm. The methods of setting two important parameters in heuristic have been given. The approaches used to gain the lower bound have been explained. The results of this work have been compared with the known results given by Beasley.

Share and Cite:

E. Alenezy and R. Khalaf, "Implementing Lagrangean Decomposition Technique to Acquire an Adequate Lower Boundon the Facility Location Problem Solution," Applied Mathematics, Vol. 4 No. 8, 2013, pp. 1168-1172. doi: 10.4236/am.2013.48156.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] K. Holmberg, M. Ronnqvist and D. Yuan, “An Exact Algorithm for the Capacitated Facility Location Problems with Single Sourcing,” European Journal of Operational Research, Vol. 113, No. 3, 1999, pp. 544-559. doi:10.1016/S0377-2217(98)00008-3
[2] S. Melkote and M. S. Daskin, “Capacitated Facility Loca tion-Network Design Problems,” European Journal of Operational Research, Vol. 129, No. 3, 2001, pp. 481 495. doi:10.1016/S0377-2217(99)00464-6
[3] R. K. Ahuja, J. B. Orlin, S. Pallottino, M. P. Scaparra and M. G. Scutella, “A Multiexchange Heuristic for the Sin gle-Source Capacitated Facility Location Problem,” Man agement Science, Vol. 50, No. 6, 2004, pp. 749-760. doi:10.1287/mnsc.1030.0193
[4] M. J. Cortinhal and M. E. Captivo, “Genetic Algorithms for the Single Source Capacitated Location Problem,” Metaheuristics: Computer Decision-Making, Vol. 86, 2004, pp. 187-216.
[5] I. A. Contreras and J. A. Diaz, “Scatter Search for the Single Source Capacitated Facility Location Problem,” Annals of Operations Research, Vol. 157, No. 1, 2008, pp. 73-89. doi:10.1007/s10479-007-0193-1
[6] M. Leitner and G. R. Raidl, “A Lagrangian Decomposi tion Based Heuristic for Capacitated Connected Facility Location,” In: S. VoB and M. Caserta, Eds., Proceedings of the 8th Metaheuristic International Conference (MIC 2009), Hamburg, 13-16 July 2009.
[7] M. Held and R. M. Karp, “The Travelling Salesman Prob lem and Minimum Spanning Trees,” Operations Re search, Vol. 18, No. 6, 1970, pp. 1138-1162. doi:10.1287/opre.18.6.1138
[8] E. J. Alenezy, “Practical Techniques to Solve Capacitated Facility Location Problem,” Far East Journal of Mathe matical Sciences (FJMS), Vol. 37, No. 1, 2010, pp. 49-60.
[9] M. Held, C. Wolf and H. Crowder, “Validation Subgradient Optimisation,” Mathematical Programming, Vol. 6, No. 1, 1974, pp. 62-88. doi:10.1007/BF01580223
[10] F. Barahona and R. Anbil, “The Volume Algorithm: Pro ducing Primal Solutions Using a Subgradient Method,” Mathematical Programming, Vol. 87, No. 3, 2000, pp. 385-399. doi:10.1007/s101070050002
[11] D. Serra, S. Ratick and C. Revelle, “The Maximum Cap ture Problem with Uncertainty,” Environment and Plan ning, Vol. B23, No. 1, 1996, pp. 49-59.
[12] G. Cornuejols, R. Sridharn and J. Thizy, “A Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem,” European Journal and Opertional Research, Vol. 50, No. 3, 1991, pp. 280-297. doi:10.1016/0377-2217(91)90261-S
[13] J. E. Beasley, (1990), “Distributing Test Problems by Electronic Mail,” Journal of the Operational Research Society, Vol. 41, No. 11, 1990, pp. 1069-1072.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.