Article ID: | iaor20003724 |
Country: | United States |
Volume: | 45 |
Issue: | 11 |
Start Page Number: | 1539 |
End Page Number: | 1551 |
Publication Date: | Nov 1999 |
Journal: | Management Science |
Authors: | Sierksma Gerard, Tijssen Gert A., Goldengorin Boris, Tso Michael |
Keywords: | optimization |
The Data-Covering (DC) Algorithm is a recursive branch-and-bound type algorithm, in which the data of a given problem instance are ‘heuristically corrected’ at each branching in such a way that the new instance will be as close as possible to polynomially solvable and the results satisfies a prescribed accuracy (the difference between optimal and current solution). In this paper the DC algorithm is applied to determining exact or approximate global minima of supermodular functions. The working of the algorithm is illustrated by an instance of the Simple Plant Location (SPL) Problem. Computational results, obtained for the Quadratic Cost Partition Problem (QCP), show that the DC algorithm outperforms a branch-and-cut algorithm, not only for sparse graphs but also for nonsparse graphs (with density more than 40%), often with speeds 100 times faster.