doc/min_cost_flow.dox
 changeset 956 141f9c0db4a3 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  *
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.