An experimental implementation of the dual cancel and tighten algorithm for minimum-cost network flow
S. McCormick, Lei Liu · DIMACS series in discrete mathematics and theoretical computer science · 1993
We present an exerimental implementation of a variant of the Dual Cancel and Tighten (DCT) algorithm for Minimum-Cost Network Flow (MCNF). The algorithm maintains a dual feasible π and a primal x necessarily satisfying only conservation. It then seeks to minimize the largest horizontal violation of complementary slackness on the kilter diagram of any arc. The variant uses a heuristic to find a tight or nearly tight flow for the current dual solution at each iteration. We report on the computational results that led us to abandon the original form of the algorithm, on our experiments to find a fast variant of it, and extensive computational results for the variant that we settled on. We find that this algorithm is an order of magnitude (or more) slower than Kennington and Helgason’s NETFLO network simplex code.