digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and

 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the

 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the

 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]

 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]

 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)

 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

     \qquad \forall v\in V\setminus\{s,t\} \f]

     \quad \forall u\in V\setminus\{s,t\} \f]

 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]

 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

 This group describes the algorithms for finding minimum cost flows and

 This group contains the algorithms for finding minimum cost flows and

 in a network with capacity constraints and arc costs.

 in a network with capacity constraints (lower and upper bounds)

 and arc costs.

 upper bounds for the flow values on the arcs,

 upper bounds for the flow values on the arcs, for which

 \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.

 on the arcs, and

 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the

 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values

 signed supply values of the nodes.

 of the nodes.

 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of

 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

 the following optimization problem.

 \f$-sup(u)\f$ demand.

 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution

 \f[ \min\sum_{a\in A} f(a) cost(a) \f]

 of the following optimization problem.

 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =

     supply(v) \qquad \forall v\in V \f]

 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]

 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq

     sup(u) \quad \forall u\in V \f]

 LEMON contains several algorithms for solving minimum cost flow problems:

 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

  - \ref CycleCanceling Cycle-canceling algorithms.

  - \ref CapacityScaling Successive shortest path algorithm with optional

 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

 zero or negative in order to have a feasible solution (since the sum

 of the expressions on the left-hand side of the inequalities is zero).

 It means that the total demand must be greater or equal to the total

 supply and all the supplies have to be carried out from the supply nodes,

 but there could be demands that are not satisfied.

 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

 constraints have to be satisfied with equality, i.e. all demands

 have to be satisfied and all supplies have to be used.

 If you need the opposite inequalities in the supply/demand constraints

 (i.e. the total demand is less than the total supply and all the demands

 have to be satisfied while there could be supplies that are not used),

 then you could easily transform the problem to the above form by reversing

 the direction of the arcs and taking the negative of the supply values

 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).

 However \ref NetworkSimplex algorithm also supports this form directly

 for the sake of convenience.

 A feasible solution for this problem can be found using \ref Circulation.

 Note that the above formulation is actually more general than the usual

 definition of the minimum cost flow problem, in which strict equalities

 are required in the supply/demand contraints, i.e.

 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =

     sup(u) \quad \forall u\in V. \f]

 However if the sum of the supply values is zero, then these two problems

 are equivalent. So if you need the equality form, you have to ensure this

 additional contraint for the algorithms.

 The dual solution of the minimum cost flow problem is represented by node 

 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.

 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem

 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$

 node potentials the following \e complementary \e slackness optimality

 conditions hold.

  - For all \f$uv\in A\f$ arcs:

    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

  - For all \f$u\in V\f$:

    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

      then \f$\pi(u)=0\f$.

 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

 \f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.

 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

 All algorithms provide dual solution (node potentials) as well

 if an optimal flow is found.

 LEMON contains several algorithms for solving minimum cost flow problems.

  - \ref NetworkSimplex Primal Network Simplex algorithm with various

    pivot strategies.

  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on

    cost scaling.

  - \ref CapacityScaling Successive Shortest %Path algorithm with optional

  - \ref CostScaling Push-relabel and augment-relabel algorithms based on

  - \ref CancelAndTighten The Cancel and Tighten algorithm.

    cost scaling.

  - \ref CycleCanceling Cycle-Canceling algorithms.

  - \ref NetworkSimplex Primal network simplex algorithm with various

    pivot strategies.

 Most of these implementations support the general inequality form of the

 minimum cost flow problem, but CancelAndTighten and CycleCanceling

 only support the equality form due to the primal method they use.

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