My Project
|
The minimum cost flow problem is to find a feasible flow of minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) and arc costs [amo93networkflows].
Formally, let
The sum of the supply values, i.e.
LEMON contains several algorithms for solving this problem, for more information see Minimum Cost Flow Algorithms.
A feasible solution for this problem can be found using Circulation.
The dual solution of the minimum cost flow problem is represented by node potentials
Here
All algorithms provide dual solution (node potentials), as well, if an optimal flow is found.
The above definition is actually more general than the usual formulation of the minimum cost flow problem, in which strict equalities are required in the supply/demand contraints.
However, if the sum of the supply values is zero, then these two problems are equivalent. The algorithms in LEMON support the general form, so if you need the equality form, you have to ensure this additional contraint manually.
Another possible definition of the minimum cost flow problem is when there are "less or equal" (LEQ) supply/demand constraints, instead of the "greater or equal" (GEQ) constraints.
It means that the total demand must be less or equal to the total supply (i.e.
You could easily transform this case to the GEQ form of the problem by reversing the direction of the arcs and taking the negative of the supply values (e.g. using ReverseDigraph and NegMap adaptors). However NetworkSimplex algorithm also supports this form directly for the sake of convenience.
Note that the optimality conditions for this supply constraint type are slightly differ from the conditions that are discussed for the GEQ form, namely the potentials have to be non-negative instead of non-positive. An