Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4958984 | Computers & Operations Research | 2017 | 15 Pages |
Abstract
Given an undirected simple graph G, the profile minimization problem (PMP) is to find an ordering of the vertices of the graph G such that the sum of the profiles of all its vertices is minimized. The profile of the vertex v in position i is defined as max{0,iâhv}, where hv is the position of the leftmost vertex among all vertices adjacent to v in G. We propose an approach for the PMP, which combines a variable neighborhood search (VNS) scheme with the multi-start simulated annealing (MSA) technique. The solution delivered by MSA is submitted as input to the VNS component of the method. The VNS algorithm heavily relies on a fast insertion neighborhood exploration procedure. We show that the time complexity of this procedure is O(n2), where n is the order of G. We have found empirically that it is advantageous to give between 50 and 75% of the computation time to MSA and the rest to VNS. The results of the computational experiments demonstrate the superiority of our MSA-VNS algorithm over the current state-of-the-art metaheuristic approaches for the PMP. Using MSA-VNS, we improved the best known solutions for 50 well-recognized benchmark PMP instances in the literature. The source code implementing MSA-VNS is made publicly available as a benchmark for future comparisons.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gintaras Palubeckis,