The data-correcting algorithm for the minimization of supermodular functions

The data-correcting algorithm for the minimization of supermodular functions

0.00 Avg rating0 Votes
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: , , ,
Keywords: optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.