diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -316,7 +316,8 @@ \brief Common graph search algorithms. This group contains the common graph search algorithms, namely -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS). +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS) +\ref clrs01algorithms. */ /** @@ -324,7 +325,8 @@ @ingroup algs \brief Algorithms for finding shortest paths. -This group contains the algorithms for finding shortest paths in digraphs. +This group contains the algorithms for finding shortest paths in digraphs +\ref clrs01algorithms. - \ref Dijkstra algorithm for finding shortest paths from a source node when all arc lengths are non-negative. @@ -346,7 +348,7 @@ \brief Algorithms for finding minimum cost spanning trees and arborescences. This group contains the algorithms for finding minimum cost spanning -trees and arborescences. +trees and arborescences \ref clrs01algorithms. */ /** @@ -355,7 +357,7 @@ \brief Algorithms for finding maximum flows. This group contains the algorithms for finding maximum flows and -feasible circulations. +feasible circulations \ref clrs01algorithms, \ref amo93networkflows. The \e maximum \e flow \e problem is to find a flow of maximum value between a single source and a single target. Formally, there is a \f$G=(V,A)\f$ @@ -370,12 +372,16 @@ \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] LEMON contains several algorithms for solving maximum flow problems: -- \ref EdmondsKarp Edmonds-Karp algorithm. -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. +- \ref EdmondsKarp Edmonds-Karp algorithm + \ref edmondskarp72theoretical. +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm + \ref goldberg88newapproach. +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees + \ref dinic70algorithm, \ref sleator83dynamic. +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees + \ref goldberg88newapproach, \ref sleator83dynamic. -In most cases the \ref Preflow "Preflow" algorithm provides the +In most cases the \ref Preflow algorithm provides the fastest method for computing a maximum flow. All implementations also provide functions to query the minimum cut, which is the dual problem of maximum flow. @@ -393,18 +399,22 @@ \brief Algorithms for finding minimum cost flows and circulations. This group contains the algorithms for finding minimum cost flows and -circulations. For more information about this problem and its dual -solution see \ref min_cost_flow "Minimum Cost Flow Problem". +circulations \ref amo93networkflows. For more information about this +problem and its dual solution, see \ref min_cost_flow +"Minimum Cost Flow Problem". LEMON contains several algorithms for this problem. - \ref NetworkSimplex Primal Network Simplex algorithm with various - pivot strategies. + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on - cost scaling. + cost scaling \ref goldberg90approximation, \ref goldberg97efficient, + \ref bunnagel98efficient. - \ref CapacityScaling Successive Shortest %Path algorithm with optional - capacity scaling. - - \ref CancelAndTighten The Cancel and Tighten algorithm. - - \ref CycleCanceling Cycle-Canceling algorithms. + capacity scaling \ref edmondskarp72theoretical. + - \ref CancelAndTighten The Cancel and Tighten algorithm + \ref goldberg89cyclecanceling. + - \ref CycleCanceling Cycle-Canceling algorithms + \ref klein67primal, \ref goldberg89cyclecanceling. In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. @@ -534,13 +544,16 @@ */ /** -@defgroup lp_group Lp and Mip Solvers +@defgroup lp_group LP and MIP Solvers @ingroup gen_opt_group -\brief Lp and Mip solver interfaces for LEMON. +\brief LP and MIP solver interfaces for LEMON. -This group contains Lp and Mip solver interfaces for LEMON. The -various LP solvers could be used in the same manner with this -interface. +This group contains LP and MIP solver interfaces for LEMON. +Various LP solvers could be used in the same manner with this +high-level interface. + +The currently supported solvers are \ref glpk, \ref clp, \ref cbc, +\ref cplex, \ref soplex. */ /** diff --git a/doc/mainpage.dox b/doc/mainpage.dox --- a/doc/mainpage.dox +++ b/doc/mainpage.dox @@ -21,14 +21,11 @@ \section intro Introduction -\subsection whatis What is LEMON - -LEMON stands for Library for Efficient Modeling -and Optimization in Networks. -It is a C++ template -library aimed at combinatorial optimization tasks which -often involve in working -with graphs. +LEMON stands for Library for Efficient Modeling +and Optimization in Networks. +It is a C++ template library providing efficient implementation of common +data structures and algorithms with focus on combinatorial optimization +problems in graphs and networks. LEMON is an open source @@ -38,7 +35,16 @@ \ref license "license terms". -\subsection howtoread How to read the documentation +The project is maintained by the +Egerváry Research Group on +Combinatorial Optimization \ref egres +at the Operations Research Department of the +Eötvös Loránd University, +Budapest, Hungary. +LEMON is also a member of the COIN-OR +initiative \ref coinor. + +\section howtoread How to Read the Documentation If you would like to get to know the library, see LEMON Tutorial. diff --git a/doc/min_cost_flow.dox b/doc/min_cost_flow.dox --- a/doc/min_cost_flow.dox +++ b/doc/min_cost_flow.dox @@ -26,7 +26,7 @@ The \e minimum \e cost \e flow \e problem is to find a feasible flow of minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) -and arc costs. +and arc costs \ref amo93networkflows. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and diff --git a/doc/references.bib b/doc/references.bib --- a/doc/references.bib +++ b/doc/references.bib @@ -150,15 +150,25 @@ %%%%% Maximum flow algorithms %%%%% -@inproceedings{goldberg86newapproach, +@article{edmondskarp72theoretical, + author = {Jack Edmonds and Richard M. Karp}, + title = {Theoretical improvements in algorithmic efficiency + for network flow problems}, + journal = {Journal of the ACM}, + year = 1972, + volume = 19, + number = 2, + pages = {248-264} +} + +@article{goldberg88newapproach, author = {Andrew V. Goldberg and Robert E. Tarjan}, title = {A new approach to the maximum flow problem}, - booktitle = {STOC '86: Proceedings of the Eighteenth Annual ACM - Symposium on Theory of Computing}, - year = 1986, - publisher = {ACM Press}, - address = {New York, NY}, - pages = {136-146} + journal = {Journal of the ACM}, + year = 1988, + volume = 35, + number = 4, + pages = {921-940} } @article{dinic70algorithm, @@ -229,42 +239,18 @@ pages = {205-220} } -@inproceedings{goldberg88cyclecanceling, +@article{goldberg89cyclecanceling, author = {Andrew V. Goldberg and Robert E. Tarjan}, title = {Finding minimum-cost circulations by canceling negative cycles}, - booktitle = {STOC '88: Proceedings of the Twentieth Annual ACM - Symposium on Theory of Computing}, - year = 1988, - publisher = {ACM Press}, - address = {New York, NY}, - pages = {388-397} + journal = {Journal of the ACM}, + year = 1989, + volume = 36, + number = 4, + pages = {873-886} } -@article{edmondskarp72theoretical, - author = {Jack Edmonds and Richard M. Karp}, - title = {Theoretical improvements in algorithmic efficiency - for network flow problems}, - journal = {Journal of the ACM}, - year = 1972, - volume = 19, - number = 2, - pages = {248-264} -} - -@inproceedings{goldberg87approximation, - author = {Andrew V. Goldberg and Robert E. Tarjan}, - title = {Solving minimum-cost flow problems by successive - approximation}, - booktitle = {STOC '87: Proceedings of the Nineteenth Annual ACM - Symposium on Theory of Computing}, - year = 1987, - publisher = {ACM Press}, - address = {New York, NY}, - pages = {7-18} -} - -@article{goldberg90finding, +@article{goldberg90approximation, author = {Andrew V. Goldberg and Robert E. Tarjan}, title = {Finding Minimum-Cost Circulations by Successive Approximation}, @@ -297,6 +283,13 @@ pages = {157-174} } +@book{dantzig63linearprog, + author = {George B. Dantzig}, + title = {Linear Programming and Extensions}, + publisher = {Princeton University Press}, + year = 1963 +} + @mastersthesis{kellyoneill91netsimplex, author = {Damian J. Kelly and Garrett M. O'Neill}, title = {The Minimum Cost Flow Problem and The Network @@ -306,25 +299,3 @@ year = 1991, month = sep, } - -@techreport{lobel96networksimplex, - author = {Andreas L{\"o}bel}, - title = {Solving large-scale real-world minimum-cost flow - problems by a network simplex method}, - institution = {Konrad-Zuse-Zentrum fur Informationstechnik Berlin - ({ZIB})}, - address = {Berlin, Germany}, - year = 1996, - number = {SC 96-7} -} - -@article{frangioni06computational, - author = {Antonio Frangioni and Antonio Manca}, - title = {A Computational Study of Cost Reoptimization for - Min-Cost Flow Problems}, - journal = {INFORMS Journal On Computing}, - year = 2006, - volume = 18, - number = 1, - pages = {61-70} -} diff --git a/lemon/network_simplex.h b/lemon/network_simplex.h --- a/lemon/network_simplex.h +++ b/lemon/network_simplex.h @@ -40,7 +40,9 @@ /// for finding a \ref min_cost_flow "minimum cost flow". /// /// \ref NetworkSimplex implements the primal Network Simplex algorithm - /// for finding a \ref min_cost_flow "minimum cost flow". + /// for finding a \ref min_cost_flow "minimum cost flow" + /// \ref amo93networkflows, \ref dantzig63linearprog, + /// \ref kellyoneill91netsimplex. /// This algorithm is a specialized version of the linear programming /// simplex method directly for the minimum cost flow problem. /// It is one of the most efficient solution methods. diff --git a/lemon/preflow.h b/lemon/preflow.h --- a/lemon/preflow.h +++ b/lemon/preflow.h @@ -102,7 +102,8 @@ /// /// This class provides an implementation of Goldberg-Tarjan's \e preflow /// \e push-relabel algorithm producing a \ref max_flow - /// "flow of maximum value" in a digraph. + /// "flow of maximum value" in a digraph \ref clrs01algorithms, + /// \ref amo93networkflows, \ref goldberg88newapproach. /// The preflow algorithms are the fastest known maximum /// flow algorithms. The current implementation uses a mixture of the /// \e "highest label" and the \e "bound decrease" heuristics.