All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Classes | Files
Minimum Cost Flow Algorithms
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.

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.