Perturbation Heuristics for Unconstrained Quadratic 0–1 Programming and an Alternate Stopping and Comparison Criterium
Kim Allemand, Thomas M. Liebling · 2001
Given quadratic function f the unconstrained quadratic zero-one programming problem consists in minimizing f (x) where x is a zero-one vector of dimension n. This problem is NP-hard and therefore the most efficient results have been obtained by heuristics. As optimal solutions are in most cases unkown, comparisons between heuristics are usually based on the shortest time to reach the best known solution. This approach is arbitrary and depends on both problem size and computer speed. We present an alternate comparison and stopping criterium based on an approximate count evaluations of the objective function. This comparison technique will be applied on descent algorithms embedded in a multi-start heuristic scheme. Finally, some results for public instances of various sizes will be reported.