1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/min_cost_flow.dox Tue May 12 12:06:40 2009 +0200
1.3 @@ -0,0 +1,153 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +namespace lemon {
1.23 +
1.24 +/**
1.25 +\page min_cost_flow Minimum Cost Flow Problem
1.26 +
1.27 +\section mcf_def Definition (GEQ form)
1.28 +
1.29 +The \e minimum \e cost \e flow \e problem is to find a feasible flow of
1.30 +minimum total cost from a set of supply nodes to a set of demand nodes
1.31 +in a network with capacity constraints (lower and upper bounds)
1.32 +and arc costs.
1.33 +
1.34 +Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
1.35 +\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
1.36 +upper bounds for the flow values on the arcs, for which
1.37 +\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
1.38 +\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
1.39 +on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
1.40 +signed supply values of the nodes.
1.41 +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
1.42 +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
1.43 +\f$-sup(u)\f$ demand.
1.44 +A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
1.45 +of the following optimization problem.
1.46 +
1.47 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.48 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
1.49 + sup(u) \quad \forall u\in V \f]
1.50 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
1.51 +
1.52 +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
1.53 +zero or negative in order to have a feasible solution (since the sum
1.54 +of the expressions on the left-hand side of the inequalities is zero).
1.55 +It means that the total demand must be greater or equal to the total
1.56 +supply and all the supplies have to be carried out from the supply nodes,
1.57 +but there could be demands that are not satisfied.
1.58 +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
1.59 +constraints have to be satisfied with equality, i.e. all demands
1.60 +have to be satisfied and all supplies have to be used.
1.61 +
1.62 +
1.63 +\section mcf_algs Algorithms
1.64 +
1.65 +LEMON contains several algorithms for solving this problem, for more
1.66 +information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
1.67 +
1.68 +A feasible solution for this problem can be found using \ref Circulation.
1.69 +
1.70 +
1.71 +\section mcf_dual Dual Solution
1.72 +
1.73 +The dual solution of the minimum cost flow problem is represented by
1.74 +node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
1.75 +An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
1.76 +if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
1.77 +the following \e complementary \e slackness optimality conditions hold.
1.78 +
1.79 + - For all \f$uv\in A\f$ arcs:
1.80 + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
1.81 + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
1.82 + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
1.83 + - For all \f$u\in V\f$ nodes:
1.84 + - \f$\pi(u)<=0\f$;
1.85 + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
1.86 + then \f$\pi(u)=0\f$.
1.87 +
1.88 +Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
1.89 +\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
1.90 +\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
1.91 +
1.92 +All algorithms provide dual solution (node potentials), as well,
1.93 +if an optimal flow is found.
1.94 +
1.95 +
1.96 +\section mcf_eq Equality Form
1.97 +
1.98 +The above \ref mcf_def "definition" is actually more general than the
1.99 +usual formulation of the minimum cost flow problem, in which strict
1.100 +equalities are required in the supply/demand contraints.
1.101 +
1.102 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.103 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
1.104 + sup(u) \quad \forall u\in V \f]
1.105 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
1.106 +
1.107 +However if the sum of the supply values is zero, then these two problems
1.108 +are equivalent.
1.109 +The \ref min_cost_flow_algs "algorithms" in LEMON support the general
1.110 +form, so if you need the equality form, you have to ensure this additional
1.111 +contraint manually.
1.112 +
1.113 +
1.114 +\section mcf_leq Opposite Inequalites (LEQ Form)
1.115 +
1.116 +Another possible definition of the minimum cost flow problem is
1.117 +when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
1.118 +instead of the <em>"greater or equal"</em> (GEQ) constraints.
1.119 +
1.120 +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
1.121 +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
1.122 + sup(u) \quad \forall u\in V \f]
1.123 +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
1.124 +
1.125 +It means that the total demand must be less or equal to the
1.126 +total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
1.127 +positive) and all the demands have to be satisfied, but there
1.128 +could be supplies that are not carried out from the supply
1.129 +nodes.
1.130 +The equality form is also a special case of this form, of course.
1.131 +
1.132 +You could easily transform this case to the \ref mcf_def "GEQ form"
1.133 +of the problem by reversing the direction of the arcs and taking the
1.134 +negative of the supply values (e.g. using \ref ReverseDigraph and
1.135 +\ref NegMap adaptors).
1.136 +However \ref NetworkSimplex algorithm also supports this form directly
1.137 +for the sake of convenience.
1.138 +
1.139 +Note that the optimality conditions for this supply constraint type are
1.140 +slightly differ from the conditions that are discussed for the GEQ form,
1.141 +namely the potentials have to be non-negative instead of non-positive.
1.142 +An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
1.143 +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
1.144 +node potentials the following conditions hold.
1.145 +
1.146 + - For all \f$uv\in A\f$ arcs:
1.147 + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
1.148 + - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
1.149 + - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
1.150 + - For all \f$u\in V\f$ nodes:
1.151 + - \f$\pi(u)>=0\f$;
1.152 + - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
1.153 + then \f$\pi(u)=0\f$.
1.154 +
1.155 +*/
1.156 +}