Comparing different implementations of Branch and Bound Method
Optimer library is used as reference implementation.
The results of the reference implementation are presented in the third column “time (s.)”. Results of other implementations are presented in columns with names “(n)”, where n is a reference number of the implementation. Please see below the table to get the full list of the implementations.
| Problem | # of cities | time (s.) | # of cores | (1) | (2) | (3) | (3) - Concorde | (4) | (5) |
|---|---|---|---|---|---|---|---|---|---|
| br17 | 17 | 2.891 | 8 | 3 | 4.18 | – | – | 6.937 | 1256.524 |
| ft53 | 53 | 57.136 | 8 | – | 2.53 | 0.44 | 0.27 | – | – |
| ft70 | 70 | 0.078 | 2 | – | 1.87 | 1.51 | – | – | 147.265 |
| ftv33 | 34 | 0.004 | 4 | – | 0.11 | 0.01 | – | 3.94 | 0.156 |
| ftv35 | 36 | 0.007 | 8 | – | 0.22 | 0.46 | – | 97.425 | 0.031 |
| ftv38 | 39 | 0.012 | 8 | – | 0.22 | 0.51 | – | 382.958 | 0.031 |
| ftv44 | 45 | 0.008 | 4 | – | 0.05 | 0.06 | – | – | 0.078 |
| ftv47 | 48 | 0.041 | 8 | – | 1.37 | 2.07 | – | – | 0.406 |
| ftv55 | 56 | 0.347 | 8 | 6 | 4.56 | 10.59 | – | – | 2.437 |
| ftv64 | 65 | 0.191 | 8 | – | 3.24 | 1.56 | 30.21 | – | 1.984 |
| ftv70 | 71 | 0.301 | 8 | 9 | 8.57 | 4.89 | 8.43 | – | 8.203 |
| ftv90 | 91 | 0.077 | 8 | – | 1.54 | – | – | – | 1.484 |
| ftv100 | 101 | 0.975 | 8 | – | 21.87 | – | – | – | – |
| ftv110 | 111 | 1.291 | 8 | – | 89.56 | – | – | – | – |
| ftv120 | 121 | 8.453 | 8 | – | 305.71 | – | – | – | – |
| ftv130 | 131 | 0.421 | 8 | – | 19.01 | – | – | – | 114.265 |
| ftv140 | 141 | 0.756 | 8 | – | 13.3 | – | – | – | 108.375 |
| ftv150 | 151 | 0.402 | 8 | – | 4.67 | – | – | – | 132.078 |
| ftv160 | 161 | 8.328 | 8 | – | 496.92 | – | – | – | 3771.093 |
| ftv170 | 171 | 39.827 | 8 | 480 | 656.59 | – | – | – | – |
| kro124p | 100 | 219.555 | 8 | – | Not | 1000+ | 5.61 | – | 3505.406 |
| rbg323 | 323 | 0.306 | 2 | – | 0 | – | – | 0.034 | 2.968 |
| rbg358 | 358 | 0.393 | 2 | – | 0 | 0.03 | – | 0.042 | 7.328 |
| rbg403 | 403 | 0.602 | 2 | – | 0.05 | – | 847.1 | 0.079 | 5.484 |
| rbg443 | 443 | 0.734 | 2 | – | 0.05 | 0.05 | 81.62 | 0.079 | 3.578 |
| ry48p | 48 | 15.908 | 8 | – | 105.88 | 77.35 | 11.39 | – | 54.406 |
| p43 | 43 | 2280* | 8 | 4800 | Not | – | – | – | – |
(1) AV Tyulenev, Application of integer linear programming with sequential elimination of cycles to solve the traveling salesman problem. 2012 (2) Marcel Turkensteen, Diptesh Ghosh, Boris Goldengorin, Gerard Sierksma. Tolerance-based Branch and Bound algorithms for the ATSP. 2008. (3) Remco Germs, Boris Goldengorin, Marcel Turkenstee. Lower tolerance-based Branch and Bound algorithms for the ATSP. 2012 (4) Pessoa, Tiago Carneiro. Estratégias paralelas inteligentes para o método branch-and- bound aplicadas ao problema do caixeiro viajante assimétrico. 2012. (5) IF Borhanov, VR Fazylov, “Little’s method with optimal matrix reduction”, Physics and mathematics, Cat. App. Kazan. State. University. Ser. Phys.-Math. Science, 148, No. 4, Kazan Univ., Kazan, 2006, 13-22