doc/min_cost_flow.dox
 changeset 1259 8b2d4e5d96e4 parent 835 c92296660262 child 1164 f63ba40a60f4
equal inserted replaced
3:d69f1d82f728 4:035fff31f3f0
     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-2010
     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)\leq 0\f$;
    81    - \f$\pi(u)\leq 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.