Abstract
Many optimization problems are formulated as min–max problems where the objective function consist of minimizing a maximum value. In this case, it is usual that many solutions of the problem has associated the same value of the objective function. When this happens it is difficult to determine which solution is more promising to continue the search. In this paper we propose a new variant of the Variable Neighbourhood Search methodology to tackle this kind of problems. The new variant, named Variable Formulation Search, makes use of alternative formulations of the problem to determine which solution is more promising when they have the same value of the objective function in the original formulation. We do that in shaking, local search and neighbourhood change steps of the basic Variable Neighbourhood Search. We apply the new methodology to the Cutwidth Minimization Problem. Computational results show that our proposal outperforms previous algorithms in the state of the art in terms of quality and computing time.
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.
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.