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 47 insertions and 55 deletions:

lemon/network_simplex.h

↑ Collapse diff ↑

lemon/network_simplex.h

Show inline comments

@@ -366,3 +366,3 @@
 		        int cnt = _block_size;
-		        int e, min_arc = _next_arc;
 		        int e;
 		        for (e = _next_arc; e < _search_arc_num; ++e) {
@@ -371,6 +371,6 @@
 		            min = c;
-		            min_arc = e;
+		            _in_arc = e;
+		          }
 		          if (--cnt == 0) {
-		            if (min < 0) break;
+		            if (min < 0) goto search_end;
 		            cnt = _block_size;
@@ -378,13 +378,11 @@
+		        }
 		        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;
+		            }
 		            if (--cnt == 0) {
 		              if (min < 0) break;
 		              cnt = _block_size;
+		            }
+		        for (e = 0; e < _next_arc; ++e) {
 		          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		          if (c < min) {
 		            min = c;
 		            _in_arc = e;
+		          }
 		          if (--cnt == 0) {
 		            if (min < 0) goto search_end;
 		            cnt = _block_size;
+		          }
@@ -392,3 +390,4 @@
 		        if (min >= 0) return false;
-		        _in_arc = min_arc;
 		      search_end:
 		        _next_arc = e;
@@ -430,3 +429,3 @@
 		        // 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;
@@ -447,3 +446,3 @@
 		        Cost min, c;
-		        int e, min_arc = _next_arc;
 		        int e;
 		        if (_curr_length > 0 && _minor_count < _minor_limit) {
@@ -458,5 +457,5 @@
 		              min = c;
-		              min_arc = e;
+		              _in_arc = e;
+		            }
 		            if (c >= 0) {
+		            else if (c >= 0) {
 		              _candidates[i--] = _candidates[--_curr_length];
@@ -464,6 +463,3 @@
+		          }
 		          if (min < 0) {
 		            _in_arc = min_arc;
 		            return true;
+		          }
 		          if (min < 0) return true;
+		        }
@@ -479,18 +475,16 @@
 		              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;
+		              }
 		              if (_curr_length == _list_length) break;
 		        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;
 		              _in_arc = e;
+		            }
 		            if (_curr_length == _list_length) goto search_end;
+		          }
@@ -498,4 +492,5 @@
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        _minor_count = 1;
 		        _in_arc = min_arc;
 		        _next_arc = e;
@@ -551,3 +546,3 @@
 		        // 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;
@@ -580,6 +575,5 @@
 		        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] *
@@ -588,6 +582,5 @@
 		            _candidates[_curr_length++] = e;
 		            last_arc = e;
+		          }
 		          if (--cnt == 0) {
-		            if (_curr_length > limit) break;
+		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
@@ -596,15 +589,12 @@
+		        }
 		        if (_curr_length <= limit) {
 		          for (int 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;
 		              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) {
 		            _candidates[_curr_length++] = e;
+		          }
 		          if (--cnt == 0) {
 		            if (_curr_length > limit) goto search_end;
 		            limit = 0;
 		            cnt = _block_size;
+		          }
@@ -612,3 +602,4 @@
 		        if (_curr_length == 0) return false;
-		        _next_arc = last_arc + 1;
 		      search_end:
@@ -620,2 +611,3 @@
 		        _in_arc = _candidates[0];
 		        _next_arc = e;
 		        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,

0 comments (0 inline)

RhodeCode

Login to your account