The Data-Correcting Algorithm for the Minimization of Supermodular Functions

Boris Goldengorin, Gerard Sierksma, Gert A. Tijssen and Michael Tso
Additional contact information
Boris Goldengorin: Department of Econometrics and Operations Research, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands
Gerard Sierksma: Department of Econometrics and Operations Research, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands
Gert A. Tijssen: Department of Econometrics and Operations Research, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands
Michael Tso: Department of Mathematics, University of Manchester, Institute of Science and Technology, UMIST, Manchester, United Kingdom

Management Science, 1999, vol. 45, issue 11, 1539-1551

Abstract: 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.

Keywords: data-correcting algorithm; supermodular function; global minimum (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.45.11.1539 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:45:y:1999:i:11:p:1539-1551

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().