doc/min_cost_flow.dox
 branch 1.1 changeset 1258 bdfc038f364c parent 710 8b0df68370a4
equal inserted replaced
0:c60ebd4b1c89 5:abd516e6bfaa
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2011
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    79    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\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:
    80  - For all \f$u\in V\f$ nodes:
    81    - \f$\pi(u)<=0\f$;
    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$,
    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$.
    83      then \f$\pi(u)=0\f$.
    84
    84
    85 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    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.
    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]
    87 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
    88
    88
    89 All algorithms provide dual solution (node potentials), as well,
    89 All algorithms provide dual solution (node potentials), as well,
   117 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
   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
   118 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
   119     sup(u) \quad \forall u\in V \f]
   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]
   120 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
   121
   121
   122 It means that the total demand must be less or equal to the
   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
   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
   124 positive) and all the demands have to be satisfied, but there
   125 could be supplies that are not carried out from the supply
   125 could be supplies that are not carried out from the supply
   126 nodes.
   126 nodes.
   127 The equality form is also a special case of this form, of course.
   127 The equality form is also a special case of this form, of course.