Inhaltszusammenfassung

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 multico...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. » weiterlesen» einklappen

Autoren