An experimental comparison of Variable Neighborhood Search variants for the minimization of the vertex-cut in layout problems

Abstract

Variable Neighborhood Search (VNS) is a metaheuristic for solving optimization problems based on a systematic change of neighborhoods. In recent years, a large variety of VNS strategies have been proposed. However, we have only found limited experimental comparisons among different VNS variants. This paper reviews three VNS strategies for finding near-optimal solutions for vertex-cut minimization problems. Specifically, we consider the min-max variant (Vertex Separation Problem) and the min-sum variant (SumCut Minimization Problem). We also present an preliminary computational comparison of the methods on previously reported instances.

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

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.