  


GRASP with path relinking heuristics for the antibandwidth problem
Abraham Duarte(abraham.duarteurjc.es) Abstract: This paper 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 highquality solutions in much less time than the commercial solver. Keywords: Metaheuristics, bandwidth, antibandwidth, GRASP, pathrelinking, evolutionary pathrelinking Category 1: Combinatorial Optimization (Meta Heuristics ) Category 2: Global Optimization (Stochastic Approaches ) Category 3: Integer Programming (01 Programming ) Citation: AT&T Labs Research Technical Report, Florham Park, NJ 07932 USA, August 2009. Download: [PDF] Entry Submitted: 08/09/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  