Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6893149 | Computers & Operations Research | 2013 | 8 Pages |
Abstract
This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Yang Wang, Zhipeng Lü, Fred Glover, Jin-Kao Hao,