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 witch 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. | Yugoslav Journal of Operations Research 26 (2016), Number 1, 3–16 DOI: VARIABLE NEIGHBORHOOD SEARCH FOR MINIMUM LINEAR ARRANGEMENT PROBLEM ´ Nenad MLADENOVIC LAMIH, University of Valenciennes, France ˇ ´ Dragan UROSEVI C Mathematical Institute SANU, Belgrade draganu@ ´ Dionisio PEREZ-BRIT Departamentos de Estad´ıstica, Investigaci´on Operativa y Computaci´on, Universidad de La Laguna, Spain. Dperez@ Received: September 2014 / Accepted: December 2014 Abstract: 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 witch 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. Keywords: Graphs, Optimization, Minimum linear arrangement problem, Variable neighborhood search. MSC: 90B06, 90C05, 90C08. 4 N. Mladenovi´c, D. Uroˇsevi´c, D. P´erez-Brito / VNS for MinLA Problem 1. INTRODUCTION Let G = (V, E) be an undirected graph, where V is a set of vertices, and E be a set of undirected edges. Let labelling be any bijective mapping f of V into itself: V → {1, ., n} (n = |V|). For a given labelling f one can calculate cost of mapping C f as: ∑ Cf = | f (u) − f (v)| (u,v)∈E Minimum arrangement problem (MinAP) consists of finding labelling f whose cost C f is minimal. Let us denote with S a set of all valid labelling. We suppose that vertices .
