COIN-OR::LEMON - Graph Library

Changeset 663:8b0df68370a4 in lemon-1.2 for doc


Ignore:
Timestamp:
05/12/09 12:06:40 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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.
Location:
doc
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • doc/Makefile.am

    r587 r663  
    99        doc/mainpage.dox \
    1010        doc/migration.dox \
     11        doc/min_cost_flow.dox \
    1112        doc/named-param.dox \
    1213        doc/namespaces.dox \
  • doc/groups.dox

    r660 r663  
    336336
    337337/**
    338 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     338@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    339339@ingroup algs
    340340
     
    342342
    343343This group contains the algorithms for finding minimum cost flows and
    344 circulations.
    345 
    346 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    347 minimum total cost from a set of supply nodes to a set of demand nodes
    348 in a network with capacity constraints (lower and upper bounds)
    349 and arc costs.
    350 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
    351 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
    352 upper bounds for the flow values on the arcs, for which
    353 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
    354 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
    355 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
    356 signed supply values of the nodes.
    357 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    358 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    359 \f$-sup(u)\f$ demand.
    360 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
    361 of the following optimization problem.
    362 
    363 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
    364 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
    365     sup(u) \quad \forall u\in V \f]
    366 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    367 
    368 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    369 zero or negative in order to have a feasible solution (since the sum
    370 of the expressions on the left-hand side of the inequalities is zero).
    371 It means that the total demand must be greater or equal to the total
    372 supply and all the supplies have to be carried out from the supply nodes,
    373 but there could be demands that are not satisfied.
    374 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
    375 constraints have to be satisfied with equality, i.e. all demands
    376 have to be satisfied and all supplies have to be used.
    377 
    378 If you need the opposite inequalities in the supply/demand constraints
    379 (i.e. the total demand is less than the total supply and all the demands
    380 have to be satisfied while there could be supplies that are not used),
    381 then you could easily transform the problem to the above form by reversing
    382 the direction of the arcs and taking the negative of the supply values
    383 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    384 However \ref NetworkSimplex algorithm also supports this form directly
    385 for the sake of convenience.
    386 
    387 A feasible solution for this problem can be found using \ref Circulation.
    388 
    389 Note that the above formulation is actually more general than the usual
    390 definition of the minimum cost flow problem, in which strict equalities
    391 are required in the supply/demand contraints, i.e.
    392 
    393 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
    394     sup(u) \quad \forall u\in V. \f]
    395 
    396 However if the sum of the supply values is zero, then these two problems
    397 are equivalent. So if you need the equality form, you have to ensure this
    398 additional contraint for the algorithms.
    399 
    400 The dual solution of the minimum cost flow problem is represented by node
    401 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
    402 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
    403 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
    404 node potentials the following \e complementary \e slackness optimality
    405 conditions hold.
    406 
    407  - For all \f$uv\in A\f$ arcs:
    408    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
    409    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    410    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    411  - For all \f$u\in V\f$ nodes:
    412    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    413      then \f$\pi(u)=0\f$.
    414  
    415 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    416 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
    417 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
    418 
    419 All algorithms provide dual solution (node potentials) as well,
    420 if an optimal flow is found.
    421 
    422 LEMON contains several algorithms for solving minimum cost flow problems.
     344circulations. For more information about this problem and its dual
     345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     346
     347LEMON contains several algorithms for this problem.
    423348 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    424349   pivot strategies.
     
    429354 - \ref CancelAndTighten The Cancel and Tighten algorithm.
    430355 - \ref CycleCanceling Cycle-Canceling algorithms.
    431 
    432 Most of these implementations support the general inequality form of the
    433 minimum cost flow problem, but CancelAndTighten and CycleCanceling
    434 only support the equality form due to the primal method they use.
    435356
    436357In general NetworkSimplex is the most efficient implementation,
Note: See TracChangeset for help on using the changeset viewer.