Minimum Cost Flow Algorithms

The same group on the Doxygen site.

group Minimum Cost Flow Algorithms

Algorithms for finding minimum cost flows and circulations.

This group contains the algorithms for finding minimum cost flows and circulations [1]. For more information about this problem and its dual solution, see: Minimum Cost Flow Problem.

LEMON contains several algorithms for this problem.

  • NetworkSimplex Primal Network Simplex algorithm with various pivot strategies [9], [26].

  • CostScaling Cost Scaling algorithm based on push/augment and relabel operations [18], [19], [2].

  • CapacityScaling Capacity Scaling algorithm based on the successive shortest path method [13].

  • CycleCanceling Cycle-Canceling algorithms, two of which are strongly polynomial [28], [17].

Besides an optimal flow, KBestExtremeFlows gives the K vertices of least cost of the polyhedron of the flows in order [30] (or, within a limit on the bases it expands, distinct vertices in order, or the optimal vertices and those one cycle of least reduced cost away from them), and KBestFlows the K integer flows of least cost in order [21], [29].

In general, NetworkSimplex and CostScaling are the most efficient implementations. NetworkSimplex is usually the fastest on relatively small graphs (up to several thousands of nodes) and on dense graphs, while CostScaling is typically more efficient on large graphs (e.g. hundreds of thousands of nodes or above), especially if they are sparse. However, other algorithms could be faster in special cases. For example, if the total supply and/or capacities are rather small, CapacityScaling is usually the fastest algorithm (without effective scaling).

The four algorithms take integer and floating-point data alike: with a floating-point type, the flows and the reduced costs are compared against tolerances relative to the largest supply or bound and to the largest cost. When an answer is not optimal, infeasibleCut() and unboundedCycle() give its certificate.

For more details about these implementations and for a comprehensive experimental study, see the paper [27]. It also compares these codes to other publicly available minimum cost flow solvers.

Classes

Class

Description

CapacityScaling

Implementation of the Capacity Scaling algorithm for finding a minimum cost flow.

CostScaling

Implementation of the Cost Scaling algorithm for finding a minimum cost flow.

CycleCanceling

Implementation of cycle-canceling algorithms for finding a minimum cost flow.

KBestExtremeFlows

The K best extreme flows of a minimum cost flow problem.

KBestFlows

The K best integer flows of a minimum cost flow problem.

NetworkSimplex

Implementation of the primal Network Simplex algorithm for finding a minimum cost flow.

Other classes of its headers

Class

Description

CapacityScalingDefaultTraits

Default traits class of CapacityScaling algorithm.

CostScalingDefaultTraits

Default traits class of CostScaling algorithm.