Index: doc/Makefile.am
===================================================================
 doc/Makefile.am (revision 634)
+++ doc/Makefile.am (revision 710)
@@ 9,4 +9,5 @@
doc/mainpage.dox \
doc/migration.dox \
+ doc/min_cost_flow.dox \
doc/namedparam.dox \
doc/namespaces.dox \
Index: doc/groups.dox
===================================================================
 doc/groups.dox (revision 843)
+++ doc/groups.dox (revision 844)
@@ 139,14 +139,4 @@
/**
@defgroup semi_adaptors SemiAdaptor Classes for Graphs
@ingroup graphs
\brief Graph types between real graphs and graph adaptors.

This group contains some graph types between real graphs and graph adaptors.
These classes wrap graphs to give new functionality as the adaptors do it.
On the other hand they are not lightweight structures as the adaptors.
*/

/**
@defgroup maps Maps
@ingroup datas
@@ 316,4 +306,5 @@
minimum cut, which is the dual problem of maximum flow.
+
\ref Circulation is a preflow pushrelabel algorithm implemented directly
for finding feasible circulations, which is a somewhat different problem,
@@ 323,5 +314,5 @@
/**
@defgroup min_cost_flow Minimum Cost Flow Algorithms
+@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
@ingroup algs
@@ 329,78 +320,6 @@
This group contains the algorithms for finding minimum cost flows and
circulations.

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.
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
\f$upper: A\rightarrow\mathbf{Z}\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{Z}\f$ denotes the cost per unit flow
on the arcs and \f$sup: V\rightarrow\mathbf{Z}\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{Z}\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 lefthand 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}\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)Library of Efficient Models
+LEMON stands for Library for Efficient Modeling
and Optimization in Networks.
It is a C++ template
@@ 42,12 +41,8 @@
\subsection howtoread How to read the documentation
If you want to get a quick start and see the most important features then
take a look at our \ref quicktour
"Quick Tour to LEMON" which will guide you along.

If you already feel like using our library, see the
+If you would like to get to know the library, see
LEMON Tutorial.
If you know what you are looking for then try to find it under the
+If you know what you are looking for, then try to find it under the
Modules section.
Index: doc/min_cost_flow.dox
===================================================================
 doc/min_cost_flow.dox (revision 710)
+++ doc/min_cost_flow.dox (revision 710)
@@ 0,0 +1,153 @@
+/* * mode: C++; indenttabsmode: nil; *
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 20032009
+ * 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.
+
+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 lefthand 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)"less or equal" (LEQ) supply/demand constraints,
+instead of the "greater or equal" (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 nonnegative instead of nonpositive.
+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)=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$.
+
+*/
+}