1.1 --- a/doc/groups.dox Thu Sep 13 12:23:46 2012 +0200
1.2 +++ b/doc/groups.dox Wed Nov 07 17:39:39 2012 +0100
1.3 @@ -407,9 +407,19 @@
1.4 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
1.5
1.6 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
1.7 -implementations, but the other two algorithms could be faster in special cases.
1.8 +implementations.
1.9 +\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
1.10 +several thousands of nodes) and on dense graphs, while \ref CostScaling is
1.11 +typically more efficient on large graphs (e.g. hundreds of thousands of
1.12 +nodes or above), especially if they are sparse.
1.13 +However, other algorithms could be faster in special cases.
1.14 For example, if the total supply and/or capacities are rather small,
1.15 \ref CapacityScaling is usually the fastest algorithm (without effective scaling).
1.16 +
1.17 +These classes are intended to be used with integer-valued input data
1.18 +(capacities, supply values, and costs), except for \ref CapacityScaling,
1.19 +which is capable of handling real-valued arc costs (other numerical
1.20 +data are required to be integer).
1.21 */
1.22
1.23 /**
1.24 @@ -448,7 +458,7 @@
1.25 \brief Algorithms for finding minimum mean cycles.
1.26
1.27 This group contains the algorithms for finding minimum mean cycles
1.28 -\ref clrs01algorithms, \ref amo93networkflows.
1.29 +\ref amo93networkflows, \ref karp78characterization.
1.30
1.31 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.32 of minimum mean length (cost) in a digraph.
1.33 @@ -464,12 +474,11 @@
1.34 function.
1.35
1.36 LEMON contains three algorithms for solving the minimum mean cycle problem:
1.37 -- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
1.38 - \ref dasdan98minmeancycle.
1.39 +- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
1.40 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
1.41 - version of Karp's algorithm \ref dasdan98minmeancycle.
1.42 + version of Karp's algorithm \ref hartmann93finding.
1.43 - \ref HowardMmc Howard's policy iteration algorithm
1.44 - \ref dasdan98minmeancycle.
1.45 + \ref dasdan98minmeancycle, \ref dasdan04experimental.
1.46
1.47 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
1.48 most efficient one, though the best known theoretical bound on its running
2.1 --- a/doc/min_cost_flow.dox Thu Sep 13 12:23:46 2012 +0200
2.2 +++ b/doc/min_cost_flow.dox Wed Nov 07 17:39:39 2012 +0100
2.3 @@ -101,7 +101,7 @@
2.4 sup(u) \quad \forall u\in V \f]
2.5 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
2.6
2.7 -However if the sum of the supply values is zero, then these two problems
2.8 +However, if the sum of the supply values is zero, then these two problems
2.9 are equivalent.
2.10 The \ref min_cost_flow_algs "algorithms" in LEMON support the general
2.11 form, so if you need the equality form, you have to ensure this additional
3.1 --- a/doc/references.bib Thu Sep 13 12:23:46 2012 +0200
3.2 +++ b/doc/references.bib Wed Nov 07 17:39:39 2012 +0100
3.3 @@ -4,8 +4,7 @@
3.4 key = {LEMON},
3.5 title = {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
3.6 {O}ptimization in {N}etworks},
3.7 - howpublished = {\url{http://lemon.cs.elte.hu/}},
3.8 - year = 2009
3.9 + howpublished = {\url{http://lemon.cs.elte.hu/}}
3.10 }
3.11
3.12 @misc{egres,
3.13 @@ -213,6 +212,16 @@
3.14 pages = {309-311}
3.15 }
3.16
3.17 +@article{hartmann93finding,
3.18 + author = {Mark Hartmann and James B. Orlin},
3.19 + title = {Finding minimum cost to time ratio cycles with small
3.20 + integral transit times},
3.21 + journal = {Networks},
3.22 + year = 1993,
3.23 + volume = 23,
3.24 + pages = {567-574}
3.25 +}
3.26 +
3.27 @article{dasdan98minmeancycle,
3.28 author = {Ali Dasdan and Rajesh K. Gupta},
3.29 title = {Faster Maximum and Minimum Mean Cycle Alogrithms for
3.30 @@ -225,6 +234,17 @@
3.31 pages = {889-899}
3.32 }
3.33
3.34 +@article{dasdan04experimental,
3.35 + author = {Ali Dasdan},
3.36 + title = {Experimental analysis of the fastest optimum cycle
3.37 + ratio and mean algorithms},
3.38 + journal = {ACM Trans. Des. Autom. Electron. Syst.},
3.39 + year = 2004,
3.40 + volume = 9,
3.41 + issue = 4,
3.42 + pages = {385-418}
3.43 +}
3.44 +
3.45
3.46 %%%%% Minimum cost flow algorithms %%%%%
3.47
4.1 --- a/lemon/capacity_scaling.h Thu Sep 13 12:23:46 2012 +0200
4.2 +++ b/lemon/capacity_scaling.h Wed Nov 07 17:39:39 2012 +0100
4.3 @@ -70,6 +70,11 @@
4.4 /// \ref edmondskarp72theoretical. It is an efficient dual
4.5 /// solution method.
4.6 ///
4.7 + /// This algorithm is typically slower than \ref CostScaling and
4.8 + /// \ref NetworkSimplex, but in special cases, it can be more
4.9 + /// efficient than them.
4.10 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
4.11 + ///
4.12 /// Most of the parameters of the problem (except for the digraph)
4.13 /// can be given using separate functions, and the algorithm can be
4.14 /// executed using the \ref run() function. If some parameters are not
4.15 @@ -676,7 +681,8 @@
4.16 return _res_cap[_arc_idb[a]];
4.17 }
4.18
4.19 - /// \brief Return the flow map (the primal solution).
4.20 + /// \brief Copy the flow values (the primal solution) into the
4.21 + /// given map.
4.22 ///
4.23 /// This function copies the flow value on each arc into the given
4.24 /// map. The \c Value type of the algorithm must be convertible to
4.25 @@ -700,7 +706,8 @@
4.26 return _pi[_node_id[n]];
4.27 }
4.28
4.29 - /// \brief Return the potential map (the dual solution).
4.30 + /// \brief Copy the potential values (the dual solution) into the
4.31 + /// given map.
4.32 ///
4.33 /// This function copies the potential (dual value) of each node
4.34 /// into the given map.
5.1 --- a/lemon/cost_scaling.h Thu Sep 13 12:23:46 2012 +0200
5.2 +++ b/lemon/cost_scaling.h Wed Nov 07 17:39:39 2012 +0100
5.3 @@ -98,7 +98,8 @@
5.4 /// "preflow push-relabel" algorithm for the maximum flow problem.
5.5 ///
5.6 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
5.7 - /// implementations available in LEMON for this problem.
5.8 + /// implementations available in LEMON for solving this problem.
5.9 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
5.10 ///
5.11 /// Most of the parameters of the problem (except for the digraph)
5.12 /// can be given using separate functions, and the algorithm can be
5.13 @@ -704,7 +705,8 @@
5.14 return _res_cap[_arc_idb[a]];
5.15 }
5.16
5.17 - /// \brief Return the flow map (the primal solution).
5.18 + /// \brief Copy the flow values (the primal solution) into the
5.19 + /// given map.
5.20 ///
5.21 /// This function copies the flow value on each arc into the given
5.22 /// map. The \c Value type of the algorithm must be convertible to
5.23 @@ -728,7 +730,8 @@
5.24 return static_cast<Cost>(_pi[_node_id[n]]);
5.25 }
5.26
5.27 - /// \brief Return the potential map (the dual solution).
5.28 + /// \brief Copy the potential values (the dual solution) into the
5.29 + /// given map.
5.30 ///
5.31 /// This function copies the potential (dual value) of each node
5.32 /// into the given map.
6.1 --- a/lemon/cycle_canceling.h Thu Sep 13 12:23:46 2012 +0200
6.2 +++ b/lemon/cycle_canceling.h Wed Nov 07 17:39:39 2012 +0100
6.3 @@ -48,11 +48,12 @@
6.4 /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
6.5 /// \ref amo93networkflows, \ref klein67primal,
6.6 /// \ref goldberg89cyclecanceling.
6.7 - /// The most efficent one (both theoretically and practically)
6.8 - /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
6.9 - /// thus it is the default method.
6.10 - /// It is strongly polynomial, but in practice, it is typically much
6.11 - /// slower than the scaling algorithms and NetworkSimplex.
6.12 + /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
6.13 + /// "Cancel-and-Tighten" algorithm, thus it is the default method.
6.14 + /// It runs in strongly polynomial time, but in practice, it is typically
6.15 + /// orders of magnitude slower than the scaling algorithms and
6.16 + /// \ref NetworkSimplex.
6.17 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
6.18 ///
6.19 /// Most of the parameters of the problem (except for the digraph)
6.20 /// can be given using separate functions, and the algorithm can be
6.21 @@ -116,26 +117,28 @@
6.22 /// for the \ref run() function.
6.23 ///
6.24 /// \ref CycleCanceling provides three different cycle-canceling
6.25 - /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
6.26 + /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
6.27 /// is used, which is by far the most efficient and the most robust.
6.28 /// However, the other methods can be selected using the \ref run()
6.29 /// function with the proper parameter.
6.30 enum Method {
6.31 /// A simple cycle-canceling method, which uses the
6.32 - /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
6.33 - /// number for detecting negative cycles in the residual network.
6.34 + /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
6.35 + /// cycles in the residual network.
6.36 + /// The number of Bellman-Ford iterations is bounded by a successively
6.37 + /// increased limit.
6.38 SIMPLE_CYCLE_CANCELING,
6.39 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
6.40 /// well-known strongly polynomial method
6.41 /// \ref goldberg89cyclecanceling. It improves along a
6.42 /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
6.43 - /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
6.44 + /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
6.45 MINIMUM_MEAN_CYCLE_CANCELING,
6.46 - /// The "Cancel And Tighten" algorithm, which can be viewed as an
6.47 + /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
6.48 /// improved version of the previous method
6.49 /// \ref goldberg89cyclecanceling.
6.50 /// It is faster both in theory and in practice, its running time
6.51 - /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
6.52 + /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
6.53 CANCEL_AND_TIGHTEN
6.54 };
6.55
6.56 @@ -610,7 +613,8 @@
6.57 return _res_cap[_arc_idb[a]];
6.58 }
6.59
6.60 - /// \brief Return the flow map (the primal solution).
6.61 + /// \brief Copy the flow values (the primal solution) into the
6.62 + /// given map.
6.63 ///
6.64 /// This function copies the flow value on each arc into the given
6.65 /// map. The \c Value type of the algorithm must be convertible to
6.66 @@ -634,7 +638,8 @@
6.67 return static_cast<Cost>(_pi[_node_id[n]]);
6.68 }
6.69
6.70 - /// \brief Return the potential map (the dual solution).
6.71 + /// \brief Copy the potential values (the dual solution) into the
6.72 + /// given map.
6.73 ///
6.74 /// This function copies the potential (dual value) of each node
6.75 /// into the given map.
6.76 @@ -954,7 +959,7 @@
6.77 }
6.78 }
6.79
6.80 - // Execute the "Cancel And Tighten" method
6.81 + // Execute the "Cancel-and-Tighten" method
6.82 void startCancelAndTighten() {
6.83 // Constants for the min mean cycle computations
6.84 const double LIMIT_FACTOR = 1.0;
7.1 --- a/lemon/hartmann_orlin_mmc.h Thu Sep 13 12:23:46 2012 +0200
7.2 +++ b/lemon/hartmann_orlin_mmc.h Wed Nov 07 17:39:39 2012 +0100
7.3 @@ -98,7 +98,7 @@
7.4 ///
7.5 /// This class implements the Hartmann-Orlin algorithm for finding
7.6 /// a directed cycle of minimum mean cost in a digraph
7.7 - /// \ref amo93networkflows, \ref dasdan98minmeancycle.
7.8 + /// \ref hartmann93finding, \ref dasdan98minmeancycle.
7.9 /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
7.10 /// it applies an efficient early termination scheme.
7.11 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
8.1 --- a/lemon/howard_mmc.h Thu Sep 13 12:23:46 2012 +0200
8.2 +++ b/lemon/howard_mmc.h Wed Nov 07 17:39:39 2012 +0100
8.3 @@ -98,7 +98,7 @@
8.4 ///
8.5 /// This class implements Howard's policy iteration algorithm for finding
8.6 /// a directed cycle of minimum mean cost in a digraph
8.7 - /// \ref amo93networkflows, \ref dasdan98minmeancycle.
8.8 + /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
8.9 /// This class provides the most efficient algorithm for the
8.10 /// minimum mean cycle problem, though the best known theoretical
8.11 /// bound on its running time is exponential.
9.1 --- a/lemon/karp_mmc.h Thu Sep 13 12:23:46 2012 +0200
9.2 +++ b/lemon/karp_mmc.h Wed Nov 07 17:39:39 2012 +0100
9.3 @@ -98,7 +98,7 @@
9.4 ///
9.5 /// This class implements Karp's algorithm for finding a directed
9.6 /// cycle of minimum mean cost in a digraph
9.7 - /// \ref amo93networkflows, \ref dasdan98minmeancycle.
9.8 + /// \ref karp78characterization, \ref dasdan98minmeancycle.
9.9 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
9.10 ///
9.11 /// \tparam GR The type of the digraph the algorithm runs on.
10.1 --- a/lemon/network_simplex.h Thu Sep 13 12:23:46 2012 +0200
10.2 +++ b/lemon/network_simplex.h Wed Nov 07 17:39:39 2012 +0100
10.3 @@ -48,7 +48,8 @@
10.4 /// flow problem.
10.5 ///
10.6 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
10.7 - /// implementations available in LEMON for this problem.
10.8 + /// implementations available in LEMON for solving this problem.
10.9 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
10.10 /// Furthermore, this class supports both directions of the supply/demand
10.11 /// inequality constraints. For more information, see \ref SupplyType.
10.12 ///
10.13 @@ -1009,7 +1010,8 @@
10.14 return _flow[_arc_id[a]];
10.15 }
10.16
10.17 - /// \brief Return the flow map (the primal solution).
10.18 + /// \brief Copy the flow values (the primal solution) into the
10.19 + /// given map.
10.20 ///
10.21 /// This function copies the flow value on each arc into the given
10.22 /// map. The \c Value type of the algorithm must be convertible to
10.23 @@ -1033,7 +1035,8 @@
10.24 return _pi[_node_id[n]];
10.25 }
10.26
10.27 - /// \brief Return the potential map (the dual solution).
10.28 + /// \brief Copy the potential values (the dual solution) into the
10.29 + /// given map.
10.30 ///
10.31 /// This function copies the potential (dual value) of each node
10.32 /// into the given map.