|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||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 | 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 Apr 15, 2021
checked on Apr 16, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.