doc/min_cost_flow.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 23 Aug 2009 11:09:22 +0200
changeset 735 853fcddcf282
child 755 134852d7fb0a
child 786 e20173729589
permissions -rw-r--r--
Doc improvements, fixes and unifications for graphs (#311)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon {
    20 
    21 /**
    22 \page min_cost_flow Minimum Cost Flow Problem
    23 
    24 \section mcf_def Definition (GEQ form)
    25 
    26 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    27 minimum total cost from a set of supply nodes to a set of demand nodes
    28 in a network with capacity constraints (lower and upper bounds)
    29 and arc costs.
    30 
    31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
    32 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
    33 upper bounds for the flow values on the arcs, for which
    34 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
    35 \f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
    36 on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
    37 signed supply values of the nodes.
    38 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    39 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    40 \f$-sup(u)\f$ demand.
    41 A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
    42 of the following optimization problem.
    43 
    44 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
    45 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
    46     sup(u) \quad \forall u\in V \f]
    47 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    48 
    49 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    50 zero or negative in order to have a feasible solution (since the sum
    51 of the expressions on the left-hand side of the inequalities is zero).
    52 It means that the total demand must be greater or equal to the total
    53 supply and all the supplies have to be carried out from the supply nodes,
    54 but there could be demands that are not satisfied.
    55 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
    56 constraints have to be satisfied with equality, i.e. all demands
    57 have to be satisfied and all supplies have to be used.
    58 
    59 
    60 \section mcf_algs Algorithms
    61 
    62 LEMON contains several algorithms for solving this problem, for more
    63 information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
    64 
    65 A feasible solution for this problem can be found using \ref Circulation.
    66 
    67 
    68 \section mcf_dual Dual Solution
    69 
    70 The dual solution of the minimum cost flow problem is represented by
    71 node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
    72 An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
    73 if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
    74 the following \e complementary \e slackness optimality conditions hold.
    75 
    76  - For all \f$uv\in A\f$ arcs:
    77    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
    78    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    79    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    80  - For all \f$u\in V\f$ nodes:
    81    - \f$\pi(u)<=0\f$;
    82    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    83      then \f$\pi(u)=0\f$.
    84  
    85 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    86 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
    87 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
    88 
    89 All algorithms provide dual solution (node potentials), as well,
    90 if an optimal flow is found.
    91 
    92 
    93 \section mcf_eq Equality Form
    94 
    95 The above \ref mcf_def "definition" is actually more general than the
    96 usual formulation of the minimum cost flow problem, in which strict
    97 equalities are required in the supply/demand contraints.
    98 
    99 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
   100 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
   101     sup(u) \quad \forall u\in V \f]
   102 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
   103 
   104 However if the sum of the supply values is zero, then these two problems
   105 are equivalent.
   106 The \ref min_cost_flow_algs "algorithms" in LEMON support the general
   107 form, so if you need the equality form, you have to ensure this additional
   108 contraint manually.
   109 
   110 
   111 \section mcf_leq Opposite Inequalites (LEQ Form)
   112 
   113 Another possible definition of the minimum cost flow problem is
   114 when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
   115 instead of the <em>"greater or equal"</em> (GEQ) constraints.
   116 
   117 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
   118 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
   119     sup(u) \quad \forall u\in V \f]
   120 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
   121 
   122 It means that the total demand must be less or equal to the 
   123 total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
   124 positive) and all the demands have to be satisfied, but there
   125 could be supplies that are not carried out from the supply
   126 nodes.
   127 The equality form is also a special case of this form, of course.
   128 
   129 You could easily transform this case to the \ref mcf_def "GEQ form"
   130 of the problem by reversing the direction of the arcs and taking the
   131 negative of the supply values (e.g. using \ref ReverseDigraph and
   132 \ref NegMap adaptors).
   133 However \ref NetworkSimplex algorithm also supports this form directly
   134 for the sake of convenience.
   135 
   136 Note that the optimality conditions for this supply constraint type are
   137 slightly differ from the conditions that are discussed for the GEQ form,
   138 namely the potentials have to be non-negative instead of non-positive.
   139 An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
   140 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
   141 node potentials the following conditions hold.
   142 
   143  - For all \f$uv\in A\f$ arcs:
   144    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
   145    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
   146    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
   147  - For all \f$u\in V\f$ nodes:
   148    - \f$\pi(u)>=0\f$;
   149    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
   150      then \f$\pi(u)=0\f$.
   151 
   152 */
   153 }