Loading...
Searching...
No Matches
Minimum Cost Flow Algorithms
Algorithms

## Detailed Description

This group contains the algorithms for finding minimum cost flows and circulations [amo93networkflows]. 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 [dantzig63linearprog], [kellyoneill91netsimplex].
- CostScaling Cost Scaling algorithm based on push/augment and relabel operations [goldberg90approximation], [goldberg97efficient], [bunnagel98efficient].
- CapacityScaling Capacity Scaling algorithm based on the successive shortest path method [edmondskarp72theoretical].
- CycleCanceling Cycle-Canceling algorithms, two of which are strongly polynomial [klein67primal], [goldberg89cyclecanceling].

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 [KiralyKovacs12MCF]. 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...

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