Changes in / [1163:e344f0887c59:1166:d59484d5fc1f] in lemon
- Files:
-
- 10 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r1023 r1165 408 408 409 409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 410 implementations, but the other two algorithms could be faster in special cases. 410 implementations. 411 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to 412 several thousands of nodes) and on dense graphs, while \ref CostScaling is 413 typically more efficient on large graphs (e.g. hundreds of thousands of 414 nodes or above), especially if they are sparse. 415 However, other algorithms could be faster in special cases. 411 416 For example, if the total supply and/or capacities are rather small, 412 417 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). 418 419 These classes are intended to be used with integer-valued input data 420 (capacities, supply values, and costs), except for \ref CapacityScaling, 421 which is capable of handling real-valued arc costs (other numerical 422 data are required to be integer). 413 423 */ 414 424 … … 449 459 450 460 This group contains the algorithms for finding minimum mean cycles 451 \ref clrs01algorithms, \ref amo93networkflows.461 \ref amo93networkflows, \ref karp78characterization. 452 462 453 463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 465 475 466 476 LEMON contains three algorithms for solving the minimum mean cycle problem: 467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization. 469 478 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 470 version of Karp's algorithm \ref dasdan98minmeancycle.479 version of Karp's algorithm \ref hartmann93finding. 471 480 - \ref HowardMmc Howard's policy iteration algorithm 472 \ref dasdan98minmeancycle .481 \ref dasdan98minmeancycle, \ref dasdan04experimental. 473 482 474 483 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the -
doc/min_cost_flow.dox
r956 r1164 102 102 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] 103 103 104 However if the sum of the supply values is zero, then these two problems104 However, if the sum of the supply values is zero, then these two problems 105 105 are equivalent. 106 106 The \ref min_cost_flow_algs "algorithms" in LEMON support the general -
doc/references.bib
r999 r1164 5 5 title = {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and 6 6 {O}ptimization in {N}etworks}, 7 howpublished = {\url{http://lemon.cs.elte.hu/}}, 8 year = 2009 7 howpublished = {\url{http://lemon.cs.elte.hu/}} 9 8 } 10 9 … … 212 211 volume = 23, 213 212 pages = {309-311} 213 } 214 215 @article{hartmann93finding, 216 author = {Mark Hartmann and James B. Orlin}, 217 title = {Finding minimum cost to time ratio cycles with small 218 integral transit times}, 219 journal = {Networks}, 220 year = 1993, 221 volume = 23, 222 pages = {567-574} 214 223 } 215 224 … … 226 235 } 227 236 237 @article{dasdan04experimental, 238 author = {Ali Dasdan}, 239 title = {Experimental analysis of the fastest optimum cycle 240 ratio and mean algorithms}, 241 journal = {ACM Trans. Des. Autom. Electron. Syst.}, 242 year = 2004, 243 volume = 9, 244 issue = 4, 245 pages = {385-418} 246 } 247 228 248 229 249 %%%%% Minimum cost flow algorithms %%%%% -
lemon/capacity_scaling.h
r1137 r1166 70 70 /// \ref edmondskarp72theoretical. It is an efficient dual 71 71 /// solution method. 72 /// 73 /// This algorithm is typically slower than \ref CostScaling and 74 /// \ref NetworkSimplex, but in special cases, it can be more 75 /// efficient than them. 76 /// (For more information, see \ref min_cost_flow_algs "the module page".) 72 77 /// 73 78 /// Most of the parameters of the problem (except for the digraph) … … 677 682 } 678 683 679 /// \brief Return the flow map (the primal solution). 684 /// \brief Copy the flow values (the primal solution) into the 685 /// given map. 680 686 /// 681 687 /// This function copies the flow value on each arc into the given … … 701 707 } 702 708 703 /// \brief Return the potential map (the dual solution). 709 /// \brief Copy the potential values (the dual solution) into the 710 /// given map. 704 711 /// 705 712 /// This function copies the potential (dual value) of each node -
lemon/cost_scaling.h
r1049 r1165 99 99 /// 100 100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 101 /// implementations available in LEMON for this problem. 101 /// implementations available in LEMON for solving this problem. 102 /// (For more information, see \ref min_cost_flow_algs "the module page".) 102 103 /// 103 104 /// Most of the parameters of the problem (except for the digraph) … … 705 706 } 706 707 707 /// \brief Return the flow map (the primal solution). 708 /// \brief Copy the flow values (the primal solution) into the 709 /// given map. 708 710 /// 709 711 /// This function copies the flow value on each arc into the given … … 729 731 } 730 732 731 /// \brief Return the potential map (the dual solution). 733 /// \brief Copy the potential values (the dual solution) into the 734 /// given map. 732 735 /// 733 736 /// This function copies the potential (dual value) of each node -
lemon/cycle_canceling.h
r1026 r1165 49 49 /// \ref amo93networkflows, \ref klein67primal, 50 50 /// \ref goldberg89cyclecanceling. 51 /// The most efficent one (both theoretically and practically) 52 /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, 53 /// thus it is the default method. 54 /// It is strongly polynomial, but in practice, it is typically much 55 /// slower than the scaling algorithms and NetworkSimplex. 51 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 52 /// "Cancel-and-Tighten" algorithm, thus it is the default method. 53 /// It runs in strongly polynomial time, but in practice, it is typically 54 /// orders of magnitude slower than the scaling algorithms and 55 /// \ref NetworkSimplex. 56 /// (For more information, see \ref min_cost_flow_algs "the module page".) 56 57 /// 57 58 /// Most of the parameters of the problem (except for the digraph) … … 117 118 /// 118 119 /// \ref CycleCanceling provides three different cycle-canceling 119 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel andTighten"120 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten" 120 121 /// is used, which is by far the most efficient and the most robust. 121 122 /// However, the other methods can be selected using the \ref run() … … 123 124 enum Method { 124 125 /// A simple cycle-canceling method, which uses the 125 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration 126 /// number for detecting negative cycles in the residual network. 126 /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative 127 /// cycles in the residual network. 128 /// The number of Bellman-Ford iterations is bounded by a successively 129 /// increased limit. 127 130 SIMPLE_CYCLE_CANCELING, 128 131 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a … … 130 133 /// \ref goldberg89cyclecanceling. It improves along a 131 134 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 132 /// Its running time complexity is O(n<sup>2</sup> m<sup>3</sup>log(n)).135 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). 133 136 MINIMUM_MEAN_CYCLE_CANCELING, 134 /// The "Cancel AndTighten" algorithm, which can be viewed as an137 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an 135 138 /// improved version of the previous method 136 139 /// \ref goldberg89cyclecanceling. 137 140 /// It is faster both in theory and in practice, its running time 138 /// complexity is O(n<sup>2</sup> m<sup>2</sup>log(n)).141 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). 139 142 CANCEL_AND_TIGHTEN 140 143 }; … … 611 614 } 612 615 613 /// \brief Return the flow map (the primal solution). 616 /// \brief Copy the flow values (the primal solution) into the 617 /// given map. 614 618 /// 615 619 /// This function copies the flow value on each arc into the given … … 635 639 } 636 640 637 /// \brief Return the potential map (the dual solution). 641 /// \brief Copy the potential values (the dual solution) into the 642 /// given map. 638 643 /// 639 644 /// This function copies the potential (dual value) of each node … … 955 960 } 956 961 957 // Execute the "Cancel AndTighten" method962 // Execute the "Cancel-and-Tighten" method 958 963 void startCancelAndTighten() { 959 964 // Constants for the min mean cycle computations -
lemon/hartmann_orlin_mmc.h
r959 r1164 99 99 /// This class implements the Hartmann-Orlin algorithm for finding 100 100 /// a directed cycle of minimum mean cost in a digraph 101 /// \ref amo93networkflows, \ref dasdan98minmeancycle.101 /// \ref hartmann93finding, \ref dasdan98minmeancycle. 102 102 /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm, 103 103 /// it applies an efficient early termination scheme. -
lemon/howard_mmc.h
r956 r1164 99 99 /// This class implements Howard's policy iteration algorithm for finding 100 100 /// a directed cycle of minimum mean cost in a digraph 101 /// \ref amo93networkflows, \ref dasdan98minmeancycle.101 /// \ref dasdan98minmeancycle, \ref dasdan04experimental. 102 102 /// This class provides the most efficient algorithm for the 103 103 /// minimum mean cycle problem, though the best known theoretical -
lemon/karp_mmc.h
r956 r1164 99 99 /// This class implements Karp's algorithm for finding a directed 100 100 /// cycle of minimum mean cost in a digraph 101 /// \ref amo93networkflows, \ref dasdan98minmeancycle.101 /// \ref karp78characterization, \ref dasdan98minmeancycle. 102 102 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). 103 103 /// -
lemon/network_simplex.h
r1136 r1166 49 49 /// 50 50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 51 /// implementations available in LEMON for this problem. 51 /// implementations available in LEMON for solving this problem. 52 /// (For more information, see \ref min_cost_flow_algs "the module page".) 52 53 /// Furthermore, this class supports both directions of the supply/demand 53 54 /// inequality constraints. For more information, see \ref SupplyType. … … 1010 1011 } 1011 1012 1012 /// \brief Return the flow map (the primal solution). 1013 /// \brief Copy the flow values (the primal solution) into the 1014 /// given map. 1013 1015 /// 1014 1016 /// This function copies the flow value on each arc into the given … … 1034 1036 } 1035 1037 1036 /// \brief Return the potential map (the dual solution). 1038 /// \brief Copy the potential values (the dual solution) into the 1039 /// given map. 1037 1040 /// 1038 1041 /// This function copies the potential (dual value) of each node
Note: See TracChangeset
for help on using the changeset viewer.