LEMON/LEMON-official Changeset - r1136:fcb6ad1e67d0

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r1136:fcb6ad1e67d0

« 1132:48e173

1138:c8896b »

r1136:fcb6ad1e67d0

Mon, 30 Jan 2012 20:21:45

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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.

0 1 0

default

1 file changed with 23 insertions and 20 deletions:

lemon/network_simplex.h

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -119,20 +119,23 @@
 		    /// \brief Constants for selecting the pivot rule.
 		    ///
 		    /// Enum type containing constants for selecting the pivot rule for
 		    /// the \ref run() function.
 		    ///
 		    /// \ref NetworkSimplex provides five different pivot rule
 		    /// implementations that significantly affect the running time
 		    /// \ref NetworkSimplex provides five different implementations for
 		    /// the pivot strategy that significantly affects the running time
 		    /// of the algorithm.
 		    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
 		    /// turend out to be the most efficient and the most robust on various
 		    /// test inputs.
 		    /// However, another pivot rule can be selected using the \ref run()
-		    /// function with the proper parameter.
+		    /// According to experimental tests conducted on various problem
 		    /// instances, \ref BLOCK_SEARCH "Block Search" and
 		    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
 		    /// to be the most efficient.
 		    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
 		    /// seemed to be slightly more robust, it is used by default.
 		    /// However, another pivot rule can easily be selected using the
 		    /// \ref run() function with the proper parameter.
 		    enum PivotRule {
 		      /// The \e First \e Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
@@ -152,13 +155,13 @@
 		      /// in a wraparound fashion and in the following minor iterations
 		      /// the best eligible arc is selected from this list.
 		      CANDIDATE_LIST,
 		      /// The \e Altering \e Candidate \e List pivot rule.
 		      /// It is a modified version of the Candidate List method.
-		      /// It keeps only the several best eligible arcs from the former
+		      /// It keeps only a few of the best eligible arcs from the former
 		      /// candidate list and extends this list in every iteration.
 		      ALTERING_LIST
 		    };
 		  private:
@@ -535,13 +538,13 @@
+		      {
 		      private:
 		        const CostVector &_map;
 		      public:
 		        SortFunc(const CostVector &map) : _map(map) {}
 		        bool operator()(int left, int right) {
-		          return _map[left] > _map[right];
+		          return _map[left] < _map[right];
+		        }
 		      };
 		      SortFunc _sort_func;
 		    public:
@@ -553,13 +556,13 @@
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
+		      {
 		        // The main parameters of the pivot rule
 		        const double BLOCK_SIZE_FACTOR = 1.0;
 		        const int MIN_BLOCK_SIZE = 10;
-		        const double HEAD_LENGTH_FACTOR = 0.1;
+		        const double HEAD_LENGTH_FACTOR = 0.01;
 		        const int MIN_HEAD_LENGTH = 3;
 		        _block_size = std::max( int(BLOCK_SIZE_FACTOR *
 		                                    std::sqrt(double(_search_arc_num))),
 		                                MIN_BLOCK_SIZE );
 		        _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
@@ -597,37 +600,37 @@
 		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        for (e = 0; e != _next_arc; ++e) {
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-		          if (_cand_cost[e] < 0) {
+		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < 0) {
 		            _cand_cost[e] = c;
 		            _candidates[_curr_length++] = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        // Make heap of the candidate list (approximating a partial sort)
 		        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
-		                   _sort_func );
+		        // Perform partial sort operation on the candidate list
 		        int new_length = std::min(_head_length + 1, _curr_length);
 		        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
 		                          _candidates.begin() + _curr_length, _sort_func);
-		        // Pop the first element of the heap
+		        // Select the entering arc and remove it from the list
 		        _in_arc = _candidates[0];
 		        _next_arc = e;
 		        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                  _sort_func );
-		        _curr_length = std::min(_head_length, _curr_length - 1);
+		        _candidates[0] = _candidates[new_length - 1];
 		        _curr_length = new_length - 1;
 		        return true;
+		      }
 		    }; //class AlteringListPivotRule
 		  public:

0 comments (0 inline)

RhodeCode

Login to your account