A New Local Search Algorithm for Binary Optimization

A New Local Search Algorithm for Binary Optimization

By
Dan A. Iancu, Dimitris Bertsimas, Dmitriy Katz
INFORMS Journal on Computing.
2013, Vol. 25, Issue 2, Pages 208-221

We develop a new local search algorithm for binary optimization problems, whose complexity and performance are explicitly controlled by a parameter Q, measuring the depth of the local search neighborhood. We show that the algorithm is pseudo-polynomial for general cost vector c, and achieves a w2/(2w1) approximation guarantee for set packing problems with exactly w ones in each column of the constraint matrix A, when using Q = w2. Most importantly, we find that the method has practical promise on large, randomly generated instances of both set covering and set packing problems, as it delivers performance that is competitive with leading general-purpose optimization software (CPLEX 11.2).