1.1 --- a/doc/groups.dox Sat Oct 10 08:15:07 2009 +0200
1.2 +++ b/doc/groups.dox Sat Oct 10 08:18:46 2009 +0200
1.3 @@ -316,7 +316,8 @@
1.4 \brief Common graph search algorithms.
1.5
1.6 This group contains the common graph search algorithms, namely
1.7 -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
1.8 +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
1.9 +\ref clrs01algorithms.
1.10 */
1.11
1.12 /**
1.13 @@ -324,7 +325,8 @@
1.14 @ingroup algs
1.15 \brief Algorithms for finding shortest paths.
1.16
1.17 -This group contains the algorithms for finding shortest paths in digraphs.
1.18 +This group contains the algorithms for finding shortest paths in digraphs
1.19 +\ref clrs01algorithms.
1.20
1.21 - \ref Dijkstra algorithm for finding shortest paths from a source node
1.22 when all arc lengths are non-negative.
1.23 @@ -346,7 +348,7 @@
1.24 \brief Algorithms for finding minimum cost spanning trees and arborescences.
1.25
1.26 This group contains the algorithms for finding minimum cost spanning
1.27 -trees and arborescences.
1.28 +trees and arborescences \ref clrs01algorithms.
1.29 */
1.30
1.31 /**
1.32 @@ -355,7 +357,7 @@
1.33 \brief Algorithms for finding maximum flows.
1.34
1.35 This group contains the algorithms for finding maximum flows and
1.36 -feasible circulations.
1.37 +feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
1.38
1.39 The \e maximum \e flow \e problem is to find a flow of maximum value between
1.40 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.41 @@ -370,12 +372,16 @@
1.42 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
1.43
1.44 LEMON contains several algorithms for solving maximum flow problems:
1.45 -- \ref EdmondsKarp Edmonds-Karp algorithm.
1.46 -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
1.47 -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
1.48 -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
1.49 +- \ref EdmondsKarp Edmonds-Karp algorithm
1.50 + \ref edmondskarp72theoretical.
1.51 +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
1.52 + \ref goldberg88newapproach.
1.53 +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
1.54 + \ref dinic70algorithm, \ref sleator83dynamic.
1.55 +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
1.56 + \ref goldberg88newapproach, \ref sleator83dynamic.
1.57
1.58 -In most cases the \ref Preflow "Preflow" algorithm provides the
1.59 +In most cases the \ref Preflow algorithm provides the
1.60 fastest method for computing a maximum flow. All implementations
1.61 also provide functions to query the minimum cut, which is the dual
1.62 problem of maximum flow.
1.63 @@ -393,18 +399,22 @@
1.64 \brief Algorithms for finding minimum cost flows and circulations.
1.65
1.66 This group contains the algorithms for finding minimum cost flows and
1.67 -circulations. For more information about this problem and its dual
1.68 -solution see \ref min_cost_flow "Minimum Cost Flow Problem".
1.69 +circulations \ref amo93networkflows. For more information about this
1.70 +problem and its dual solution, see \ref min_cost_flow
1.71 +"Minimum Cost Flow Problem".
1.72
1.73 LEMON contains several algorithms for this problem.
1.74 - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.75 - pivot strategies.
1.76 + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
1.77 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.78 - cost scaling.
1.79 + cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
1.80 + \ref bunnagel98efficient.
1.81 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
1.82 - capacity scaling.
1.83 - - \ref CancelAndTighten The Cancel and Tighten algorithm.
1.84 - - \ref CycleCanceling Cycle-Canceling algorithms.
1.85 + capacity scaling \ref edmondskarp72theoretical.
1.86 + - \ref CancelAndTighten The Cancel and Tighten algorithm
1.87 + \ref goldberg89cyclecanceling.
1.88 + - \ref CycleCanceling Cycle-Canceling algorithms
1.89 + \ref klein67primal, \ref goldberg89cyclecanceling.
1.90
1.91 In general NetworkSimplex is the most efficient implementation,
1.92 but in special cases other algorithms could be faster.
1.93 @@ -534,13 +544,16 @@
1.94 */
1.95
1.96 /**
1.97 -@defgroup lp_group Lp and Mip Solvers
1.98 +@defgroup lp_group LP and MIP Solvers
1.99 @ingroup gen_opt_group
1.100 -\brief Lp and Mip solver interfaces for LEMON.
1.101 +\brief LP and MIP solver interfaces for LEMON.
1.102
1.103 -This group contains Lp and Mip solver interfaces for LEMON. The
1.104 -various LP solvers could be used in the same manner with this
1.105 -interface.
1.106 +This group contains LP and MIP solver interfaces for LEMON.
1.107 +Various LP solvers could be used in the same manner with this
1.108 +high-level interface.
1.109 +
1.110 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.111 +\ref cplex, \ref soplex.
1.112 */
1.113
1.114 /**
2.1 --- a/doc/mainpage.dox Sat Oct 10 08:15:07 2009 +0200
2.2 +++ b/doc/mainpage.dox Sat Oct 10 08:18:46 2009 +0200
2.3 @@ -21,14 +21,11 @@
2.4
2.5 \section intro Introduction
2.6
2.7 -\subsection whatis What is LEMON
2.8 -
2.9 -LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
2.10 -and <b>O</b>ptimization in <b>N</b>etworks.
2.11 -It is a C++ template
2.12 -library aimed at combinatorial optimization tasks which
2.13 -often involve in working
2.14 -with graphs.
2.15 +<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
2.16 +and <b>O</b>ptimization in <b>N</b>etworks</i>.
2.17 +It is a C++ template library providing efficient implementation of common
2.18 +data structures and algorithms with focus on combinatorial optimization
2.19 +problems in graphs and networks.
2.20
2.21 <b>
2.22 LEMON is an <a class="el" href="http://opensource.org/">open source</a>
2.23 @@ -38,7 +35,16 @@
2.24 \ref license "license terms".
2.25 </b>
2.26
2.27 -\subsection howtoread How to read the documentation
2.28 +The project is maintained by the
2.29 +<a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on
2.30 +Combinatorial Optimization</a> \ref egres
2.31 +at the Operations Research Department of the
2.32 +<a href="http://www.elte.hu/">Eötvös Loránd University,
2.33 +Budapest</a>, Hungary.
2.34 +LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
2.35 +initiative \ref coinor.
2.36 +
2.37 +\section howtoread How to Read the Documentation
2.38
2.39 If you would like to get to know the library, see
2.40 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
3.1 --- a/doc/min_cost_flow.dox Sat Oct 10 08:15:07 2009 +0200
3.2 +++ b/doc/min_cost_flow.dox Sat Oct 10 08:18:46 2009 +0200
3.3 @@ -26,7 +26,7 @@
3.4 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
3.5 minimum total cost from a set of supply nodes to a set of demand nodes
3.6 in a network with capacity constraints (lower and upper bounds)
3.7 -and arc costs.
3.8 +and arc costs \ref amo93networkflows.
3.9
3.10 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
3.11 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
4.1 --- a/doc/references.bib Sat Oct 10 08:15:07 2009 +0200
4.2 +++ b/doc/references.bib Sat Oct 10 08:18:46 2009 +0200
4.3 @@ -150,15 +150,25 @@
4.4
4.5 %%%%% Maximum flow algorithms %%%%%
4.6
4.7 -@inproceedings{goldberg86newapproach,
4.8 +@article{edmondskarp72theoretical,
4.9 + author = {Jack Edmonds and Richard M. Karp},
4.10 + title = {Theoretical improvements in algorithmic efficiency
4.11 + for network flow problems},
4.12 + journal = {Journal of the ACM},
4.13 + year = 1972,
4.14 + volume = 19,
4.15 + number = 2,
4.16 + pages = {248-264}
4.17 +}
4.18 +
4.19 +@article{goldberg88newapproach,
4.20 author = {Andrew V. Goldberg and Robert E. Tarjan},
4.21 title = {A new approach to the maximum flow problem},
4.22 - booktitle = {STOC '86: Proceedings of the Eighteenth Annual ACM
4.23 - Symposium on Theory of Computing},
4.24 - year = 1986,
4.25 - publisher = {ACM Press},
4.26 - address = {New York, NY},
4.27 - pages = {136-146}
4.28 + journal = {Journal of the ACM},
4.29 + year = 1988,
4.30 + volume = 35,
4.31 + number = 4,
4.32 + pages = {921-940}
4.33 }
4.34
4.35 @article{dinic70algorithm,
4.36 @@ -229,42 +239,18 @@
4.37 pages = {205-220}
4.38 }
4.39
4.40 -@inproceedings{goldberg88cyclecanceling,
4.41 +@article{goldberg89cyclecanceling,
4.42 author = {Andrew V. Goldberg and Robert E. Tarjan},
4.43 title = {Finding minimum-cost circulations by canceling
4.44 negative cycles},
4.45 - booktitle = {STOC '88: Proceedings of the Twentieth Annual ACM
4.46 - Symposium on Theory of Computing},
4.47 - year = 1988,
4.48 - publisher = {ACM Press},
4.49 - address = {New York, NY},
4.50 - pages = {388-397}
4.51 + journal = {Journal of the ACM},
4.52 + year = 1989,
4.53 + volume = 36,
4.54 + number = 4,
4.55 + pages = {873-886}
4.56 }
4.57
4.58 -@article{edmondskarp72theoretical,
4.59 - author = {Jack Edmonds and Richard M. Karp},
4.60 - title = {Theoretical improvements in algorithmic efficiency
4.61 - for network flow problems},
4.62 - journal = {Journal of the ACM},
4.63 - year = 1972,
4.64 - volume = 19,
4.65 - number = 2,
4.66 - pages = {248-264}
4.67 -}
4.68 -
4.69 -@inproceedings{goldberg87approximation,
4.70 - author = {Andrew V. Goldberg and Robert E. Tarjan},
4.71 - title = {Solving minimum-cost flow problems by successive
4.72 - approximation},
4.73 - booktitle = {STOC '87: Proceedings of the Nineteenth Annual ACM
4.74 - Symposium on Theory of Computing},
4.75 - year = 1987,
4.76 - publisher = {ACM Press},
4.77 - address = {New York, NY},
4.78 - pages = {7-18}
4.79 -}
4.80 -
4.81 -@article{goldberg90finding,
4.82 +@article{goldberg90approximation,
4.83 author = {Andrew V. Goldberg and Robert E. Tarjan},
4.84 title = {Finding Minimum-Cost Circulations by Successive
4.85 Approximation},
4.86 @@ -297,6 +283,13 @@
4.87 pages = {157-174}
4.88 }
4.89
4.90 +@book{dantzig63linearprog,
4.91 + author = {George B. Dantzig},
4.92 + title = {Linear Programming and Extensions},
4.93 + publisher = {Princeton University Press},
4.94 + year = 1963
4.95 +}
4.96 +
4.97 @mastersthesis{kellyoneill91netsimplex,
4.98 author = {Damian J. Kelly and Garrett M. O'Neill},
4.99 title = {The Minimum Cost Flow Problem and The Network
4.100 @@ -306,25 +299,3 @@
4.101 year = 1991,
4.102 month = sep,
4.103 }
4.104 -
4.105 -@techreport{lobel96networksimplex,
4.106 - author = {Andreas L{\"o}bel},
4.107 - title = {Solving large-scale real-world minimum-cost flow
4.108 - problems by a network simplex method},
4.109 - institution = {Konrad-Zuse-Zentrum fur Informationstechnik Berlin
4.110 - ({ZIB})},
4.111 - address = {Berlin, Germany},
4.112 - year = 1996,
4.113 - number = {SC 96-7}
4.114 -}
4.115 -
4.116 -@article{frangioni06computational,
4.117 - author = {Antonio Frangioni and Antonio Manca},
4.118 - title = {A Computational Study of Cost Reoptimization for
4.119 - Min-Cost Flow Problems},
4.120 - journal = {INFORMS Journal On Computing},
4.121 - year = 2006,
4.122 - volume = 18,
4.123 - number = 1,
4.124 - pages = {61-70}
4.125 -}
5.1 --- a/lemon/network_simplex.h Sat Oct 10 08:15:07 2009 +0200
5.2 +++ b/lemon/network_simplex.h Sat Oct 10 08:18:46 2009 +0200
5.3 @@ -40,7 +40,9 @@
5.4 /// for finding a \ref min_cost_flow "minimum cost flow".
5.5 ///
5.6 /// \ref NetworkSimplex implements the primal Network Simplex algorithm
5.7 - /// for finding a \ref min_cost_flow "minimum cost flow".
5.8 + /// for finding a \ref min_cost_flow "minimum cost flow"
5.9 + /// \ref amo93networkflows, \ref dantzig63linearprog,
5.10 + /// \ref kellyoneill91netsimplex.
5.11 /// This algorithm is a specialized version of the linear programming
5.12 /// simplex method directly for the minimum cost flow problem.
5.13 /// It is one of the most efficient solution methods.
6.1 --- a/lemon/preflow.h Sat Oct 10 08:15:07 2009 +0200
6.2 +++ b/lemon/preflow.h Sat Oct 10 08:18:46 2009 +0200
6.3 @@ -102,7 +102,8 @@
6.4 ///
6.5 /// This class provides an implementation of Goldberg-Tarjan's \e preflow
6.6 /// \e push-relabel algorithm producing a \ref max_flow
6.7 - /// "flow of maximum value" in a digraph.
6.8 + /// "flow of maximum value" in a digraph \ref clrs01algorithms,
6.9 + /// \ref amo93networkflows, \ref goldberg88newapproach.
6.10 /// The preflow algorithms are the fastest known maximum
6.11 /// flow algorithms. The current implementation uses a mixture of the
6.12 /// \e "highest label" and the \e "bound decrease" heuristics.