A New Local Search Algorithm for Binary Optimization

Local search for binary optimization normally trades solution quality against running time with no principled way to set the dial. We develop a general-purpose algorithm whose single parameter controls both the depth of the search and its computational cost. The method has a formal approximation guarantee for a class of set-packing problems and, on large randomly generated set-covering and set-packing instances, performs competitively with leading general-purpose optimization software.

INFORMS Journal on Computing, vol. 25, no. 2, pp. 208–221