doc/min_cost_flow.dox
 author Peter Kovacs Tue, 12 May 2009 12:06:40 +0200 changeset 710 8b0df68370a4 child 802 134852d7fb0a child 833 e20173729589 child 1081 f1398882a928 permissions -rw-r--r--
Fix the GEQ/LEQ handling in NetworkSimplex + improve doc (#291)

- Fix the optimality conditions for the GEQ/LEQ form.
- Fix the initialization of the algortihm. It ensures correct
solutions and it is much faster for the inequality forms.
- Fix the pivot rules to search all the arcs that have to be
allowed to get in the basis.
- Better block size for the Block Search pivot rule.
- Improve documentation of the problem and move it to a
separate page.
 kpeter@710  1 /* -*- mode: C++; indent-tabs-mode: nil; -*-  kpeter@710  2  *  kpeter@710  3  * This file is a part of LEMON, a generic C++ optimization library.  kpeter@710  4  *  kpeter@710  5  * Copyright (C) 2003-2009  kpeter@710  6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport  kpeter@710  7  * (Egervary Research Group on Combinatorial Optimization, EGRES).  kpeter@710  8  *  kpeter@710  9  * Permission to use, modify and distribute this software is granted  kpeter@710  10  * provided that this copyright notice appears in all copies. For  kpeter@710  11  * precise terms see the accompanying LICENSE file.  kpeter@710  12  *  kpeter@710  13  * This software is provided "AS IS" with no warranty of any kind,  kpeter@710  14  * express or implied, and with no claim as to its suitability for any  kpeter@710  15  * purpose.  kpeter@710  16  *  kpeter@710  17  */  kpeter@710  18 kpeter@710  19 namespace lemon {  kpeter@710  20 kpeter@710  21 /**  kpeter@710  22 \page min_cost_flow Minimum Cost Flow Problem  kpeter@710  23 kpeter@710  24 \section mcf_def Definition (GEQ form)  kpeter@710  25 kpeter@710  26 The \e minimum \e cost \e flow \e problem is to find a feasible flow of  kpeter@710  27 minimum total cost from a set of supply nodes to a set of demand nodes  kpeter@710  28 in a network with capacity constraints (lower and upper bounds)  kpeter@710  29 and arc costs.  kpeter@710  30 kpeter@710  31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,  kpeter@710  32 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and  kpeter@710  33 upper bounds for the flow values on the arcs, for which  kpeter@710  34 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,  kpeter@710  35 \f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow  kpeter@710  36 on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the  kpeter@710  37 signed supply values of the nodes.  kpeter@710  38 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$  kpeter@710  39 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with  kpeter@710  40 \f$-sup(u)\f$ demand.  kpeter@710  41 A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution  kpeter@710  42 of the following optimization problem.  kpeter@710  43 kpeter@710  44 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]  kpeter@710  45 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq  kpeter@710  46  sup(u) \quad \forall u\in V \f]  kpeter@710  47 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]  kpeter@710  48 kpeter@710  49 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be  kpeter@710  50 zero or negative in order to have a feasible solution (since the sum  kpeter@710  51 of the expressions on the left-hand side of the inequalities is zero).  kpeter@710  52 It means that the total demand must be greater or equal to the total  kpeter@710  53 supply and all the supplies have to be carried out from the supply nodes,  kpeter@710  54 but there could be demands that are not satisfied.  kpeter@710  55 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand  kpeter@710  56 constraints have to be satisfied with equality, i.e. all demands  kpeter@710  57 have to be satisfied and all supplies have to be used.  kpeter@710  58 kpeter@710  59 kpeter@710  60 \section mcf_algs Algorithms  kpeter@710  61 kpeter@710  62 LEMON contains several algorithms for solving this problem, for more  kpeter@710  63 information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".  kpeter@710  64 kpeter@710  65 A feasible solution for this problem can be found using \ref Circulation.  kpeter@710  66 kpeter@710  67 kpeter@710  68 \section mcf_dual Dual Solution  kpeter@710  69 kpeter@710  70 The dual solution of the minimum cost flow problem is represented by  kpeter@710  71 node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.  kpeter@710  72 An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal  kpeter@710  73 if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials  kpeter@710  74 the following \e complementary \e slackness optimality conditions hold.  kpeter@710  75 kpeter@710  76  - For all \f$uv\in A\f$ arcs:  kpeter@710  77  - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;  kpeter@710  78  - if \f$lower(uv)"less or equal" (LEQ) supply/demand constraints,  kpeter@710  115 instead of the "greater or equal" (GEQ) constraints.  kpeter@710  116 kpeter@710  117 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]  kpeter@710  118 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq  kpeter@710  119  sup(u) \quad \forall u\in V \f]  kpeter@710  120 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]  kpeter@710  121 kpeter@710  122 It means that the total demand must be less or equal to the  kpeter@710  123 total supply (i.e. \f$\sum_{u\in V} sup(u)\f$must be zero or  kpeter@710  124 positive) and all the demands have to be satisfied, but there  kpeter@710  125 could be supplies that are not carried out from the supply  kpeter@710  126 nodes.  kpeter@710  127 The equality form is also a special case of this form, of course.  kpeter@710  128 kpeter@710  129 You could easily transform this case to the \ref mcf_def "GEQ form"  kpeter@710  130 of the problem by reversing the direction of the arcs and taking the  kpeter@710  131 negative of the supply values (e.g. using \ref ReverseDigraph and  kpeter@710  132 \ref NegMap adaptors).  kpeter@710  133 However \ref NetworkSimplex algorithm also supports this form directly  kpeter@710  134 for the sake of convenience.  kpeter@710  135 kpeter@710  136 Note that the optimality conditions for this supply constraint type are  kpeter@710  137 slightly differ from the conditions that are discussed for the GEQ form,  kpeter@710  138 namely the potentials have to be non-negative instead of non-positive.  kpeter@710  139 An \f$f: A\rightarrow\mathbf{R}\f$feasible solution of this problem  kpeter@710  140 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ kpeter@710  141 node potentials the following conditions hold.  kpeter@710  142 kpeter@710  143  - For all \f$uv\in A\f$arcs:  kpeter@710  144  - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;  kpeter@710  145  - if \f$lower(uv)=0\f$;  kpeter@710  149  - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,  kpeter@710  150  then \f$\pi(u)=0\f\$.  kpeter@710  151 kpeter@710  152 */  kpeter@710  153 }