1 files changed, 153 insertions, 0 deletions
diff --git a/lemon/doc/min_cost_flow.dox b/lemon/doc/min_cost_flow.dox
new file mode 100644
index 0000000..ae8f044
--- /dev/null
+++ b/lemon/doc/min_cost_flow.dox
@@ -0,0 +1,153 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+namespace lemon {
+
+/**
+\page min_cost_flow Minimum Cost Flow Problem
+
+\section mcf_def Definition (GEQ form)
+
+The \e minimum \e cost \e flow \e 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 \ref amo93networkflows.
+
+Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
+\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
+upper bounds for the flow values on the arcs, for which
+\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
+\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
+on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
+signed supply values of the nodes.
+If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
+supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
+\f$-sup(u)\f$ demand.
+A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
+of the following optimization problem.
+
+\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
+    sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+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.
+
+
+\section mcf_algs Algorithms
+
+LEMON contains several algorithms for solving this problem, for more
+information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
+
+A feasible solution for this problem can be found using \ref Circulation.
+
+
+\section mcf_dual Dual Solution
+
+The dual solution of the minimum cost flow problem is represented by
+node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
+An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
+if and only if for some \f$\pi: V\rightarrow\mathbf{R}\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$ nodes:
+   - \f$\pi(u)\leq 0\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 potential function \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.
+
+
+\section mcf_eq Equality Form
+
+The above \ref mcf_def "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.
+
+\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
+    sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+However if the sum of the supply values is zero, then these two problems
+are equivalent.
+The \ref min_cost_flow_algs "algorithms" in LEMON support the general
+form, so if you need the equality form, you have to ensure this additional
+contraint manually.
+
+
+\section mcf_leq Opposite Inequalites (LEQ Form)
+
+Another possible definition of the minimum cost flow problem is
+when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
+instead of the <em>"greater or equal"</em> (GEQ) constraints.
+
+\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
+\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
+    sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+It means that the total demand must be less or equal to the
+total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
+positive) and all the demands have to be satisfied, but there
+could be supplies that are not carried out from the supply
+nodes.
+The equality form is also a special case of this form, of course.
+
+You could easily transform this case to the \ref mcf_def "GEQ form"
+of the problem 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.
+
+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 \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
+is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
+node potentials the following 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$ nodes:
+   - \f$\pi(u)\geq 0\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$.
+
+*/
+}