Small improvements in NS pivot rules (#298)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 01 Jul 2009 16:34:01 +0200
changeset 727cab85bd7859b
parent 680 257e91516e09
child 728 e2bdd1a988f3
Small improvements in NS pivot rules (#298)
lemon/network_simplex.h
     1.1 --- a/lemon/network_simplex.h	Fri May 29 17:46:48 2009 +0100
     1.2 +++ b/lemon/network_simplex.h	Wed Jul 01 16:34:01 2009 +0200
     1.3 @@ -364,33 +364,32 @@
     1.4        bool findEnteringArc() {
     1.5          Cost c, min = 0;
     1.6          int cnt = _block_size;
     1.7 -        int e, min_arc = _next_arc;
     1.8 +        int e;
     1.9          for (e = _next_arc; e < _search_arc_num; ++e) {
    1.10            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    1.11            if (c < min) {
    1.12              min = c;
    1.13 -            min_arc = e;
    1.14 +            _in_arc = e;
    1.15            }
    1.16            if (--cnt == 0) {
    1.17 -            if (min < 0) break;
    1.18 +            if (min < 0) goto search_end;
    1.19              cnt = _block_size;
    1.20            }
    1.21          }
    1.22 -        if (min == 0 || cnt > 0) {
    1.23 -          for (e = 0; e < _next_arc; ++e) {
    1.24 -            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    1.25 -            if (c < min) {
    1.26 -              min = c;
    1.27 -              min_arc = e;
    1.28 -            }
    1.29 -            if (--cnt == 0) {
    1.30 -              if (min < 0) break;
    1.31 -              cnt = _block_size;
    1.32 -            }
    1.33 +        for (e = 0; e < _next_arc; ++e) {
    1.34 +          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    1.35 +          if (c < min) {
    1.36 +            min = c;
    1.37 +            _in_arc = e;
    1.38 +          }
    1.39 +          if (--cnt == 0) {
    1.40 +            if (min < 0) goto search_end;
    1.41 +            cnt = _block_size;
    1.42            }
    1.43          }
    1.44          if (min >= 0) return false;
    1.45 -        _in_arc = min_arc;
    1.46 +
    1.47 +      search_end:
    1.48          _next_arc = e;
    1.49          return true;
    1.50        }
    1.51 @@ -428,7 +427,7 @@
    1.52          _next_arc(0)
    1.53        {
    1.54          // The main parameters of the pivot rule
    1.55 -        const double LIST_LENGTH_FACTOR = 1.0;
    1.56 +        const double LIST_LENGTH_FACTOR = 0.25;
    1.57          const int MIN_LIST_LENGTH = 10;
    1.58          const double MINOR_LIMIT_FACTOR = 0.1;
    1.59          const int MIN_MINOR_LIMIT = 3;
    1.60 @@ -445,7 +444,7 @@
    1.61        /// Find next entering arc
    1.62        bool findEnteringArc() {
    1.63          Cost min, c;
    1.64 -        int e, min_arc = _next_arc;
    1.65 +        int e;
    1.66          if (_curr_length > 0 && _minor_count < _minor_limit) {
    1.67            // Minor iteration: select the best eligible arc from the
    1.68            // current candidate list
    1.69 @@ -456,16 +455,13 @@
    1.70              c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    1.71              if (c < min) {
    1.72                min = c;
    1.73 -              min_arc = e;
    1.74 +              _in_arc = e;
    1.75              }
    1.76 -            if (c >= 0) {
    1.77 +            else if (c >= 0) {
    1.78                _candidates[i--] = _candidates[--_curr_length];
    1.79              }
    1.80            }
    1.81 -          if (min < 0) {
    1.82 -            _in_arc = min_arc;
    1.83 -            return true;
    1.84 -          }
    1.85 +          if (min < 0) return true;
    1.86          }
    1.87  
    1.88          // Major iteration: build a new candidate list
    1.89 @@ -477,27 +473,26 @@
    1.90              _candidates[_curr_length++] = e;
    1.91              if (c < min) {
    1.92                min = c;
    1.93 -              min_arc = e;
    1.94 +              _in_arc = e;
    1.95              }
    1.96 -            if (_curr_length == _list_length) break;
    1.97 +            if (_curr_length == _list_length) goto search_end;
    1.98            }
    1.99          }
   1.100 -        if (_curr_length < _list_length) {
   1.101 -          for (e = 0; e < _next_arc; ++e) {
   1.102 -            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.103 -            if (c < 0) {
   1.104 -              _candidates[_curr_length++] = e;
   1.105 -              if (c < min) {
   1.106 -                min = c;
   1.107 -                min_arc = e;
   1.108 -              }
   1.109 -              if (_curr_length == _list_length) break;
   1.110 +        for (e = 0; e < _next_arc; ++e) {
   1.111 +          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.112 +          if (c < 0) {
   1.113 +            _candidates[_curr_length++] = e;
   1.114 +            if (c < min) {
   1.115 +              min = c;
   1.116 +              _in_arc = e;
   1.117              }
   1.118 +            if (_curr_length == _list_length) goto search_end;
   1.119            }
   1.120          }
   1.121          if (_curr_length == 0) return false;
   1.122 +      
   1.123 +      search_end:        
   1.124          _minor_count = 1;
   1.125 -        _in_arc = min_arc;
   1.126          _next_arc = e;
   1.127          return true;
   1.128        }
   1.129 @@ -549,7 +544,7 @@
   1.130          _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
   1.131        {
   1.132          // The main parameters of the pivot rule
   1.133 -        const double BLOCK_SIZE_FACTOR = 1.5;
   1.134 +        const double BLOCK_SIZE_FACTOR = 1.0;
   1.135          const int MIN_BLOCK_SIZE = 10;
   1.136          const double HEAD_LENGTH_FACTOR = 0.1;
   1.137          const int MIN_HEAD_LENGTH = 3;
   1.138 @@ -578,39 +573,35 @@
   1.139  
   1.140          // Extend the list
   1.141          int cnt = _block_size;
   1.142 -        int last_arc = 0;
   1.143          int limit = _head_length;
   1.144  
   1.145 -        for (int e = _next_arc; e < _search_arc_num; ++e) {
   1.146 +        for (e = _next_arc; e < _search_arc_num; ++e) {
   1.147            _cand_cost[e] = _state[e] *
   1.148              (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.149            if (_cand_cost[e] < 0) {
   1.150              _candidates[_curr_length++] = e;
   1.151 -            last_arc = e;
   1.152            }
   1.153            if (--cnt == 0) {
   1.154 -            if (_curr_length > limit) break;
   1.155 +            if (_curr_length > limit) goto search_end;
   1.156              limit = 0;
   1.157              cnt = _block_size;
   1.158            }
   1.159          }
   1.160 -        if (_curr_length <= limit) {
   1.161 -          for (int e = 0; e < _next_arc; ++e) {
   1.162 -            _cand_cost[e] = _state[e] *
   1.163 -              (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.164 -            if (_cand_cost[e] < 0) {
   1.165 -              _candidates[_curr_length++] = e;
   1.166 -              last_arc = e;
   1.167 -            }
   1.168 -            if (--cnt == 0) {
   1.169 -              if (_curr_length > limit) break;
   1.170 -              limit = 0;
   1.171 -              cnt = _block_size;
   1.172 -            }
   1.173 +        for (e = 0; e < _next_arc; ++e) {
   1.174 +          _cand_cost[e] = _state[e] *
   1.175 +            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
   1.176 +          if (_cand_cost[e] < 0) {
   1.177 +            _candidates[_curr_length++] = e;
   1.178 +          }
   1.179 +          if (--cnt == 0) {
   1.180 +            if (_curr_length > limit) goto search_end;
   1.181 +            limit = 0;
   1.182 +            cnt = _block_size;
   1.183            }
   1.184          }
   1.185          if (_curr_length == 0) return false;
   1.186 -        _next_arc = last_arc + 1;
   1.187 +        
   1.188 +      search_end:
   1.189  
   1.190          // Make heap of the candidate list (approximating a partial sort)
   1.191          make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
   1.192 @@ -618,6 +609,7 @@
   1.193  
   1.194          // Pop the first element of the heap
   1.195          _in_arc = _candidates[0];
   1.196 +        _next_arc = e;
   1.197          pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
   1.198                    _sort_func );
   1.199          _curr_length = std::min(_head_length, _curr_length - 1);