n | EX | optimal | DM | SM | GA | TTHM | Algorithm 3 | BAB |
100 | 1 | 759 | 764 | 774 | 774 | 1573 | 759 | x |
2 | 610 | 610 | 624 | 614 | 4327 | 624 | x | |
3 | 863 | 863 | 876 | 863 | 1000 | 872 | x | |
4 | 596 | 596 | 596 | 596 | 2834 | 596 | x | |
5 | 874 | 894 | 895 | 894 | 1868 | 874 | x | |
|
| No of opt. | 3 | 1 | 2 | 0 | 3 |
|
Av. time in Sec. | 0.3011 | 0.4940 | 0.2915 | 0.0597 | 0.0249 |
| ||
500 | 1 | 2889 | 2903 | 2903 | 2902 | 11,154 | 2889 | x |
2 | 1566 | 1572 | 1572 | 1572 | 2262 | 1566 | x | |
3 | 1612 | 1617 | 1617 | 1612 | 4503 | 1617 | x | |
4 | 1979 | 1979 | 1989 | 1979 | 8486 | 1988 | x | |
5 | 1138 | 1139 | 1139 | 1139 | 3977 | 1138 | x | |
|
| No of opt. | 1 | 0 | 2 | 0 | 3 |
|
Av. time in Sec. | 0.6981 | 2.8196 | 0.6891 | 2.4845 | 0.0810 |
| ||
1000 | 1 | 2001 | 2001 | 2001 | 2001 | 2813 | 2001 | x |
2 | 2640 | 2648 | 2648 | 2648 | 29,837 | 2640 | x | |
3 | 1811 | 1811 | 1811 | 1811 | 1894 | 1811 | x | |
4 | 2678 | 2732 | 2732 | 2732 | 10,057 | 2678 | x | |
5 | 4013 | 4015 | 4015 | 4013 | 12,992 | 4013 | x | |
|
| No of opt. | 2 | 2 | 3 | 0 | 5 |
|
Av. time in Sec. | 1.2873 | 6.9351 | 1.2615 | 19.0697 | 0.17836 |
| ||
1500 | 1 | 2372 | 2376 | 2376 | 2376 | 34,793 | 2372 | x |
2 | 2734 | 2746 | 2746 | 2746 | 3885 | 2734 | x | |
3 | 2624 | 2651 | 2651 | 2651 | 36,126 | 2624 | x | |
4 | 3175 | 3202 | 3202 | 3202 | 13,788 | 3175 | x | |
5 | 2143 | 2164 | 2164 | 2164 | 23,346 | 2143 | x | |
|
| No of opt. | 0 | 0 | 0 | 0 | 5 |
|
Av. time in Sec. | 1.8198 | 13.5740 | 1.8171 | 51.8916 | 0.3083 |
| ||
2000 | 1 | 3518 | 3532 | 3531 | 3531 | 3531 | 3518 | x |
| 2 | 3601 | 3601 | 3602 | 3602 | 12,034 | 3602 | x |
| 3 | 2456 | 2468 | 2468 | 2468 | 8609 | 2456 | x |
| 4 | 2541 | 2567 | 2567 | 2567 | 20,922 | 2541 | x |
| 5 | 2720 | 2747 | 2747 | 2747 | 5000 | 2720 | x |
|
| No of opt. | 1 | 0 | 0 | 0 | 4 |
|
Av. time in Sec. | 2.2309 | 20.0777 | 2.4222 | 115.0507 | 0.4138 |
| ||
2500 | 1 | 3741 | 3755 | 3755 | 3755 | 70,285 | 3741 | x |
| 2 | 4151 | 4189 | 4189 | 4189 | 89,556 | 4151 | x |
| 3 | 3453 | 3455 | 3455 | 3455 | 32,784 | 3453 | x |
| 4 | 3387 | 3387 | 3387 | 3387 | 57,419 | 3387 | x |
| 5 | 3362 | 3398 | 3398 | 3398 | 7220 | 3362 | x |
|
| No of opt. | 1 | 1 | 1 | 0 | 5 |
|
Av. time in Sec. | 2.9920 | 30.9195 | 2.9153 | 245.7569 | 0.5907 |
| ||
3000 | 1 | 3374 | 3381 | 3381 | 3381 | 113,080 | 3374 | x |
| 2 | 3891 | 3925 | 3925 | 3925 | 82,982 | 3891 | x |
| 3 | 2760 | 2765 | 2765 | 2765 | 12,794 | 2760 | x |
| 4 | 5084 | 5086 | 5086 | 5086 | 22,620 | 5084 | x |
| 5 | 4106 | 4107 | 4107 | 4107 | 28,783 | 4106 | x |
|
| No of opt. | 0 | 0 | 0 | 0 | 5 |
|
Av. time in Sec. | 3.4263 | 40.9182 | 3.4889 | 393.2098 | 0.7786 |
| ||
3500 | 1 | 5327 | 5361 | 5361 | 5361 | 17,022 | 5327 | x |
| 2 | 4774 | 4780 | 4780 | 4780 | 21,512 | 4774 | x |
| 3 | 3025 | 3025 | 3025 | 3025 | 4200 | 3025 | x |
| 4 | 3053 | 3053 | 3053 | 3053 | 64,133 | 3053 | x |
| 5 | 2853 | 2872 | 2872 | 2872 | 31,780 | 2853 | x |
|
| No of opt. | 2 | 2 | 2 | 0 | 5 |
|
Av. time in Sec. | 4.9491 | 55.2326 | 4.9758 | 847.2746 | 1.2653 |
| ||
4000 | 1 | 6124 | 6147 | 6147 | 6147 | 6147 | 6124 | x |
| 2 | 4196 | 4202 | 4202 | 4202 | 106,519 | 4196 | x |
| 3 | 4453 | 4499 | 4499 | 4499 | 5350 | 4453 | x |
| 4 | 4693 | 4694 | 4694 | 4694 | 107,738 | 4693 | x |
| 5 | 7584 | 7589 | 7589 | 7589 | 59,895 | 7584 | x |
|
| No of opt. | 0 | 0 | 0 | 0 | 5 |
|
Av. time in Sec. | 5.4975 | 68.4537 | 5.5505 | 1201.5244 | 1.5200 |
| ||
4500 | 1 | 4758 | 4760 | 4760 | 4760 | 39,727 | 4758 | x |
2 | 4867 | 4874 | 4874 | 4874 | 5933 | 4867 | x | |
3 | 3921 | 3929 | 3929 | 3929 | 36,110 | 3921 | x | |
4 | 5577 | 5579 | 5579 | 5579 | 77,961 | 5577 | x | |
5 | 4416 | 4418 | 4418 | 4418 | 51,170 | 4416 | x | |
|
| No of opt. | 0 | 0 | 0 | 0 | 5 |
|
Av. time in Sec. | 5.8256 | 81.7492 | 8.8406 | 1691.8303 | 2.2209 |
| ||
5000 | 1 | 7452 | 7452 | 7452 | 7452 | 27,028 | 7452 | x |
2 | 6479 | 6479 | 6479 | 6479 | 81,149 | 6479 | x | |
3 | 4704 | 4704 | 4704 | 4704 | 35,999 | 4704 | x | |
4 | 8576 | 8612 | 8612 | 8612 | 94,709 | 8576 | x | |
5 | 7834 | 7834 | 7834 | 7834 | 159,234 | 7834 | x | |
|
| No of opt. | 4 | 4 | 4 | 0 | 5 |
|
Av. time in Sec. | 6.3790 | 96.7463 | 6.8763 | 2351.9938 | 2.5285 |
|