COIN-OR::LEMON - Graph Library

Changeset 984:fcb6ad1e67d0 in lemon-main


Ignore:
Timestamp:
01/30/12 20:21:45 (12 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve the Altering List pivot rule for NetworkSimplex? (#435)
Much less candidate arcs are preserved from an iteration to the
next one and partial_sort() is used instead of heap operations.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r922 r984  
    123123    /// the \ref run() function.
    124124    ///
    125     /// \ref NetworkSimplex provides five different pivot rule
    126     /// implementations that significantly affect the running time
     125    /// \ref NetworkSimplex provides five different implementations for
     126    /// the pivot strategy that significantly affects the running time
    127127    /// of the algorithm.
    128     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    129     /// turend out to be the most efficient and the most robust on various
    130     /// test inputs.
    131     /// However, another pivot rule can be selected using the \ref run()
    132     /// function with the proper parameter.
     128    /// According to experimental tests conducted on various problem
     129    /// instances, \ref BLOCK_SEARCH "Block Search" and
     130    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
     131    /// to be the most efficient.
     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.
    133136    enum PivotRule {
    134137
     
    156159      /// The \e Altering \e Candidate \e List pivot rule.
    157160      /// 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
    159162      /// candidate list and extends this list in every iteration.
    160163      ALTERING_LIST
     
    539542        SortFunc(const CostVector &map) : _map(map) {}
    540543        bool operator()(int left, int right) {
    541           return _map[left] > _map[right];
     544          return _map[left] < _map[right];
    542545        }
    543546      };
     
    557560        const double BLOCK_SIZE_FACTOR = 1.0;
    558561        const int MIN_BLOCK_SIZE = 10;
    559         const double HEAD_LENGTH_FACTOR = 0.1;
     562        const double HEAD_LENGTH_FACTOR = 0.01;
    560563        const int MIN_HEAD_LENGTH = 3;
    561564
     
    601604        }
    602605        for (e = 0; e != _next_arc; ++e) {
    603           _cand_cost[e] = _state[e] *
    604             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    605           if (_cand_cost[e] < 0) {
     606          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     607          if (c < 0) {
     608            _cand_cost[e] = c;
    606609            _candidates[_curr_length++] = e;
    607610          }
     
    616619      search_end:
    617620
    618         // Make heap of the candidate list (approximating a partial sort)
    619         make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    620                    _sort_func );
    621 
    622         // Pop the first element of the heap
     621        // Perform partial sort operation on the candidate list
     622        int new_length = std::min(_head_length + 1, _curr_length);
     623        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
     624                          _candidates.begin() + _curr_length, _sort_func);
     625
     626        // Select the entering arc and remove it from the list
    623627        _in_arc = _candidates[0];
    624628        _next_arc = e;
    625         pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    626                   _sort_func );
    627         _curr_length = std::min(_head_length, _curr_length - 1);
     629        _candidates[0] = _candidates[new_length - 1];
     630        _curr_length = new_length - 1;
    628631        return true;
    629632      }
Note: See TracChangeset for help on using the changeset viewer.