zbMATH — the first resource for mathematics

Greedy and local search heuristics for unconstrained binary quadratic programming. (English) Zbl 1013.90100
Summary: 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 \leq 100\). The \(k\)-opt local searches even find the best-known solutions for all problems of size \(n \leq 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.

90C20 Quadratic programming
90C59 Approximation methods and heuristics in mathematical programming
90B40 Search theory
Full Text: DOI