The Data-Correcting Algorithm for the Minimization of Supermodular Functions
The Data-Correcting (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 result 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.
Volume (Year): 45 (1999)
Issue (Month): 11 (November)
|Contact details of provider:|| Postal: |
Web page: http://www.informs.org/
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:45:y:1999:i:11:p:1539-1551. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)
If references are entirely missing, you can add them using this form.