Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.