Minimum Cost Flow Algorithms

Detailed Description

This group contains the algorithms for finding minimum cost flows and circulations [AMO93]. 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 [Dan63], [KO91].
• CostScaling Cost Scaling algorithm based on push/augment and relabel operations [GT90], [Gol97], [BKV98].
• CapacityScaling Capacity Scaling algorithm based on the successive shortest path method [EK72].
• CycleCanceling Cycle-Canceling algorithms, two of which are strongly polynomial [Kle67], [GT89].

In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. For example, if the total supply and/or capacities are rather small, CapacityScaling is usually the fastest algorithm (without effective scaling).

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.