Changeset - r1136:fcb6ad1e67d0
« 1132:48e173
1138:c8896b »
gravatar
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
23
20
↑ Collapse diff ↑
lemon/network_simplex.h
Ignore white space 6 line context
... ... 
@@ -122,14 +122,17 @@
122 122 
    /// Enum type containing constants for selecting the pivot rule for
123 123 
    /// the \ref run() function.
124 124 
    ///
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
127 127 
    /// 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.
133 136 
    enum PivotRule {
134 137 

			




	135
	138
	
		
      /// The \e First \e Eligible pivot rule.


			




	...
	...
	
		
@@ -155,7 +158,7 @@


			




	155
	158
	
		

			




	156
	159
	
		
      /// The \e Altering \e Candidate \e List pivot rule.


			




	157
	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
	162
	
		
      /// candidate list and extends this list in every iteration.


			




	160
	163
	
		
      ALTERING_LIST


			




	161
	164
	
		
    };


			




	...
	...
	
		
@@ -538,7 +541,7 @@


			




	538
	541
	
		
      public:


			




	539
	542
	
		
        SortFunc(const CostVector &map) : _map(map) {}


			




	540
	543
	
		
        bool operator()(int left, int right) {


			




	541
	
	
		
          return _map[left] > _map[right];


			




	
	544
	
		
          return _map[left] < _map[right];


			




	542
	545
	
		
        }


			




	543
	546
	
		
      };


			




	544
	547
	
		

			




	...
	...
	
		
@@ -556,7 +559,7 @@


			




	556
	559
	
		
        // The main parameters of the pivot rule


			




	557
	560
	
		
        const double BLOCK_SIZE_FACTOR = 1.0;


			




	558
	561
	
		
        const int MIN_BLOCK_SIZE = 10;


			




	559
	
	
		
        const double HEAD_LENGTH_FACTOR = 0.1;


			




	
	562
	
		
        const double HEAD_LENGTH_FACTOR = 0.01;


			




	560
	563
	
		
        const int MIN_HEAD_LENGTH = 3;


			




	561
	564
	
		

			




	562
	565
	
		
        _block_size = std::max( int(BLOCK_SIZE_FACTOR *


			




	...
	...
	
		
@@ -600,9 +603,9 @@


			




	600
	603
	
		
          }


			




	601
	604
	
		
        }


			




	602
	605
	
		
        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;


			




	606
	609
	
		
            _candidates[_curr_length++] = e;


			




	607
	610
	
		
          }


			




	608
	611
	
		
          if (--cnt == 0) {


			




	...
	...
	
		
@@ -615,16 +618,16 @@


			




	615
	618
	
		

			




	616
	619
	
		
      search_end:


			




	617
	620
	
		

			




	618
	
	
		
        // Make heap of the candidate list (approximating a partial sort)


			




	619
	
	
		
        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,


			




	620
	
	
		
                   _sort_func );


			




	
	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);


			




	621
	625
	
		

			




	622
	
	
		
        // Pop the first element of the heap


			




	
	626
	
		
        // Select the entering arc and remove it from the list


			




	623
	627
	
		
        _in_arc = _candidates[0];


			




	624
	628
	
		
        _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;


			




	628
	631
	
		
        return true;


			




	629
	632
	
		
      }


			




	630
	633
	
		

			




        

    






    
    



    


    

     
    
0 comments (0 inline)