Changes in / [1004:d59484d5fc1f:1001:e344f0887c59] in lemon-main
- Files:
-
- 10 edited
-
doc/groups.dox (modified) (3 diffs)
-
doc/min_cost_flow.dox (modified) (1 diff)
-
doc/references.bib (modified) (3 diffs)
-
lemon/capacity_scaling.h (modified) (3 diffs)
-
lemon/cost_scaling.h (modified) (3 diffs)
-
lemon/cycle_canceling.h (modified) (7 diffs)
-
lemon/hartmann_orlin_mmc.h (modified) (1 diff)
-
lemon/howard_mmc.h (modified) (1 diff)
-
lemon/karp_mmc.h (modified) (1 diff)
-
lemon/network_simplex.h (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r1003 r919 408 408 409 409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 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. 410 implementations, but the other two algorithms could be faster in special cases. 416 411 For example, if the total supply and/or capacities are rather small, 417 412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). 418 419 These classes are intended to be used with integer-valued input data420 (capacities, supply values, and costs), except for \ref CapacityScaling,421 which is capable of handling real-valued arc costs (other numerical422 data are required to be integer).423 413 */ 424 414 … … 459 449 460 450 This group contains the algorithms for finding minimum mean cycles 461 \ref amo93networkflows, \ref karp78characterization.451 \ref clrs01algorithms, \ref amo93networkflows. 462 452 463 453 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 475 465 476 466 LEMON contains three algorithms for solving the minimum mean cycle problem: 477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization. 467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 468 \ref dasdan98minmeancycle. 478 469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 479 version of Karp's algorithm \ref hartmann93finding.470 version of Karp's algorithm \ref dasdan98minmeancycle. 480 471 - \ref HowardMmc Howard's policy iteration algorithm 481 \ref dasdan98minmeancycle , \ref dasdan04experimental.472 \ref dasdan98minmeancycle. 482 473 483 474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the -
doc/min_cost_flow.dox
r1002 r877 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
r1002 r904 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/}} 7 howpublished = {\url{http://lemon.cs.elte.hu/}}, 8 year = 2009 8 9 } 9 10 … … 211 212 volume = 23, 212 213 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 small218 integral transit times},219 journal = {Networks},220 year = 1993,221 volume = 23,222 pages = {567-574}223 214 } 224 215 … … 235 226 } 236 227 237 @article{dasdan04experimental,238 author = {Ali Dasdan},239 title = {Experimental analysis of the fastest optimum cycle240 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 248 228 249 229 %%%%% Minimum cost flow algorithms %%%%% -
lemon/capacity_scaling.h
r1004 r985 70 70 /// \ref edmondskarp72theoretical. It is an efficient dual 71 71 /// solution method. 72 ///73 /// This algorithm is typically slower than \ref CostScaling and74 /// \ref NetworkSimplex, but in special cases, it can be more75 /// efficient than them.76 /// (For more information, see \ref min_cost_flow_algs "the module page".)77 72 /// 78 73 /// Most of the parameters of the problem (except for the digraph) … … 682 677 } 683 678 684 /// \brief Copy the flow values (the primal solution) into the 685 /// given map. 679 /// \brief Return the flow map (the primal solution). 686 680 /// 687 681 /// This function copies the flow value on each arc into the given … … 707 701 } 708 702 709 /// \brief Copy the potential values (the dual solution) into the 710 /// given map. 703 /// \brief Return the potential map (the dual solution). 711 704 /// 712 705 /// This function copies the potential (dual value) of each node -
lemon/cost_scaling.h
r1003 r938 99 99 /// 100 100 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 101 /// implementations available in LEMON for solving this problem. 102 /// (For more information, see \ref min_cost_flow_algs "the module page".) 101 /// implementations available in LEMON for this problem. 103 102 /// 104 103 /// Most of the parameters of the problem (except for the digraph) … … 706 705 } 707 706 708 /// \brief Copy the flow values (the primal solution) into the 709 /// given map. 707 /// \brief Return the flow map (the primal solution). 710 708 /// 711 709 /// This function copies the flow value on each arc into the given … … 731 729 } 732 730 733 /// \brief Copy the potential values (the dual solution) into the 734 /// given map. 731 /// \brief Return the potential map (the dual solution). 735 732 /// 736 733 /// This function copies the potential (dual value) of each node -
lemon/cycle_canceling.h
r1003 r922 49 49 /// \ref amo93networkflows, \ref klein67primal, 50 50 /// \ref goldberg89cyclecanceling. 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".) 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. 57 56 /// 58 57 /// Most of the parameters of the problem (except for the digraph) … … 118 117 /// 119 118 /// \ref CycleCanceling provides three different cycle-canceling 120 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel -and-Tighten"119 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" 121 120 /// is used, which is by far the most efficient and the most robust. 122 121 /// However, the other methods can be selected using the \ref run() … … 124 123 enum Method { 125 124 /// A simple cycle-canceling method, which uses the 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. 125 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration 126 /// number for detecting negative cycles in the residual network. 130 127 SIMPLE_CYCLE_CANCELING, 131 128 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a … … 133 130 /// \ref goldberg89cyclecanceling. It improves along a 134 131 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 135 /// Its running time complexity is O(n<sup>2</sup> e<sup>3</sup>log(n)).132 /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)). 136 133 MINIMUM_MEAN_CYCLE_CANCELING, 137 /// The "Cancel -and-Tighten" algorithm, which can be viewed as an134 /// The "Cancel And Tighten" algorithm, which can be viewed as an 138 135 /// improved version of the previous method 139 136 /// \ref goldberg89cyclecanceling. 140 137 /// It is faster both in theory and in practice, its running time 141 /// complexity is O(n<sup>2</sup> e<sup>2</sup>log(n)).138 /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)). 142 139 CANCEL_AND_TIGHTEN 143 140 }; … … 614 611 } 615 612 616 /// \brief Copy the flow values (the primal solution) into the 617 /// given map. 613 /// \brief Return the flow map (the primal solution). 618 614 /// 619 615 /// This function copies the flow value on each arc into the given … … 639 635 } 640 636 641 /// \brief Copy the potential values (the dual solution) into the 642 /// given map. 637 /// \brief Return the potential map (the dual solution). 643 638 /// 644 639 /// This function copies the potential (dual value) of each node … … 960 955 } 961 956 962 // Execute the "Cancel -and-Tighten" method957 // Execute the "Cancel And Tighten" method 963 958 void startCancelAndTighten() { 964 959 // Constants for the min mean cycle computations -
lemon/hartmann_orlin_mmc.h
r1002 r879 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 hartmann93finding, \ref dasdan98minmeancycle.101 /// \ref amo93networkflows, \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
r1002 r877 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 dasdan98minmeancycle, \ref dasdan04experimental.101 /// \ref amo93networkflows, \ref dasdan98minmeancycle. 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
r1002 r877 99 99 /// This class implements Karp's algorithm for finding a directed 100 100 /// cycle of minimum mean cost in a digraph 101 /// \ref karp78characterization, \ref dasdan98minmeancycle.101 /// \ref amo93networkflows, \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
r1004 r984 49 49 /// 50 50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 51 /// implementations available in LEMON for solving this problem. 52 /// (For more information, see \ref min_cost_flow_algs "the module page".) 51 /// implementations available in LEMON for this problem. 53 52 /// Furthermore, this class supports both directions of the supply/demand 54 53 /// inequality constraints. For more information, see \ref SupplyType. … … 1011 1010 } 1012 1011 1013 /// \brief Copy the flow values (the primal solution) into the 1014 /// given map. 1012 /// \brief Return the flow map (the primal solution). 1015 1013 /// 1016 1014 /// This function copies the flow value on each arc into the given … … 1036 1034 } 1037 1035 1038 /// \brief Copy the potential values (the dual solution) into the 1039 /// given map. 1036 /// \brief Return the potential map (the dual solution). 1040 1037 /// 1041 1038 /// This function copies the potential (dual value) of each node
Note: See TracChangeset
for help on using the changeset viewer.
