Greedy and local search heuristics for unconstrained binary quadratic programming

Greedy and local search heuristics for unconstrained binary quadratic programming

0.00 Avg rating0 Votes
Article ID: iaor20023496
Country: Netherlands
Volume: 8
Issue: 2
Start Page Number: 197
End Page Number: 213
Publication Date: Mar 2002
Journal: Journal of Heuristics
Authors: ,
Keywords: heuristics
Abstract:

In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem. These heuristics are well suited for the incorporation into meta-heuristics such as evolutionary algorithms. Their performance is compared for 115 problem instances. All methods are capable of producing high quality solutions in short time. In particular, the greedy heuristic is able to find near optimum solutions a few percent below the best-known solutions, and the local search procedures are sufficient to find the best-known solutions of all problem instances with n ≤ 100. The k-opt local searches even find the best-known solutions for all problems of size n ≤ 250 and for 11 out of 15 instances of size n = 500 in all runs. For larger problems (n = 500, 1000, 2500), the heuristics appear to be capable of finding near optimum solutions quickly. Therefore, the proposed heuristics – especially the k-opt local search – offer a great potential for the incorporation in more sophisticated meta-heuristics.

Reviews

Required fields are marked *. Your email address will not be published.