120 /// \brief Constants for selecting the pivot rule. |
120 /// \brief Constants for selecting the pivot rule. |
121 /// |
121 /// |
122 /// Enum type containing constants for selecting the pivot rule for |
122 /// Enum type containing constants for selecting the pivot rule for |
123 /// the \ref run() function. |
123 /// the \ref run() function. |
124 /// |
124 /// |
125 /// \ref NetworkSimplex provides five different pivot rule |
125 /// \ref NetworkSimplex provides five different implementations for |
126 /// implementations that significantly affect the running time |
126 /// the pivot strategy that significantly affects the running time |
127 /// of the algorithm. |
127 /// of the algorithm. |
128 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which |
128 /// According to experimental tests conducted on various problem |
129 /// turend out to be the most efficient and the most robust on various |
129 /// instances, \ref BLOCK_SEARCH "Block Search" and |
130 /// test inputs. |
130 /// \ref ALTERING_LIST "Altering Candidate List" rules turned out |
131 /// However, another pivot rule can be selected using the \ref run() |
131 /// to be the most efficient. |
132 /// function with the proper parameter. |
132 /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that |
|
133 /// seemed to be slightly more robust, it is used by default. |
|
134 /// However, another pivot rule can easily be selected using the |
|
135 /// \ref run() function with the proper parameter. |
133 enum PivotRule { |
136 enum PivotRule { |
134 |
137 |
135 /// The \e First \e Eligible pivot rule. |
138 /// The \e First \e Eligible pivot rule. |
136 /// The next eligible arc is selected in a wraparound fashion |
139 /// The next eligible arc is selected in a wraparound fashion |
137 /// in every iteration. |
140 /// in every iteration. |
153 /// the best eligible arc is selected from this list. |
156 /// the best eligible arc is selected from this list. |
154 CANDIDATE_LIST, |
157 CANDIDATE_LIST, |
155 |
158 |
156 /// The \e Altering \e Candidate \e List pivot rule. |
159 /// The \e Altering \e Candidate \e List pivot rule. |
157 /// It is a modified version of the Candidate List method. |
160 /// It is a modified version of the Candidate List method. |
158 /// It keeps only the several best eligible arcs from the former |
161 /// It keeps only a few of the best eligible arcs from the former |
159 /// candidate list and extends this list in every iteration. |
162 /// candidate list and extends this list in every iteration. |
160 ALTERING_LIST |
163 ALTERING_LIST |
161 }; |
164 }; |
162 |
165 |
163 private: |
166 private: |
554 _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost) |
557 _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost) |
555 { |
558 { |
556 // The main parameters of the pivot rule |
559 // The main parameters of the pivot rule |
557 const double BLOCK_SIZE_FACTOR = 1.0; |
560 const double BLOCK_SIZE_FACTOR = 1.0; |
558 const int MIN_BLOCK_SIZE = 10; |
561 const int MIN_BLOCK_SIZE = 10; |
559 const double HEAD_LENGTH_FACTOR = 0.1; |
562 const double HEAD_LENGTH_FACTOR = 0.01; |
560 const int MIN_HEAD_LENGTH = 3; |
563 const int MIN_HEAD_LENGTH = 3; |
561 |
564 |
562 _block_size = std::max( int(BLOCK_SIZE_FACTOR * |
565 _block_size = std::max( int(BLOCK_SIZE_FACTOR * |
563 std::sqrt(double(_search_arc_num))), |
566 std::sqrt(double(_search_arc_num))), |
564 MIN_BLOCK_SIZE ); |
567 MIN_BLOCK_SIZE ); |
598 limit = 0; |
601 limit = 0; |
599 cnt = _block_size; |
602 cnt = _block_size; |
600 } |
603 } |
601 } |
604 } |
602 for (e = 0; e != _next_arc; ++e) { |
605 for (e = 0; e != _next_arc; ++e) { |
603 _cand_cost[e] = _state[e] * |
606 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
604 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
607 if (c < 0) { |
605 if (_cand_cost[e] < 0) { |
608 _cand_cost[e] = c; |
606 _candidates[_curr_length++] = e; |
609 _candidates[_curr_length++] = e; |
607 } |
610 } |
608 if (--cnt == 0) { |
611 if (--cnt == 0) { |
609 if (_curr_length > limit) goto search_end; |
612 if (_curr_length > limit) goto search_end; |
610 limit = 0; |
613 limit = 0; |
613 } |
616 } |
614 if (_curr_length == 0) return false; |
617 if (_curr_length == 0) return false; |
615 |
618 |
616 search_end: |
619 search_end: |
617 |
620 |
618 // Make heap of the candidate list (approximating a partial sort) |
621 // Perform partial sort operation on the candidate list |
619 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, |
622 int new_length = std::min(_head_length + 1, _curr_length); |
620 _sort_func ); |
623 std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, |
621 |
624 _candidates.begin() + _curr_length, _sort_func); |
622 // Pop the first element of the heap |
625 |
|
626 // Select the entering arc and remove it from the list |
623 _in_arc = _candidates[0]; |
627 _in_arc = _candidates[0]; |
624 _next_arc = e; |
628 _next_arc = e; |
625 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, |
629 _candidates[0] = _candidates[new_length - 1]; |
626 _sort_func ); |
630 _curr_length = new_length - 1; |
627 _curr_length = std::min(_head_length, _curr_length - 1); |
|
628 return true; |
631 return true; |
629 } |
632 } |
630 |
633 |
631 }; //class AlteringListPivotRule |
634 }; //class AlteringListPivotRule |
632 |
635 |