This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Bastert, O. Articles by de Vries, S.

A Generalized Wedelin Heuristic for Integer Programming

FICO, Leam House, Leamington Spa, Warwickshire CV32 5YN, United Kingdom
Institut für Informatik, Technische Universität München, 85747 Garching bei München, Germany
FB IV - Mathematik, Universität Trier, 54286 Trier, Germany
oliverbastert{at}fico.com
hummelb{at}in.tum.de
devries{at}uni-trier.de

A very important ingredient for solving hard general integer programs are heuristics that try to quickly find good feasible solutions. One of these heuristics is Wedelin's algorithm, which works for the limited class of 0-1 integer programs. A big advantage of Wedelin's approach is that it does not depend on a solution of the linear programming (LP) relaxation as many other heuristics do. This makes it extremely fast in practice and makes it easy to use the parallelism of the upcoming multicore CPUs, as in an integer programming (IP) solver it could be applied in parallel to the traditional branch-and-bound algorithm.

In this paper, we present several extensions and generalizations to Wedelin's algorithm (most can be handled in an implicit manner without much performance cost) and investigate different ways of improving it. We give all necessary details and parameters. We strive for an algorithm that is faster than other heuristics but achieves comparable solution quality.

We evaluate the performance of the algorithm on a large set of more than 100 instances from different sources. The results indicate that our heuristic often finds solutions comparable to or even better than those found using current state-of-the-art heuristics while typically needing only a fraction of their running time.

Additionally, we report positive findings on the application of the heuristic on feasibility instances from discrete tomography. Our algorithm always finds the IP optimum in less time than the simplex/barrier algorithms and often in less time than it takes the volume algorithm to find just the LP optimum.

Key words: integer programming algorithms/heuristics
History: received January 2007; revised July 2008; accepted February 2009.