[663] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
[877] | 5 | * Copyright (C) 2003-2010 |
---|
[663] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | namespace lemon { |
---|
| 20 | |
---|
| 21 | /** |
---|
| 22 | \page min_cost_flow Minimum Cost Flow Problem |
---|
| 23 | |
---|
| 24 | \section mcf_def Definition (GEQ form) |
---|
| 25 | |
---|
| 26 | The \e minimum \e cost \e flow \e problem is to find a feasible flow of |
---|
| 27 | minimum total cost from a set of supply nodes to a set of demand nodes |
---|
| 28 | in a network with capacity constraints (lower and upper bounds) |
---|
[755] | 29 | and arc costs \ref amo93networkflows. |
---|
[663] | 30 | |
---|
| 31 | Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, |
---|
| 32 | \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and |
---|
| 33 | upper bounds for the flow values on the arcs, for which |
---|
| 34 | \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, |
---|
| 35 | \f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow |
---|
| 36 | on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the |
---|
| 37 | signed supply values of the nodes. |
---|
| 38 | If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ |
---|
| 39 | supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with |
---|
| 40 | \f$-sup(u)\f$ demand. |
---|
| 41 | A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution |
---|
| 42 | of the following optimization problem. |
---|
| 43 | |
---|
| 44 | \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] |
---|
| 45 | \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq |
---|
| 46 | sup(u) \quad \forall u\in V \f] |
---|
| 47 | \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] |
---|
| 48 | |
---|
| 49 | The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be |
---|
| 50 | zero or negative in order to have a feasible solution (since the sum |
---|
| 51 | of the expressions on the left-hand side of the inequalities is zero). |
---|
| 52 | It means that the total demand must be greater or equal to the total |
---|
| 53 | supply and all the supplies have to be carried out from the supply nodes, |
---|
| 54 | but there could be demands that are not satisfied. |
---|
| 55 | If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand |
---|
| 56 | constraints have to be satisfied with equality, i.e. all demands |
---|
| 57 | have to be satisfied and all supplies have to be used. |
---|
| 58 | |
---|
| 59 | |
---|
| 60 | \section mcf_algs Algorithms |
---|
| 61 | |
---|
| 62 | LEMON contains several algorithms for solving this problem, for more |
---|
| 63 | information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms". |
---|
| 64 | |
---|
| 65 | A feasible solution for this problem can be found using \ref Circulation. |
---|
| 66 | |
---|
| 67 | |
---|
| 68 | \section mcf_dual Dual Solution |
---|
| 69 | |
---|
| 70 | The dual solution of the minimum cost flow problem is represented by |
---|
| 71 | node potentials \f$\pi: V\rightarrow\mathbf{R}\f$. |
---|
| 72 | An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal |
---|
| 73 | if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials |
---|
| 74 | the following \e complementary \e slackness optimality conditions hold. |
---|
| 75 | |
---|
| 76 | - For all \f$uv\in A\f$ arcs: |
---|
| 77 | - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; |
---|
| 78 | - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\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: |
---|
[786] | 81 | - \f$\pi(u)\leq 0\f$; |
---|
[663] | 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$. |
---|
[877] | 84 | |
---|
[663] | 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. |
---|
| 87 | \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] |
---|
| 88 | |
---|
| 89 | All algorithms provide dual solution (node potentials), as well, |
---|
| 90 | if an optimal flow is found. |
---|
| 91 | |
---|
| 92 | |
---|
| 93 | \section mcf_eq Equality Form |
---|
| 94 | |
---|
| 95 | The above \ref mcf_def "definition" is actually more general than the |
---|
| 96 | usual formulation of the minimum cost flow problem, in which strict |
---|
| 97 | equalities are required in the supply/demand contraints. |
---|
| 98 | |
---|
| 99 | \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] |
---|
| 100 | \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = |
---|
| 101 | sup(u) \quad \forall u\in V \f] |
---|
| 102 | \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] |
---|
| 103 | |
---|
| 104 | However if the sum of the supply values is zero, then these two problems |
---|
| 105 | are equivalent. |
---|
| 106 | The \ref min_cost_flow_algs "algorithms" in LEMON support the general |
---|
| 107 | form, so if you need the equality form, you have to ensure this additional |
---|
| 108 | contraint manually. |
---|
| 109 | |
---|
| 110 | |
---|
| 111 | \section mcf_leq Opposite Inequalites (LEQ Form) |
---|
| 112 | |
---|
| 113 | Another possible definition of the minimum cost flow problem is |
---|
| 114 | when there are <em>"less or equal"</em> (LEQ) supply/demand constraints, |
---|
| 115 | instead of the <em>"greater or equal"</em> (GEQ) constraints. |
---|
| 116 | |
---|
| 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 |
---|
| 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] |
---|
| 121 | |
---|
[877] | 122 | It means that the total demand must be less or equal to the |
---|
[663] | 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 |
---|
| 125 | could be supplies that are not carried out from the supply |
---|
| 126 | nodes. |
---|
| 127 | The equality form is also a special case of this form, of course. |
---|
| 128 | |
---|
| 129 | You could easily transform this case to the \ref mcf_def "GEQ form" |
---|
| 130 | of the problem by reversing the direction of the arcs and taking the |
---|
| 131 | negative of the supply values (e.g. using \ref ReverseDigraph and |
---|
| 132 | \ref NegMap adaptors). |
---|
| 133 | However \ref NetworkSimplex algorithm also supports this form directly |
---|
| 134 | for the sake of convenience. |
---|
| 135 | |
---|
| 136 | Note that the optimality conditions for this supply constraint type are |
---|
| 137 | slightly differ from the conditions that are discussed for the GEQ form, |
---|
| 138 | namely the potentials have to be non-negative instead of non-positive. |
---|
| 139 | An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem |
---|
| 140 | is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ |
---|
| 141 | node potentials the following conditions hold. |
---|
| 142 | |
---|
| 143 | - For all \f$uv\in A\f$ arcs: |
---|
| 144 | - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; |
---|
| 145 | - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; |
---|
| 146 | - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. |
---|
| 147 | - For all \f$u\in V\f$ nodes: |
---|
[786] | 148 | - \f$\pi(u)\geq 0\f$; |
---|
[663] | 149 | - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, |
---|
| 150 | then \f$\pi(u)=0\f$. |
---|
| 151 | |
---|
| 152 | */ |
---|
| 153 | } |
---|