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.