Minimum Cost Flow Algorithms

Detailed Description

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 [8], [23].
• 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 [25], [17].

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).

These classes are intended to be used with integer-valued input data (capacities, supply values, and costs), except for CapacityScaling, which is capable of handling real-valued arc costs (other numerical data are required to be integer).

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

Classes
class	CapacityScaling< GR, V, C, TR >
	Implementation of the Capacity Scaling algorithm for finding a minimum cost flow. More...
class	CostScaling< GR, V, C, TR >
	Implementation of the Cost Scaling algorithm for finding a minimum cost flow. More...
class	CycleCanceling< GR, V, C >
	Implementation of cycle-canceling algorithms for finding a minimum cost flow. More...
class	NetworkSimplex< GR, V, C >
	Implementation of the primal Network Simplex algorithm for finding a minimum cost flow. More...
struct	CapacityScaling< GR, V, C, TR >::SetHeap< T >
	Named parameter for setting Heap type. More...
struct	CostScaling< GR, V, C, TR >::SetLargeCost< T >
	Named parameter for setting LargeCost type. More...

Files
file	capacity_scaling.h
	Capacity Scaling algorithm for finding a minimum cost flow.
file	cost_scaling.h
	Cost scaling algorithm for finding a minimum cost flow.
file	cycle_canceling.h
	Cycle-canceling algorithms for finding a minimum cost flow.
file	network_simplex.h
	Network Simplex algorithm for finding a minimum cost flow.