Abstract
The cutwidth minimization problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this problem, such as Simulated Annealing and Evolutionary Path Relinking.
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.