出版社：Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Economics Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mechanical Engineering, Belgrade
摘要：The minimum linear arrangement problem is widely used and studied in many practical and theoretical applications. It consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. This problem is one among the classical NP-hard optimization problems and therefore there has been extensive research on exact and approximative algorithms. In this paper we present an implementation of a variable neighborhood search (VNS) for solving minimum linear arrangement problem. We use Skewed general VNS scheme that appeared to be successful in solving some recent optimization problems on graphs. Based on computational experiments, we argue that our approach is comparable with the state-of-the-art heuristic.
关键词：graphs; optimization; minimum linear arrangement problem; variable neighborhood search
