350 |
350 |
351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of |
351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of |
352 minimum total cost from a set of supply nodes to a set of demand nodes |
352 minimum total cost from a set of supply nodes to a set of demand nodes |
353 in a network with capacity constraints (lower and upper bounds) |
353 in a network with capacity constraints (lower and upper bounds) |
354 and arc costs. |
354 and arc costs. |
355 Formally, let \f$G=(V,A)\f$ be a digraph, |
355 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$, |
356 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and |
356 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and |
357 upper bounds for the flow values on the arcs, for which |
357 upper bounds for the flow values on the arcs, for which |
358 \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. |
358 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, |
359 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow |
359 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow |
360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the |
360 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the |
361 signed supply values of the nodes. |
361 signed supply values of the nodes. |
362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ |
362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ |
363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with |
363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with |
364 \f$-sup(u)\f$ demand. |
364 \f$-sup(u)\f$ demand. |
365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution |
365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution |
366 of the following optimization problem. |
366 of the following optimization problem. |
367 |
367 |
368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] |
368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] |
369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq |
369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq |
370 sup(u) \quad \forall u\in V \f] |
370 sup(u) \quad \forall u\in V \f] |
402 are equivalent. So if you need the equality form, you have to ensure this |
402 are equivalent. So if you need the equality form, you have to ensure this |
403 additional contraint for the algorithms. |
403 additional contraint for the algorithms. |
404 |
404 |
405 The dual solution of the minimum cost flow problem is represented by node |
405 The dual solution of the minimum cost flow problem is represented by node |
406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. |
406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. |
407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem |
407 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem |
408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ |
408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ |
409 node potentials the following \e complementary \e slackness optimality |
409 node potentials the following \e complementary \e slackness optimality |
410 conditions hold. |
410 conditions hold. |
411 |
411 |
412 - For all \f$uv\in A\f$ arcs: |
412 - For all \f$uv\in A\f$ arcs: |
413 - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; |
413 - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; |
414 - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; |
414 - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; |
415 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. |
415 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. |
416 - For all \f$u\in V\f$: |
416 - For all \f$u\in V\f$ nodes: |
417 - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, |
417 - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, |
418 then \f$\pi(u)=0\f$. |
418 then \f$\pi(u)=0\f$. |
419 |
419 |
420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc |
420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc |
421 \f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e. |
421 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. |
422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] |
422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] |
423 |
423 |
424 All algorithms provide dual solution (node potentials) as well |
424 All algorithms provide dual solution (node potentials) as well, |
425 if an optimal flow is found. |
425 if an optimal flow is found. |
426 |
426 |
427 LEMON contains several algorithms for solving minimum cost flow problems. |
427 LEMON contains several algorithms for solving minimum cost flow problems. |
428 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
428 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
429 pivot strategies. |
429 pivot strategies. |