Combining intensification and diversification strategies in VNS. An application to the Vertex Separation problem

Jesús Sánchez-Oro, Juan José Pantrigo, Abraham Duarte
January, 2014
Cite DOI

Abstract

The Vertex Separation problem (VSP) is an NP-hard problem with practical applications in VLSI design, graph drawing and computer language compiler design. VSP belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. In this paper, we propose different heuristic methods and embed them into a Variable Neighborhood Search scheme to solve this problem. More precisely, we propose (i) a constructive algorithm, (ii) four shake procedures, (iii) two neighborhood structures, (iv) efficient algorithmic strategies to explore them, (v) an extended version of the objective function to facilitate the search process and finally, (vi) we embed these strategies in a Reduced Variable Neighborhood Search (RVNS), a Variable Neighborhood Descent (VND) and a General Variable Neighborhood Search (GVNS). Additionally, we provide an extensive experimental comparison among them and with the best previous method of the literature. We consider three different benchmarks, totalizing 162 representative instances. The experimentation reveals that our best procedure (GVNS) improves the state of the art in both quality and computing time. This fact is confirmed by non-parametric statistical tests. In addition, when considering only the largest instances, the other two proposed variants (RVNS and VND) also obtain statistically significant differences with respect to the best previous method identified in the state of the art.

Type
Journal article
Publication
Computers & Operations Research
Jesús Sánchez-Oro
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.

Abraham Duarte
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.