Authors: Mladenović, Nenad 
Urošević, Dragan 
Pérez-Brit, Dionisio
Title: Variable neighborhood search for minimum linear arrangement problem
Journal: Yugoslav Journal of Operations Research
Volume: 26
Issue: 1
First page: 3
Last page: 14
Issue Date: 1-Jan-2016
Rank: M51
ISSN: 0354-0243
DOI: 10.2298/YJOR140928038M
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 | Minimum linear arrangement problem | Optimization | Variable neighborhood search
Publisher: Faculty of Organizational Sciences, University of Belgrade
Project: RSF grant 14-41-00039
Gobierno de Canarias grant SolSubC200801000048

Show full item record


checked on Jul 24, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.