COIN-OR::LEMON - Graph Library

Changeset 2638:61bf01404ede in lemon-0.x


Ignore:
Timestamp:
06/04/09 03:19:06 (10 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3523
Message:

Various improvements for NS pivot rules

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r2635 r2638  
    242242        _edge(ns._edge), _source(ns._source), _target(ns._target),
    243243        _cost(ns._cost), _state(ns._state), _pi(ns._pi),
    244         _in_edge(ns._in_edge), _edge_num(ns._edge_num + ns._node_num), _next_edge(0)
     244        _in_edge(ns._in_edge), _edge_num(ns._edge_num), _next_edge(0)
    245245      {
    246246        // The main parameters of the pivot rule
    247         const double BLOCK_SIZE_FACTOR = 2.0;
     247        const double BLOCK_SIZE_FACTOR = 0.5;
    248248        const int MIN_BLOCK_SIZE = 10;
    249249
     
    256256        Cost c, min = 0;
    257257        int cnt = _block_size;
    258         int e, min_edge = _next_edge;
     258        int e;
    259259        for (e = _next_edge; e < _edge_num; ++e) {
    260260          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    261261          if (c < min) {
    262262            min = c;
    263             min_edge = e;
     263            _in_edge = e;
    264264          }
    265265          if (--cnt == 0) {
    266             if (min < 0) break;
     266            if (min < 0) goto search_end;
    267267            cnt = _block_size;
    268268          }
    269269        }
    270         if (min == 0 || cnt > 0) {
    271           for (e = 0; e < _next_edge; ++e) {
    272             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    273             if (c < min) {
    274               min = c;
    275               min_edge = e;
    276             }
    277             if (--cnt == 0) {
    278               if (min < 0) break;
    279               cnt = _block_size;
    280             }
     270        for (e = 0; e < _next_edge; ++e) {
     271          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     272          if (c < min) {
     273            min = c;
     274            _in_edge = e;
     275          }
     276          if (--cnt == 0) {
     277            if (min < 0) goto search_end;
     278            cnt = _block_size;
    281279          }
    282280        }
    283281        if (min >= 0) return false;
    284         _in_edge = min_edge;
     282
     283      search_end:
    285284        _next_edge = e;
    286285        return true;
     
    326325      {
    327326        // The main parameters of the pivot rule
    328         const double LIST_LENGTH_FACTOR = 1.0;
     327        const double LIST_LENGTH_FACTOR = 0.25;
    329328        const int MIN_LIST_LENGTH = 10;
    330329        const double MINOR_LIMIT_FACTOR = 0.1;
     
    342341      bool findEnteringEdge() {
    343342        Cost min, c;
    344         int e, min_edge = _next_edge;
     343        int e;
    345344        if (_curr_length > 0 && _minor_count < _minor_limit) {
    346345          // Minor iteration: select the best eligible edge from the
     
    353352            if (c < min) {
    354353              min = c;
    355               min_edge = e;
     354              _in_edge = e;
    356355            }
    357             if (c >= 0) {
     356            else if (c >= 0) {
    358357              _candidates[i--] = _candidates[--_curr_length];
    359358            }
    360359          }
    361           if (min < 0) {
    362             _in_edge = min_edge;
    363             return true;
    364           }
     360          if (min < 0) return true;
    365361        }
    366362
     
    374370            if (c < min) {
    375371              min = c;
    376               min_edge = e;
     372              _in_edge = e;
    377373            }
    378             if (_curr_length == _list_length) break;
    379           }
    380         }
    381         if (_curr_length < _list_length) {
    382           for (e = 0; e < _next_edge; ++e) {
    383             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    384             if (c < 0) {
    385               _candidates[_curr_length++] = e;
    386               if (c < min) {
    387                 min = c;
    388                 min_edge = e;
    389               }
    390               if (_curr_length == _list_length) break;
     374            if (_curr_length == _list_length) goto search_end;
     375          }
     376        }
     377        for (e = 0; e < _next_edge; ++e) {
     378          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     379          if (c < 0) {
     380            _candidates[_curr_length++] = e;
     381            if (c < min) {
     382              min = c;
     383              _in_edge = e;
    391384            }
     385            if (_curr_length == _list_length) goto search_end;
    392386          }
    393387        }
    394388        if (_curr_length == 0) return false;
     389     
     390      search_end:       
    395391        _minor_count = 1;
    396         _in_edge = min_edge;
    397392        _next_edge = e;
    398393        return true;
     
    452447      {
    453448        // The main parameters of the pivot rule
    454         const double BLOCK_SIZE_FACTOR = 1.5;
     449        const double BLOCK_SIZE_FACTOR = 1.0;
    455450        const int MIN_BLOCK_SIZE = 10;
    456451        const double HEAD_LENGTH_FACTOR = 0.1;
     
    480475        // Extend the list
    481476        int cnt = _block_size;
    482         int last_edge = 0;
    483477        int limit = _head_length;
    484478       
    485         for (int e = _next_edge; e < _edge_num; ++e) {
     479        for (e = _next_edge; e < _edge_num; ++e) {
    486480          _cand_cost[e] = _state[e] *
    487481            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    488482          if (_cand_cost[e] < 0) {
    489483            _candidates[_curr_length++] = e;
    490             last_edge = e;
    491484          }
    492485          if (--cnt == 0) {
    493             if (_curr_length > limit) break;
     486            if (_curr_length > limit) goto search_end;
    494487            limit = 0;
    495488            cnt = _block_size;
    496489          }
    497490        }
    498         if (_curr_length <= limit) {
    499           for (int e = 0; e < _next_edge; ++e) {
    500             _cand_cost[e] = _state[e] *
    501               (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    502             if (_cand_cost[e] < 0) {
    503               _candidates[_curr_length++] = e;
    504               last_edge = e;
    505             }
    506             if (--cnt == 0) {
    507               if (_curr_length > limit) break;
    508               limit = 0;
    509               cnt = _block_size;
    510             }
     491        for (e = 0; e < _next_edge; ++e) {
     492          _cand_cost[e] = _state[e] *
     493            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     494          if (_cand_cost[e] < 0) {
     495            _candidates[_curr_length++] = e;
     496          }
     497          if (--cnt == 0) {
     498            if (_curr_length > limit) goto search_end;
     499            limit = 0;
     500            cnt = _block_size;
    511501          }
    512502        }
    513503        if (_curr_length == 0) return false;
    514         _next_edge = last_edge + 1;
     504       
     505      search_end:
    515506
    516507        // Make heap of the candidate list (approximating a partial sort)
     
    520511        // Pop the first element of the heap
    521512        _in_edge = _candidates[0];
     513        _next_edge = e;
    522514        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    523515                  _sort_func );
     
    932924      _pi[_root] = 0;
    933925     
    934       // Store the edges in a mixed order
    935       int k = std::max(int(sqrt(_edge_num)), 10);
     926      // Store the edges
    936927      int i = 0;
    937928      for (EdgeIt e(_orig_graph); e != INVALID; ++e) {
    938         _edge[i] = e;
    939         if ((i += k) >= _edge_num) i = (i % k) + 1;
     929        _edge[i++] = e;
    940930      }
    941931
     
    962952
    963953      // Add artificial edges and initialize the spanning tree data structure
    964       Cost max_cost = std::numeric_limits<Cost>::max() / 4;
     954      Cost max_cost = std::numeric_limits<Cost>::max() / 2 + 1;
    965955      Capacity max_cap = std::numeric_limits<Capacity>::max();
    966956      for (int u = 0, e = _edge_num; u != _node_num; ++u, ++e) {
Note: See TracChangeset for help on using the changeset viewer.