Affiliations: Department of Industrial Engineering, Hanyang University, 17 Haengdang-dong, Seongdong-gu, Seoul 133-791, Korea, e-mail: art4life94@naver.com | Graduate School of Technology and Innovation Management, Hanyang University, 17 Haengdang-dong, Seongdong-gu, Seoul 133-791, Korea, e-mail: ghchoi@hanyang.ac.kr | Department of Industrial Engineering, Konkuk University, 1 Hwayang-dong, Gwangjin-gu, Seoul 143-701, Korea, e-mail: ssko@konkuk.ac.kr
Abstract: In this article, we propose a practical algorithm for capacitated facility location problems (CFLP). There are some approaches which can obtain primal solutions while simultaneously exploiting the primal structure and the dual structure. One of these approaches is the mean value cross decomposition (MVCD) method that ensures convergence without solving master problems. However, MVCD has been previously applied only to uncapacitated facility location problems (UFLP), due to the fact that the performance is highly dependent on the structure of the problem. The proposed algorithm, named the dynamic mean value cross decomposition algorithm (DMVCD), is effectively integrated with MVCD and cutting plane methods in order to tighten the bounds by reducing the duality gap. Computational results of various instances are also reported to verify the effectiveness and efficiency of DMVCD.
Keywords: capacitated facility location problems, cross decomposition, mean value cross decomposition, primal recovery strategies, Lagrangian relaxation
Journal: Informatica, vol. 24, no. 4, pp. 523-542, 2013
