A New Local Search Algorithm for Binary Optimization

A New Local Search Algorithm for Binary Optimization

0.00 Avg rating0 Votes
Article ID: iaor20132446
Volume: 25
Issue: 2
Start Page Number: 208
End Page Number: 221
Publication Date: Mar 2013
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: covering problems, packing
Abstract:

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 w 2/(2w‐1) approximation guarantee for set packing problems with exactly w ones in each column of the constraint matrix A, when using Q = w 2. 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).

Reviews

Required fields are marked *. Your email address will not be published.