362 |
362 |
363 // Find next entering arc |
363 // Find next entering arc |
364 bool findEnteringArc() { |
364 bool findEnteringArc() { |
365 Cost c, min = 0; |
365 Cost c, min = 0; |
366 int cnt = _block_size; |
366 int cnt = _block_size; |
367 int e, min_arc = _next_arc; |
367 int e; |
368 for (e = _next_arc; e < _search_arc_num; ++e) { |
368 for (e = _next_arc; e < _search_arc_num; ++e) { |
369 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
369 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
370 if (c < min) { |
370 if (c < min) { |
371 min = c; |
371 min = c; |
372 min_arc = e; |
372 _in_arc = e; |
373 } |
373 } |
374 if (--cnt == 0) { |
374 if (--cnt == 0) { |
375 if (min < 0) break; |
375 if (min < 0) goto search_end; |
376 cnt = _block_size; |
376 cnt = _block_size; |
377 } |
377 } |
378 } |
378 } |
379 if (min == 0 || cnt > 0) { |
379 for (e = 0; e < _next_arc; ++e) { |
380 for (e = 0; e < _next_arc; ++e) { |
380 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
381 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
381 if (c < min) { |
382 if (c < min) { |
382 min = c; |
383 min = c; |
383 _in_arc = e; |
384 min_arc = e; |
384 } |
385 } |
385 if (--cnt == 0) { |
386 if (--cnt == 0) { |
386 if (min < 0) goto search_end; |
387 if (min < 0) break; |
387 cnt = _block_size; |
388 cnt = _block_size; |
|
389 } |
|
390 } |
388 } |
391 } |
389 } |
392 if (min >= 0) return false; |
390 if (min >= 0) return false; |
393 _in_arc = min_arc; |
391 |
|
392 search_end: |
394 _next_arc = e; |
393 _next_arc = e; |
395 return true; |
394 return true; |
396 } |
395 } |
397 |
396 |
398 }; //class BlockSearchPivotRule |
397 }; //class BlockSearchPivotRule |
426 _cost(ns._cost), _state(ns._state), _pi(ns._pi), |
425 _cost(ns._cost), _state(ns._state), _pi(ns._pi), |
427 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), |
426 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), |
428 _next_arc(0) |
427 _next_arc(0) |
429 { |
428 { |
430 // The main parameters of the pivot rule |
429 // The main parameters of the pivot rule |
431 const double LIST_LENGTH_FACTOR = 1.0; |
430 const double LIST_LENGTH_FACTOR = 0.25; |
432 const int MIN_LIST_LENGTH = 10; |
431 const int MIN_LIST_LENGTH = 10; |
433 const double MINOR_LIMIT_FACTOR = 0.1; |
432 const double MINOR_LIMIT_FACTOR = 0.1; |
434 const int MIN_MINOR_LIMIT = 3; |
433 const int MIN_MINOR_LIMIT = 3; |
435 |
434 |
436 _list_length = std::max( int(LIST_LENGTH_FACTOR * |
435 _list_length = std::max( int(LIST_LENGTH_FACTOR * |
443 } |
442 } |
444 |
443 |
445 /// Find next entering arc |
444 /// Find next entering arc |
446 bool findEnteringArc() { |
445 bool findEnteringArc() { |
447 Cost min, c; |
446 Cost min, c; |
448 int e, min_arc = _next_arc; |
447 int e; |
449 if (_curr_length > 0 && _minor_count < _minor_limit) { |
448 if (_curr_length > 0 && _minor_count < _minor_limit) { |
450 // Minor iteration: select the best eligible arc from the |
449 // Minor iteration: select the best eligible arc from the |
451 // current candidate list |
450 // current candidate list |
452 ++_minor_count; |
451 ++_minor_count; |
453 min = 0; |
452 min = 0; |
454 for (int i = 0; i < _curr_length; ++i) { |
453 for (int i = 0; i < _curr_length; ++i) { |
455 e = _candidates[i]; |
454 e = _candidates[i]; |
456 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
455 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
457 if (c < min) { |
456 if (c < min) { |
458 min = c; |
457 min = c; |
459 min_arc = e; |
458 _in_arc = e; |
460 } |
459 } |
461 if (c >= 0) { |
460 else if (c >= 0) { |
462 _candidates[i--] = _candidates[--_curr_length]; |
461 _candidates[i--] = _candidates[--_curr_length]; |
463 } |
462 } |
464 } |
463 } |
465 if (min < 0) { |
464 if (min < 0) return true; |
466 _in_arc = min_arc; |
|
467 return true; |
|
468 } |
|
469 } |
465 } |
470 |
466 |
471 // Major iteration: build a new candidate list |
467 // Major iteration: build a new candidate list |
472 min = 0; |
468 min = 0; |
473 _curr_length = 0; |
469 _curr_length = 0; |
475 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
471 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
476 if (c < 0) { |
472 if (c < 0) { |
477 _candidates[_curr_length++] = e; |
473 _candidates[_curr_length++] = e; |
478 if (c < min) { |
474 if (c < min) { |
479 min = c; |
475 min = c; |
480 min_arc = e; |
476 _in_arc = e; |
481 } |
477 } |
482 if (_curr_length == _list_length) break; |
478 if (_curr_length == _list_length) goto search_end; |
483 } |
479 } |
484 } |
480 } |
485 if (_curr_length < _list_length) { |
481 for (e = 0; e < _next_arc; ++e) { |
486 for (e = 0; e < _next_arc; ++e) { |
482 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
487 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
483 if (c < 0) { |
488 if (c < 0) { |
484 _candidates[_curr_length++] = e; |
489 _candidates[_curr_length++] = e; |
485 if (c < min) { |
490 if (c < min) { |
486 min = c; |
491 min = c; |
487 _in_arc = e; |
492 min_arc = e; |
|
493 } |
|
494 if (_curr_length == _list_length) break; |
|
495 } |
488 } |
|
489 if (_curr_length == _list_length) goto search_end; |
496 } |
490 } |
497 } |
491 } |
498 if (_curr_length == 0) return false; |
492 if (_curr_length == 0) return false; |
|
493 |
|
494 search_end: |
499 _minor_count = 1; |
495 _minor_count = 1; |
500 _in_arc = min_arc; |
|
501 _next_arc = e; |
496 _next_arc = e; |
502 return true; |
497 return true; |
503 } |
498 } |
504 |
499 |
505 }; //class CandidateListPivotRule |
500 }; //class CandidateListPivotRule |
547 _cost(ns._cost), _state(ns._state), _pi(ns._pi), |
542 _cost(ns._cost), _state(ns._state), _pi(ns._pi), |
548 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), |
543 _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), |
549 _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost) |
544 _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost) |
550 { |
545 { |
551 // The main parameters of the pivot rule |
546 // The main parameters of the pivot rule |
552 const double BLOCK_SIZE_FACTOR = 1.5; |
547 const double BLOCK_SIZE_FACTOR = 1.0; |
553 const int MIN_BLOCK_SIZE = 10; |
548 const int MIN_BLOCK_SIZE = 10; |
554 const double HEAD_LENGTH_FACTOR = 0.1; |
549 const double HEAD_LENGTH_FACTOR = 0.1; |
555 const int MIN_HEAD_LENGTH = 3; |
550 const int MIN_HEAD_LENGTH = 3; |
556 |
551 |
557 _block_size = std::max( int(BLOCK_SIZE_FACTOR * |
552 _block_size = std::max( int(BLOCK_SIZE_FACTOR * |
576 } |
571 } |
577 } |
572 } |
578 |
573 |
579 // Extend the list |
574 // Extend the list |
580 int cnt = _block_size; |
575 int cnt = _block_size; |
581 int last_arc = 0; |
|
582 int limit = _head_length; |
576 int limit = _head_length; |
583 |
577 |
584 for (int e = _next_arc; e < _search_arc_num; ++e) { |
578 for (e = _next_arc; e < _search_arc_num; ++e) { |
585 _cand_cost[e] = _state[e] * |
579 _cand_cost[e] = _state[e] * |
586 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
580 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
587 if (_cand_cost[e] < 0) { |
581 if (_cand_cost[e] < 0) { |
588 _candidates[_curr_length++] = e; |
582 _candidates[_curr_length++] = e; |
589 last_arc = e; |
|
590 } |
583 } |
591 if (--cnt == 0) { |
584 if (--cnt == 0) { |
592 if (_curr_length > limit) break; |
585 if (_curr_length > limit) goto search_end; |
593 limit = 0; |
586 limit = 0; |
594 cnt = _block_size; |
587 cnt = _block_size; |
595 } |
588 } |
596 } |
589 } |
597 if (_curr_length <= limit) { |
590 for (e = 0; e < _next_arc; ++e) { |
598 for (int e = 0; e < _next_arc; ++e) { |
591 _cand_cost[e] = _state[e] * |
599 _cand_cost[e] = _state[e] * |
592 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
600 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
593 if (_cand_cost[e] < 0) { |
601 if (_cand_cost[e] < 0) { |
594 _candidates[_curr_length++] = e; |
602 _candidates[_curr_length++] = e; |
595 } |
603 last_arc = e; |
596 if (--cnt == 0) { |
604 } |
597 if (_curr_length > limit) goto search_end; |
605 if (--cnt == 0) { |
598 limit = 0; |
606 if (_curr_length > limit) break; |
599 cnt = _block_size; |
607 limit = 0; |
|
608 cnt = _block_size; |
|
609 } |
|
610 } |
600 } |
611 } |
601 } |
612 if (_curr_length == 0) return false; |
602 if (_curr_length == 0) return false; |
613 _next_arc = last_arc + 1; |
603 |
|
604 search_end: |
614 |
605 |
615 // Make heap of the candidate list (approximating a partial sort) |
606 // Make heap of the candidate list (approximating a partial sort) |
616 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, |
607 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, |
617 _sort_func ); |
608 _sort_func ); |
618 |
609 |
619 // Pop the first element of the heap |
610 // Pop the first element of the heap |
620 _in_arc = _candidates[0]; |
611 _in_arc = _candidates[0]; |
|
612 _next_arc = e; |
621 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, |
613 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, |
622 _sort_func ); |
614 _sort_func ); |
623 _curr_length = std::min(_head_length, _curr_length - 1); |
615 _curr_length = std::min(_head_length, _curr_length - 1); |
624 return true; |
616 return true; |
625 } |
617 } |