中文

Operations Research Transactions >

2015 , Vol. 19 >Issue 4: 37 - 47

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.04.004

A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem

Expand
  • 1.School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Center for Supernetworks Research, University of Shanghai for Science and Technology, Shanghai 200093, China

Received date: 2014-11-24

  Online published: 2015-12-15

Fold

Abstract

The un-capacitated facility location (UFL) problem is a classical combinatorial optimization hard problem and has been applied in various fields. The semi-Lagrangian relaxation method is one of the exact solution methods to the UFL. In this paper, the mathematical nature of the SLR applied to solve the UFL is further studied. Based on this, the SLR applied to solve the UFL is improved from the theoretical point of view, and the approach is also discussed to enhance its
computational capability. The numerical results show that the improvement proposed in this paper is feasible and effective.

Key words： Un-capacitated facility location; Lagrangian relaxation; Semi-Lagrangian relaxation; Primal-dual optimal solution

Cite this article

ZHANG Huizhen, WEI Xin, MA Liang . A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem[J]. Operations Research Transactions, 2015 , 19(4) : 37 -47 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.04.004

References

堵丁柱, 葛可一, 胡晓东. 近似算法的设计与分析 [M]. 北京：高等教育出版社, 2011.


Klose A. A branch and bound algorithm for an UFLP with a side constrain [J]. International Transactions in Operational Research, 1998,5(2): 155-168.

Al-Sultan K S, Al-Fawzan M A. A tabu search approach to the uncapacitated facility location problem [J].Annals of Operations Research, 1999, 86: 91-103.

Laurent M, Hentenryck P V. A simple tabu search for warehouse location [J]. European Journal of Operational Research, 2004,157(3): 576-591.

Jaramillo J H, Bhadury J, Batta R. On the use of genetic algorithms to solve location problems [J]. Computers and Operations Research, 2002, 29(6): 761-779.

Ghosh D. Neighborhood search heuristics for the uncapacitated facility location problem [J]. European Journal of Operational Research, 2003, 150(1): 150-162.

王大志, 闫杨, 汪定伟, 等. 基于OpenMP求解无容量设施选址问题的并行PSO算法 [J]. 东北大学学报(自然科学版), 2008, 29(12): 1681-1684.

Sujay Saha, Arnab Kole, Kashinath Dey. A Modified Continuous Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem [A]//Information Technology and Mobile Communication, Communications in Computer and Information Science [C]//Berlin Heidelberg: Springer, 2011, 305-311.

Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem [J]. Information and Computation,2013, 222(1): 45-58.

Beltran-Royo C, Tadonki C, Vial J.-Ph. Solving the p-median problem with a semi-Lagrangian relaxation [J].  Computational Optimization and Applications, 2006,35(2): 239-260.

Beltran-Royo C, Vial J.-P, Alonso-Ayuso A. Semi-Lagrangian relaxation applied to the uncapacitated facility location problem [J]. Computational Optimization and Applications, 2012,51(1): 387-409.

M. Hoefer. Ufllib, 2006. http://www.mpi-inf.mpg.de/departments/d1/projects/benchmarks/ UflLib/index.html.

 
Options
Outlines

/

〈 〉