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: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
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.