COIN-OR::LEMON - Graph Library

Changeset 802:134852d7fb0a in lemon


Ignore:
Timestamp:
10/10/09 08:18:46 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Insert citations into the doc (#184)

  • Add general citations to modules.
  • Add specific citations for max flow and min cost flow algorithms.
  • Add citations for the supported LP and MIP solvers.
  • Extend the main page.
  • Replace inproceedings entries with the journal versions.
  • Add a new bibtex entry about network simplex.
  • Remove unwanted entries.
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r789 r802  
    317317
    318318This group contains the common graph search algorithms, namely
    319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\ref clrs01algorithms.
    320321*/
    321322
     
    325326\brief Algorithms for finding shortest paths.
    326327
    327 This group contains the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
    328330
    329331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    347349
    348350This group contains the algorithms for finding minimum cost spanning
    349 trees and arborescences.
     351trees and arborescences \ref clrs01algorithms.
    350352*/
    351353
     
    356358
    357359This group contains the algorithms for finding maximum flows and
    358 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    359361
    360362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    371373
    372374LEMON contains several algorithms for solving maximum flow problems:
    373 - \ref EdmondsKarp Edmonds-Karp algorithm.
    374 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    375 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    376 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    377 
    378 In most cases the \ref Preflow "Preflow" algorithm provides the
     375- \ref EdmondsKarp Edmonds-Karp algorithm
     376  \ref edmondskarp72theoretical.
     377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     378  \ref goldberg88newapproach.
     379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     380  \ref dinic70algorithm, \ref sleator83dynamic.
     381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     382  \ref goldberg88newapproach, \ref sleator83dynamic.
     383
     384In most cases the \ref Preflow algorithm provides the
    379385fastest method for computing a maximum flow. All implementations
    380386also provide functions to query the minimum cut, which is the dual
     
    394400
    395401This group contains the algorithms for finding minimum cost flows and
    396 circulations. For more information about this problem and its dual
    397 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
    398405
    399406LEMON contains several algorithms for this problem.
    400407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    401    pivot strategies.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    402409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    403    cost scaling.
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
    404412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    405    capacity scaling.
    406  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    407  - \ref CycleCanceling Cycle-Canceling algorithms.
     413   capacity scaling \ref edmondskarp72theoretical.
     414 - \ref CancelAndTighten The Cancel and Tighten algorithm
     415   \ref goldberg89cyclecanceling.
     416 - \ref CycleCanceling Cycle-Canceling algorithms
     417   \ref klein67primal, \ref goldberg89cyclecanceling.
    408418
    409419In general NetworkSimplex is the most efficient implementation,
     
    535545
    536546/**
    537 @defgroup lp_group Lp and Mip Solvers
     547@defgroup lp_group LP and MIP Solvers
    538548@ingroup gen_opt_group
    539 \brief Lp and Mip solver interfaces for LEMON.
    540 
    541 This group contains Lp and Mip solver interfaces for LEMON. The
    542 various LP solvers could be used in the same manner with this
    543 interface.
     549\brief LP and MIP solver interfaces for LEMON.
     550
     551This group contains LP and MIP solver interfaces for LEMON.
     552Various LP solvers could be used in the same manner with this
     553high-level interface.
     554
     555The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     556\ref cplex, \ref soplex.
    544557*/
    545558
  • doc/mainpage.dox

    r705 r802  
    2222\section intro Introduction
    2323
    24 \subsection whatis What is LEMON
    25 
    26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    27 and <b>O</b>ptimization in <b>N</b>etworks.
    28 It is a C++ template
    29 library aimed at combinatorial optimization tasks which
    30 often involve in working
    31 with graphs.
     24<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     25and <b>O</b>ptimization in <b>N</b>etworks</i>.
     26It is a C++ template library providing efficient implementation of common
     27data structures and algorithms with focus on combinatorial optimization
     28problems in graphs and networks.
    3229
    3330<b>
     
    3936</b>
    4037
    41 \subsection howtoread How to read the documentation
     38The project is maintained by the
     39<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
     40Combinatorial Optimization</a> \ref egres
     41at the Operations Research Department of the
     42<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
     43Budapest</a>, Hungary.
     44LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
     45initiative \ref coinor.
     46
     47\section howtoread How to Read the Documentation
    4248
    4349If you would like to get to know the library, see
  • doc/min_cost_flow.dox

    r710 r802  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs.
     29and arc costs \ref amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • doc/references.bib

    r801 r802  
    151151%%%%% Maximum flow algorithms %%%%%
    152152
    153 @inproceedings{goldberg86newapproach,
     153@article{edmondskarp72theoretical,
     154  author =       {Jack Edmonds and Richard M. Karp},
     155  title =        {Theoretical improvements in algorithmic efficiency
     156                  for network flow problems},
     157  journal =      {Journal of the ACM},
     158  year =         1972,
     159  volume =       19,
     160  number =       2,
     161  pages =        {248-264}
     162}
     163
     164@article{goldberg88newapproach,
    154165  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    155166  title =        {A new approach to the maximum flow problem},
    156   booktitle =    {STOC '86: Proceedings of the Eighteenth Annual ACM
    157                   Symposium on Theory of Computing},
    158   year =         1986,
    159   publisher =    {ACM Press},
    160   address =      {New York, NY},
    161   pages =        {136-146}
     167  journal =      {Journal of the ACM},
     168  year =         1988,
     169  volume =       35,
     170  number =       4,
     171  pages =        {921-940}
    162172}
    163173
     
    230240}
    231241
    232 @inproceedings{goldberg88cyclecanceling,
     242@article{goldberg89cyclecanceling,
    233243  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    234244  title =        {Finding minimum-cost circulations by canceling
    235245                  negative cycles},
    236   booktitle =    {STOC '88: Proceedings of the Twentieth Annual ACM
    237                   Symposium on Theory of Computing},
    238   year =         1988,
    239   publisher =    {ACM Press},
    240   address =      {New York, NY},
    241   pages =        {388-397}
    242 }
    243 
    244 @article{edmondskarp72theoretical,
    245   author =       {Jack Edmonds and Richard M. Karp},
    246   title =        {Theoretical improvements in algorithmic efficiency
    247                   for network flow problems},
    248246  journal =      {Journal of the ACM},
    249   year =         1972,
    250   volume =       19,
    251   number =       2,
    252   pages =        {248-264}
    253 }
    254 
    255 @inproceedings{goldberg87approximation,
    256   author =       {Andrew V. Goldberg and Robert E. Tarjan},
    257   title =        {Solving minimum-cost flow problems by successive
    258                   approximation},
    259   booktitle =    {STOC '87: Proceedings of the Nineteenth Annual ACM
    260                   Symposium on Theory of Computing},
    261   year =         1987,
    262   publisher =    {ACM Press},
    263   address =      {New York, NY},
    264   pages =        {7-18}
    265 }
    266 
    267 @article{goldberg90finding,
     247  year =         1989,
     248  volume =       36,
     249  number =       4,
     250  pages =        {873-886}
     251}
     252
     253@article{goldberg90approximation,
    268254  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    269255  title =        {Finding Minimum-Cost Circulations by Successive
     
    298284}
    299285
     286@book{dantzig63linearprog,
     287  author =       {George B. Dantzig},
     288  title =        {Linear Programming and Extensions},
     289  publisher =    {Princeton University Press},
     290  year =         1963
     291}
     292
    300293@mastersthesis{kellyoneill91netsimplex,
    301294  author =       {Damian J. Kelly and Garrett M. O'Neill},
     
    307300  month =        sep,
    308301}
    309 
    310 @techreport{lobel96networksimplex,
    311   author =       {Andreas L{\"o}bel},
    312   title =        {Solving large-scale real-world minimum-cost flow
    313                   problems by a network simplex method},
    314   institution =  {Konrad-Zuse-Zentrum fur Informationstechnik Berlin
    315                   ({ZIB})},
    316   address =      {Berlin, Germany},
    317   year =         1996,
    318   number =       {SC 96-7}
    319 }
    320 
    321 @article{frangioni06computational,
    322   author =       {Antonio Frangioni and Antonio Manca},
    323   title =        {A Computational Study of Cost Reoptimization for
    324                   Min-Cost Flow Problems},
    325   journal =      {INFORMS Journal On Computing},
    326   year =         2006,
    327   volume =       18,
    328   number =       1,
    329   pages =        {61-70}
    330 }
  • lemon/network_simplex.h

    r777 r802  
    4141  ///
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    43   /// for finding a \ref min_cost_flow "minimum cost flow".
     43  /// for finding a \ref min_cost_flow "minimum cost flow"
     44  /// \ref amo93networkflows, \ref dantzig63linearprog,
     45  /// \ref kellyoneill91netsimplex.
    4446  /// This algorithm is a specialized version of the linear programming
    4547  /// simplex method directly for the minimum cost flow problem.
  • lemon/preflow.h

    r762 r802  
    103103  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    104104  /// \e push-relabel algorithm producing a \ref max_flow
    105   /// "flow of maximum value" in a digraph.
     105  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
     106  /// \ref amo93networkflows, \ref goldberg88newapproach.
    106107  /// The preflow algorithms are the fastest known maximum
    107108  /// flow algorithms. The current implementation uses a mixture of the
Note: See TracChangeset for help on using the changeset viewer.