COIN-OR::LEMON - Graph Library

Changeset 611:85cb3aa71cce in lemon-1.2 for doc


Ignore:
Timestamp:
04/21/09 16:18:54 (15 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
612:0c8e5c688440, 613:b1811c363299, 619:ec817dfc2cb7
Parents:
600:0ba8dfce7259 (diff), 610:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge and fix

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r590 r611  
    318318The \e maximum \e flow \e problem is to find a flow of maximum value between
    319319a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     320digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321321\f$s, t \in V\f$ source and target nodes.
    322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     322A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323323following optimization problem.
    324324
    325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    327     \qquad \forall v\in V\setminus\{s,t\} \f]
    328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
     325\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     326\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     327    \quad \forall u\in V\setminus\{s,t\} \f]
     328\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    329329
    330330LEMON contains several algorithms for solving maximum flow problems:
     
    351351The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    352352minimum total cost from a set of supply nodes to a set of demand nodes
    353 in a network with capacity constraints and arc costs.
     353in a network with capacity constraints (lower and upper bounds)
     354and arc costs.
    354355Formally, let \f$G=(V,A)\f$ be a digraph,
    355356\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    356 upper bounds for the flow values on the arcs,
     357upper 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$.
    357359\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    358 on the arcs, and
    359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    360 of the nodes.
    361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    362 the following optimization problem.
    363 
    364 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    366     supply(v) \qquad \forall v\in V \f]
    367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    368 
    369 LEMON contains several algorithms for solving minimum cost flow problems:
    370  - \ref CycleCanceling Cycle-canceling algorithms.
    371  - \ref CapacityScaling Successive shortest path algorithm with optional
     360on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
     361signed supply values of the nodes.
     362If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
     363supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
     364\f$-sup(u)\f$ demand.
     365A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
     366of the following optimization problem.
     367
     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
     370    sup(u) \quad \forall u\in V \f]
     371\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
     372
     373The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
     374zero or negative in order to have a feasible solution (since the sum
     375of the expressions on the left-hand side of the inequalities is zero).
     376It means that the total demand must be greater or equal to the total
     377supply and all the supplies have to be carried out from the supply nodes,
     378but there could be demands that are not satisfied.
     379If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
     380constraints have to be satisfied with equality, i.e. all demands
     381have to be satisfied and all supplies have to be used.
     382
     383If you need the opposite inequalities in the supply/demand constraints
     384(i.e. the total demand is less than the total supply and all the demands
     385have to be satisfied while there could be supplies that are not used),
     386then you could easily transform the problem to the above form by reversing
     387the direction of the arcs and taking the negative of the supply values
     388(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     389However \ref NetworkSimplex algorithm also supports this form directly
     390for the sake of convenience.
     391
     392A feasible solution for this problem can be found using \ref Circulation.
     393
     394Note that the above formulation is actually more general than the usual
     395definition of the minimum cost flow problem, in which strict equalities
     396are required in the supply/demand contraints, i.e.
     397
     398\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
     399    sup(u) \quad \forall u\in V. \f]
     400
     401However if the sum of the supply values is zero, then these two problems
     402are equivalent. So if you need the equality form, you have to ensure this
     403additional contraint for the algorithms.
     404
     405The dual solution of the minimum cost flow problem is represented by node
     406potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
     407An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
     408is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
     409node potentials the following \e complementary \e slackness optimality
     410conditions hold.
     411
     412 - For all \f$uv\in A\f$ arcs:
     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$;
     415   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
     416 - For all \f$u\in V\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$.
     419 
     420Here \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.
     422\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
     423
     424All algorithms provide dual solution (node potentials) as well
     425if an optimal flow is found.
     426
     427LEMON contains several algorithms for solving minimum cost flow problems.
     428 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     429   pivot strategies.
     430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     431   cost scaling.
     432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    372433   capacity scaling.
    373  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    374    cost scaling.
    375  - \ref NetworkSimplex Primal network simplex algorithm with various
    376    pivot strategies.
     434 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     435 - \ref CycleCanceling Cycle-Canceling algorithms.
     436
     437Most of these implementations support the general inequality form of the
     438minimum cost flow problem, but CancelAndTighten and CycleCanceling
     439only support the equality form due to the primal method they use.
     440
     441In general NetworkSimplex is the most efficient implementation,
     442but in special cases other algorithms could be faster.
     443For example, if the total supply and/or capacities are rather small,
     444CapacityScaling is usually the fastest algorithm (without effective scaling).
    377445*/
    378446
  • doc/groups.dox

    r609 r611  
    2121/**
    2222@defgroup datas Data Structures
    23 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2424*/
    2525
     
    143143\brief Graph types between real graphs and graph adaptors.
    144144
    145 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    146146These classes wrap graphs to give new functionality as the adaptors do it.
    147147On the other hand they are not light-weight structures as the adaptors.
     
    153153\brief Map structures implemented in LEMON.
    154154
    155 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    156156
    157157LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    166166\brief Special graph-related maps.
    167167
    168 This group describes maps that are specifically designed to assign
     168This group contains maps that are specifically designed to assign
    169169values to the nodes and arcs/edges of graphs.
    170170
     
    178178\brief Tools to create new maps from existing ones
    179179
    180 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    181181maps from other maps.
    182182
     
    241241\brief Two dimensional data storages implemented in LEMON.
    242242
    243 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    244244*/
    245245
     
    249249\brief %Path structures implemented in LEMON.
    250250
    251 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    252252
    253253LEMON provides flexible data structures to work with paths.
     
    265265\brief Auxiliary data structures implemented in LEMON.
    266266
    267 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    268268order to make it easier to implement combinatorial algorithms.
    269269*/
     
    271271/**
    272272@defgroup algs Algorithms
    273 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    274274implemented in LEMON.
    275275
    276 This group describes the several algorithms
     276This group contains the several algorithms
    277277implemented in LEMON.
    278278*/
     
    283283\brief Common graph search algorithms.
    284284
    285 This group describes the common graph search algorithms, namely
     285This group contains the common graph search algorithms, namely
    286286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    287287*/
     
    292292\brief Algorithms for finding shortest paths.
    293293
    294 This group describes the algorithms for finding shortest paths in digraphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
    295295
    296296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    313313\brief Algorithms for finding maximum flows.
    314314
    315 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    316316feasible circulations.
    317317
     
    451451\brief Algorithms for finding minimum cut in graphs.
    452452
    453 This group describes the algorithms for finding minimum cut in graphs.
     453This group contains the algorithms for finding minimum cut in graphs.
    454454
    455455The \e minimum \e cut \e problem is to find a non-empty and non-complete
     
    468468- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    469469  calculating minimum cut in undirected graphs.
    470 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     470- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    471471  all-pairs minimum cut in undirected graphs.
    472472
     
    476476
    477477/**
    478 @defgroup graph_prop Connectivity and Other Graph Properties
     478@defgroup graph_properties Connectivity and Other Graph Properties
    479479@ingroup algs
    480480\brief Algorithms for discovering the graph properties
    481481
    482 This group describes the algorithms for discovering the graph properties
     482This group contains the algorithms for discovering the graph properties
    483483like connectivity, bipartiteness, euler property, simplicity etc.
    484484
     
    492492\brief Algorithms for planarity checking, embedding and drawing
    493493
    494 This group describes the algorithms for planarity checking,
     494This group contains the algorithms for planarity checking,
    495495embedding and drawing.
    496496
     
    504504\brief Algorithms for finding matchings in graphs and bipartite graphs.
    505505
    506 This group contains algorithm objects and functions to calculate
     506This group contains the algorithms for calculating
    507507matchings in graphs and bipartite graphs. The general matching problem is
    508 finding a subset of the arcs which does not shares common endpoints.
     508finding a subset of the edges for which each node has at most one incident
     509edge.
    509510
    510511There are several different algorithms for calculate matchings in
     
    543544\brief Algorithms for finding a minimum cost spanning tree in a graph.
    544545
    545 This group describes the algorithms for finding a minimum cost spanning
     546This group contains the algorithms for finding a minimum cost spanning
    546547tree in a graph.
    547548*/
     
    552553\brief Auxiliary algorithms implemented in LEMON.
    553554
    554 This group describes some algorithms implemented in LEMON
     555This group contains some algorithms implemented in LEMON
    555556in order to make it easier to implement complex algorithms.
    556557*/
     
    561562\brief Approximation algorithms.
    562563
    563 This group describes the approximation and heuristic algorithms
     564This group contains the approximation and heuristic algorithms
    564565implemented in LEMON.
    565566*/
     
    567568/**
    568569@defgroup gen_opt_group General Optimization Tools
    569 \brief This group describes some general optimization frameworks
     570\brief This group contains some general optimization frameworks
    570571implemented in LEMON.
    571572
    572 This group describes some general optimization frameworks
     573This group contains some general optimization frameworks
    573574implemented in LEMON.
    574575*/
     
    579580\brief Lp and Mip solver interfaces for LEMON.
    580581
    581 This group describes Lp and Mip solver interfaces for LEMON. The
     582This group contains Lp and Mip solver interfaces for LEMON. The
    582583various LP solvers could be used in the same manner with this
    583584interface.
     
    598599\brief Metaheuristics for LEMON library.
    599600
    600 This group describes some metaheuristic optimization tools.
     601This group contains some metaheuristic optimization tools.
    601602*/
    602603
     
    613614\brief Simple basic graph utilities.
    614615
    615 This group describes some simple basic graph utilities.
     616This group contains some simple basic graph utilities.
    616617*/
    617618
     
    621622\brief Tools for development, debugging and testing.
    622623
    623 This group describes several useful tools for development,
     624This group contains several useful tools for development,
    624625debugging and testing.
    625626*/
     
    630631\brief Simple tools for measuring the performance of algorithms.
    631632
    632 This group describes simple tools for measuring the performance
     633This group contains simple tools for measuring the performance
    633634of algorithms.
    634635*/
     
    639640\brief Exceptions defined in LEMON.
    640641
    641 This group describes the exceptions defined in LEMON.
     642This group contains the exceptions defined in LEMON.
    642643*/
    643644
     
    646647\brief Graph Input-Output methods
    647648
    648 This group describes the tools for importing and exporting graphs
     649This group contains the tools for importing and exporting graphs
    649650and graph related data. Now it supports the \ref lgf-format
    650651"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    657658\brief Reading and writing LEMON Graph Format.
    658659
    659 This group describes methods for reading and writing
     660This group contains methods for reading and writing
    660661\ref lgf-format "LEMON Graph Format".
    661662*/
     
    666667\brief General \c EPS drawer and graph exporter
    667668
    668 This group describes general \c EPS drawing methods and special
     669This group contains general \c EPS drawing methods and special
    669670graph exporting tools.
    670671*/
     
    690691\brief Skeleton classes and concept checking classes
    691692
    692 This group describes the data/algorithm skeletons and concept checking
     693This group contains the data/algorithm skeletons and concept checking
    693694classes implemented in LEMON.
    694695
     
    720721\brief Skeleton and concept checking classes for graph structures
    721722
    722 This group describes the skeletons and concept checking classes of LEMON's
     723This group contains the skeletons and concept checking classes of LEMON's
    723724graph structures and helper classes used to implement these.
    724725*/
     
    729730\brief Skeleton and concept checking classes for maps
    730731
    731 This group describes the skeletons and concept checking classes of maps.
     732This group contains the skeletons and concept checking classes of maps.
    732733*/
    733734
     
    740741the \c demo subdirectory of the source tree.
    741742
    742 It order to compile them, use <tt>--enable-demo</tt> configure option when
    743 build the library.
     743In order to compile them, use the <tt>make demo</tt> or the
     744<tt>make check</tt> commands.
    744745*/
    745746
Note: See TracChangeset for help on using the changeset viewer.