Premium
GRASP with path relinking heuristics for the antibandwidth problem
Author(s) -
Duarte A.,
Martí R.,
Resende M.G.C.,
Silva R.M.A.
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20418
Subject(s) - heuristics , solver , grasp , integer programming , node (physics) , path (computing) , mathematical optimization , computer science , set (abstract data type) , graph , linear programming , mathematics , theoretical computer science , structural engineering , engineering , programming language
Abstract This article proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with n nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2,…, n }, such that, among all adjacent node pairs, the minimum difference between the node labels is maximized. Computational results show that only small instances of this problem can be solved exactly (to optimality) with a commercial integer programming solver and that the heuristics find high‐quality solutions in much less time than the commercial solver. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(3), 171–189 2011