Title :
An adaptive version of parallel MPSO with OpenMP for Uncapacitated Facility Location problem
Author :
Dazhi Wang ; Dingwei Wang ; Yang Yan ; Hongfeng Wang
Author_Institution :
Sch. of Inf. Sci. & Eng., Northeastern Univ., Shenyang
Abstract :
As a consequence of globalization, facilitypsilas location selection has become a markedly complicated problem. This problem is one of the most difficult combinatorial NP-hard optimization problems. Historically, this kind of problems have been usually solved by linear programming or metaheuristics methods such as genetic algorithms (GA), simulated annealing (SA), particle swarm optimization (PSO) and tabu searches with optima or near-optima. In this paper, an adaptive parallel multi-population particle swarm optimization (MPSO) algorithm with OpenMP is presented for the Uncapacitated Facility Location problem (UFLP), The linear inertia weight was introduced which made an ideal balance between the capability of global exploration and the capability of local exploitation. The aim of this paper is to implement an adaptive version of parallel MPSO method augmented with OpenMP directives and then applied it to the several benchmark suites offered by OR library. It is shown that dramatic improvement in terns of CPU times is achieved with competitive results by using a parallel programming model in a multi-core desktop.
Keywords :
combinatorial mathematics; computational complexity; facility location; globalisation; particle swarm optimisation; OpenMP; adaptive parallel multipopulation particle swarm optimization; combinatorial NP-hard optimization problem; facility location selection; global exploration; globalization; linear inertia weight; local exploitation; multicore desktop; parallel programming model; uncapacitated facility location problem; Acceleration; Algorithm design and analysis; Computational modeling; Computers; Data models; Optimization; Simulated annealing; Linear Inertia Weight; MPSO; OpenMP; Parallel Computation; Uncapacitated Facility Location Problem;
Conference_Titel :
Control and Decision Conference, 2008. CCDC 2008. Chinese
Conference_Location :
Yantai, Shandong
Print_ISBN :
978-1-4244-1733-9
DOI :
10.1109/CCDC.2008.4597752