doc/min_cost_flow.dox
 author Alpar Juttner Sun, 14 Mar 2010 09:13:04 +0100 changeset 865 d48d79b11f5b parent 755 134852d7fb0a parent 786 e20173729589 child 877 141f9c0db4a3 permissions -rw-r--r--
Replace figure at matching doc #348

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