Abstract
Variable neighbourhood search (VNS) and all its variants have been successfully proved in hard combinatorial optimization problems. However, there are only few works concerning parallel VNS algorithms, compared with the amount of works devoted to sequential VNS design. In this paper, we propose different parallel designs for the VNS schema. We illustrate the performance of these general strategies by parallelizing a new VNS variant called variable formulation search (VFS). Specifically, we propose six different variants which differ in the VNS stages to be parallelized as well as in the communication mechanisms among processes. We group these variants into three different templates. The first one is oriented to parallelize the whole VNS method. The second one parallelizes the shake and the local search procedures. Finally, the third one explores in parallel the set of predefined neighbourhoods. We test the resulting designs on the cutwidth minimization problem (CMP). Experimental results show that the parallel implementation of the VFS outperforms previous methods in the state of the art for the CMP. This fact is also confirmed by non-parametric statistical tests.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.
Eduardo García Pardo
Full Professor
One of the founders of the investigation group GRAFO, whose main line of research is the development of algorithms to tackle optimization problems, the topic of the researcher’s Doctoral Thesis and which their most notable publications are framed.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.