abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Minimum Cost Flow Algorithms

Algorithms for finding minimum cost flows and circulations. 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  k_best_extreme_flows.h
file  k_best_flows.h
file  network_simplex.h
 Network Simplex algorithm for finding a minimum cost flow.

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  KBestExtremeFlows< GR , V , C >
 The K best extreme flows of a minimum cost flow problem. More...
class  KBestFlows< GR , V , C >
 The K best integer flows of a minimum cost flow problem. More...
class  NetworkSimplex< GR , V , C >
 Implementation of the primal Network Simplex algorithm for finding a minimum cost flow. More...

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.

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.