Changeset 1318:ce1533650f7d in lemon
 Timestamp:
 07/07/14 15:40:12 (5 years ago)
 Branch:
 default
 Children:
 1319:11de70cf8550, 1322:1552352f9798
 Parents:
 1315:07cd9a2d20e0 (diff), 1317:b40c2bbb8da5 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r1298 r1318 937 937 _node_id[n] = i; 938 938 } 939 if (_arc_mixing ) {939 if (_arc_mixing && _node_num > 1) { 940 940 // Store the arcs in a mixed order 941 941 const int skip = std::max(_arc_num / _node_num, 3); 
lemon/network_simplex.h
r1317 r1318 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003201 05 * Copyright (C) 20032013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ ref amo93networkflows, \refdantzig63linearprog,45 /// \ refkellyoneill91netsimplex.44 /// \cite amo93networkflows, \cite dantzig63linearprog, 45 /// \cite kellyoneill91netsimplex. 46 46 /// This algorithm is a highly efficient specialized version of the 47 47 /// linear programming simplex method directly for the minimum cost 48 48 /// flow problem. 49 49 /// 50 /// In general, %NetworkSimplex is the fastest implementation available 51 /// in LEMON for this problem. 52 /// Moreover, it supports both directions of the supply/demand inequality 53 /// constraints. For more information, see \ref SupplyType. 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".) 53 /// Furthermore, this class supports both directions of the supply/demand 54 /// inequality constraints. For more information, see \ref SupplyType. 54 55 /// 55 56 /// Most of the parameters of the problem (except for the digraph) … … 64 65 /// algorithm. By default, it is the same as \c V. 65 66 /// 66 /// \warning Both number types must be signed and all input data must 67 /// \warning Both \c V and \c C must be signed number types. 68 /// \warning All input data (capacities, supply values, and costs) must 67 69 /// be integer. 68 70 /// … … 122 124 /// the \ref run() function. 123 125 /// 124 /// \ref NetworkSimplex provides five different pivot rule125 /// implementations that significantly affectthe running time126 /// \ref NetworkSimplex provides five different implementations for 127 /// the pivot strategy that significantly affects the running time 126 128 /// of the algorithm. 127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 /// proved to be the most efficient and the most robust on various 129 /// test inputs. 130 /// However, another pivot rule can be selected using the \ref run() 131 /// function with the proper parameter. 129 /// According to experimental tests conducted on various problem 130 /// instances, \ref BLOCK_SEARCH "Block Search" and 131 /// \ref ALTERING_LIST "Altering Candidate List" rules turned out 132 /// to be the most efficient. 133 /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that 134 /// seemed to be slightly more robust, it is used by default. 135 /// However, another pivot rule can easily be selected using the 136 /// \ref run() function with the proper parameter. 132 137 enum PivotRule { 133 138 … … 155 160 /// The \e Altering \e Candidate \e List pivot rule. 156 161 /// It is a modified version of the Candidate List method. 157 /// It keeps only the severalbest eligible arcs from the former162 /// It keeps only a few of the best eligible arcs from the former 158 163 /// candidate list and extends this list in every iteration. 159 164 ALTERING_LIST … … 168 173 typedef std::vector<Cost> CostVector; 169 174 typedef std::vector<signed char> CharVector; 170 // Note: vector<signed char> is used instead of vector<ArcState> and 175 // Note: vector<signed char> is used instead of vector<ArcState> and 171 176 // vector<ArcDirection> for efficiency reasons 172 177 … … 194 199 195 200 // Parameters of the problem 196 bool _ha ve_lower;201 bool _has_lower; 197 202 SupplyType _stype; 198 203 Value _sum_supply; … … 538 543 SortFunc(const CostVector &map) : _map(map) {} 539 544 bool operator()(int left, int right) { 540 return _map[left] >_map[right];545 return _map[left] < _map[right]; 541 546 } 542 547 }; … … 556 561 const double BLOCK_SIZE_FACTOR = 1.0; 557 562 const int MIN_BLOCK_SIZE = 10; 558 const double HEAD_LENGTH_FACTOR = 0. 1;563 const double HEAD_LENGTH_FACTOR = 0.01; 559 564 const int MIN_HEAD_LENGTH = 3; 560 565 … … 600 605 } 601 606 for (e = 0; e != _next_arc; ++e) { 602 _cand_cost[e] = _state[e] *603 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]);604 if (_cand_cost[e] < 0) {607 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 608 if (c < 0) { 609 _cand_cost[e] = c; 605 610 _candidates[_curr_length++] = e; 606 611 } … … 615 620 search_end: 616 621 617 // Make heap of the candidate list (approximating a partial sort) 618 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, 619 _sort_func ); 620 621 // Pop the first element of the heap 622 // Perform partial sort operation on the candidate list 623 int new_length = std::min(_head_length + 1, _curr_length); 624 std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, 625 _candidates.begin() + _curr_length, _sort_func); 626 627 // Select the entering arc and remove it from the list 622 628 _in_arc = _candidates[0]; 623 629 _next_arc = e; 624 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 625 _sort_func ); 626 _curr_length = std::min(_head_length, _curr_length  1); 630 _candidates[0] = _candidates[new_length  1]; 631 _curr_length = new_length  1; 627 632 return true; 628 633 } … … 678 683 template <typename LowerMap> 679 684 NetworkSimplex& lowerMap(const LowerMap& map) { 680 _ha ve_lower = true;685 _has_lower = true; 681 686 for (ArcIt a(_graph); a != INVALID; ++a) { 682 687 _lower[_arc_id[a]] = map[a]; … … 735 740 /// 736 741 /// \return <tt>(*this)</tt> 742 /// 743 /// \sa supplyType() 737 744 template<typename SupplyMap> 738 745 NetworkSimplex& supplyMap(const SupplyMap& map) { … … 751 758 /// 752 759 /// Using this function has the same effect as using \ref supplyMap() 753 /// with sucha map in which \c k is assigned to \c s, \c k is760 /// with a map in which \c k is assigned to \c s, \c k is 754 761 /// assigned to \c t and all other nodes have zero supply value. 755 762 /// … … 873 880 _cost[i] = 1; 874 881 } 875 _ha ve_lower = false;882 _has_lower = false; 876 883 _stype = GEQ; 877 884 return *this; … … 967 974 /// 968 975 /// This function returns the total cost of the found flow. 969 /// Its complexity is O( e).976 /// Its complexity is O(m). 970 977 /// 971 978 /// \note The return type of the function can be specified as a … … 1004 1011 } 1005 1012 1006 /// \brief Return the flow map (the primal solution). 1013 /// \brief Copy the flow values (the primal solution) into the 1014 /// given map. 1007 1015 /// 1008 1016 /// This function copies the flow value on each arc into the given … … 1028 1036 } 1029 1037 1030 /// \brief Return the potential map (the dual solution). 1038 /// \brief Copy the potential values (the dual solution) into the 1039 /// given map. 1031 1040 /// 1032 1041 /// This function copies the potential (dual value) of each node … … 1059 1068 (_stype == LEQ && _sum_supply >= 0)) ) return false; 1060 1069 1070 // Check lower and upper bounds 1071 LEMON_DEBUG(checkBoundMaps(), 1072 "Upper bounds must be greater or equal to the lower bounds"); 1073 1061 1074 // Remove nonzero lower bounds 1062 if (_ha ve_lower) {1075 if (_has_lower) { 1063 1076 for (int i = 0; i != _arc_num; ++i) { 1064 1077 Value c = _lower[i]; … … 1223 1236 } 1224 1237 1238 // Check if the upper bound is greater than or equal to the lower bound 1239 // on each arc. 1240 bool checkBoundMaps() { 1241 for (int j = 0; j != _arc_num; ++j) { 1242 if (_upper[j] < _lower[j]) return false; 1243 } 1244 return true; 1245 } 1246 1225 1247 // Find the join node 1226 1248 void findJoinNode() { … … 1495 1517 } 1496 1518 } else { 1497 // Find the min. cost incom ming arc for each demand node1519 // Find the min. cost incoming arc for each demand node 1498 1520 for (int i = 0; i != int(demand_nodes.size()); ++i) { 1499 1521 Node v = demand_nodes[i]; … … 1591 1613 1592 1614 // Transform the solution and the supply map to the original form 1593 if (_ha ve_lower) {1615 if (_has_lower) { 1594 1616 for (int i = 0; i != _arc_num; ++i) { 1595 1617 Value c = _lower[i]; 
test/min_cost_flow_test.cc
r1270 r1318 396 396 checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s, 397 397 mcf3.OPTIMAL, true, 300, test_str + "18", GEQ); 398 399 // Tests for empty graph 400 Digraph gr0; 401 MCF mcf0(gr0); 402 mcf0.run(param); 403 check(mcf0.totalCost() == 0, "Wrong total cost"); 398 404 } 399 405 
test/min_cost_flow_test.cc
r1317 r1318 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003201 05 * Copyright (C) 20032013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset
for help on using the changeset viewer.