LEMON/LEMON-official Changeset - r774:cab85bd7859b

Repositories » LEMON » LEMON-official

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

Changeset - r774:cab85bd7859b

« 727:257e91

775:e2bdd1 »

r774:cab85bd7859b

Wed, 01 Jul 2009 16:34:01

[Not Reviewed]

0 comments (0 inline)

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

Small improvements in NS pivot rules (#298)

0 1 0

default

1 file changed with 26 insertions and 34 deletions:

lemon/network_simplex.h

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -363,35 +363,34 @@
 		      // Find next entering arc
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
 		        int cnt = _block_size;
-		        int e, min_arc = _next_arc;
 		        int e;
 		        for (e = _next_arc; e < _search_arc_num; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
-		            min_arc = e;
+		            _in_arc = e;
+		          }
 		          if (--cnt == 0) {
-		            if (min < 0) break;
+		            if (min < 0) goto search_end;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (min == 0 || cnt > 0) {
 		          for (e = 0; e < _next_arc; ++e) {
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
-		              min_arc = e;
+		            _in_arc = e;
+		            }
 		            if (--cnt == 0) {
-		              if (min < 0) break;
+		            if (min < 0) goto search_end;
 		              cnt = _block_size;
+		            }
+		          }
+		        }
 		        if (min >= 0) return false;
-		        _in_arc = min_arc;
 		      search_end:
 		        _next_arc = e;
 		        return true;
+		      }
@@ -427,9 +426,9 @@
 		        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
 		        _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
-		        const double LIST_LENGTH_FACTOR = 1.0;
+		        const double LIST_LENGTH_FACTOR = 0.25;
 		        const int MIN_LIST_LENGTH = 10;
 		        const double MINOR_LIMIT_FACTOR = 0.1;
 		        const int MIN_MINOR_LIMIT = 3;
@@ -444,9 +443,9 @@
 		      /// Find next entering arc
 		      bool findEnteringArc() {
 		        Cost min, c;
-		        int e, min_arc = _next_arc;
 		        int e;
 		        if (_curr_length > 0 && _minor_count < _minor_limit) {
 		          // Minor iteration: select the best eligible arc from the
 		          // current candidate list
 		          ++_minor_count;
@@ -455,18 +454,15 @@
 		            e = _candidates[i];
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
-		              min_arc = e;
+		              _in_arc = e;
+		            }
 		            if (c >= 0) {
+		            else if (c >= 0) {
 		              _candidates[i--] = _candidates[--_curr_length];
+		            }
+		          }
 		          if (min < 0) {
 		            _in_arc = min_arc;
 		            return true;
+		          }
 		          if (min < 0) return true;
+		        }
 		        // Major iteration: build a new candidate list
 		        min = 0;
@@ -476,29 +472,28 @@
 		          if (c < 0) {
 		            _candidates[_curr_length++] = e;
 		            if (c < min) {
 		              min = c;
-		              min_arc = e;
+		              _in_arc = e;
+		            }
-		            if (_curr_length == _list_length) break;
+		            if (_curr_length == _list_length) goto search_end;
+		          }
+		        }
 		        if (_curr_length < _list_length) {
 		          for (e = 0; e < _next_arc; ++e) {
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < 0) {
 		              _candidates[_curr_length++] = e;
 		              if (c < min) {
 		                min = c;
-		                min_arc = e;
+		              _in_arc = e;
+		              }
 		              if (_curr_length == _list_length) break;
+		            }
 		            if (_curr_length == _list_length) goto search_end;
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        _minor_count = 1;
 		        _in_arc = min_arc;
 		        _next_arc = e;
 		        return true;
+		      }
@@ -548,9 +543,9 @@
 		        _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.5;
+		        const double BLOCK_SIZE_FACTOR = 1.0;
 		        const int MIN_BLOCK_SIZE = 10;
 		        const double HEAD_LENGTH_FACTOR = 0.1;
 		        const int MIN_HEAD_LENGTH = 3;
@@ -577,48 +572,45 @@
+		        }
 		        // Extend the list
 		        int cnt = _block_size;
 		        int last_arc = 0;
 		        int limit = _head_length;
-		        for (int e = _next_arc; e < _search_arc_num; ++e) {
 		        for (e = _next_arc; e < _search_arc_num; ++e) {
 		          _cand_cost[e] = _state[e] *
 		            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (_cand_cost[e] < 0) {
 		            _candidates[_curr_length++] = e;
 		            last_arc = e;
+		          }
 		          if (--cnt == 0) {
-		            if (_curr_length > limit) break;
+		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
+		        }
 		        if (_curr_length <= limit) {
 		          for (int e = 0; e < _next_arc; ++e) {
 		        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) {
 		              _candidates[_curr_length++] = e;
 		              last_arc = e;
+		            }
 		            if (--cnt == 0) {
-		              if (_curr_length > limit) break;
+		            if (_curr_length > limit) goto search_end;
 		              limit = 0;
 		              cnt = _block_size;
+		            }
+		          }
+		        }
 		        if (_curr_length == 0) return false;
-		        _next_arc = last_arc + 1;
 		      search_end:
 		        // Make heap of the candidate list (approximating a partial sort)
 		        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                   _sort_func );
 		        // Pop the first element of the heap
 		        _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);
 		        return true;

0 comments (0 inline)

RhodeCode

Login to your account