Title:
Local Search Heuristics for Unconstrained Quadratic Binary Optimization

Authors:
Endre Boros,
Peter L. Hammer, and
Gabriel Tavares

Abstract:
We study and analyze a family of local search based heuristics for unconstrained quadratic binary optimization. These types of methods, also known in the literature as 1-opt or greedy heuristics, change the values of the variables, iteratively one by one, increasing the value of the objective function in each iteration, until a local optimum is reached. The quality of the obtained solution and the computational time of such methods depend on various parameters, including the choice of the starting point and in each iteration the choice of the variable, the value of which is changed. By choosing different policies for these choices, we propose a family of such methods involving 40 different heuristics. We analyze the effect of the various parameters of these methods, as well as the various characteristics of the considered problems on the algorithm's performance empirically, involving thousands of randomly generated problems with number of variables ranging from 20 to 2500. Based on our analysis we constructed one particular variant, which we call ACSIOM, the performance of which dominated the other variants over all problems types. Finally, we compare this heuristic with the best results from recent publication, involving a large set of widely used benchmark problems.