Lower bounds

We also keep track of the best lower bound for each instance, and consider an instance solved when its lower bound matches its best tour. However, lower bounds are hard to check, since they don't come with easily verified certificates. When reporting lower bounds, describe the method used to establish the bound. Lower bounds which exceed the best tour for the instance will be discarded.

• USA Complete
  1. (Size 10) 10 days 17 hours 43 minutes - Branch and Bound
  2. (Size 12) 10 days 16 hours 57 minutes - Branch and Bound
  3. (Size 15) 12 days 6 hours 32 minutes - Branch and Bound
  4. (Size 20) 12 days 7 hours 0 minutes - Branch and Bound
• USA Sparse
  1. (Size 25) 14 days 15 hours 31 minutes -subtour
  2. (Size 30) 11 days 13 hours 46 minutes - subtour
  3. (Size 35) 14 days 15 hours 47 minutes - subtour
  4. (Size 40) 12 days 22 hours 42 minutes - subtour
  5. (Size 45) 13 days 13 hours 9 minutes
  6. (Size 50) 14 days 5 hours 36 minutes
  7. (Size 60) 13 days 22 hours 32 minutes
  8. (Size 80) 14 days 1 hour 3 minutes
  9. (Size 100) 14 days 0 hours 53 minutes
  10. (Size 128) 13 days 21 hours 1 minute
• UK Sparse
  1. (Size 25) 7 days 10 hours 0 minutes - B&B
  2. (Size 50) 7 days 4 hours 54 minutes
  3. (Size 75) 7 days 22 hours 1 minute
  4. (Size 100) 8 days 4 hours 43 minutes
  5. (Size 150) 8 days 5 hours 42 minutes
  6. (Size 200) 8 days 0 hours 34 minutes
  7. (Size 284) 8 days 19 hours 51 minutes
• Meshes
  1. (Size 9) 8 days 23 hours 21 minutes - Branch and Bound
  2. (Size 16) 8 days 23 hours 55 minutes - Branch and Bound
  3. (Size 25) 10 days 17 hours 8 minutes - Branch and Bound
  4. (Size 36) 9 days 3 hours 46 minutes - subtour
  5. (Size 49) 9 days 7 hours 3 minutes -subtour
  6. (Size 64) 9 days 17 hours 28 minutes
  7. (Size 81) 9 days 23 hours 40 minutes
  8. (Size 100) 10 days 2 hours 44 minutes
• Triangles
  1. (Size 6) 6 days 7 hours 3 minutes - Branch and Bound
  2. (Size 10) 7 days 5 hours 34 minutes - Branch and Bound
  3. (Size 15) 8 days 19 hours 19 minutes - Branch and Bound
  4. (Size 21) 9 days 20 hours 13 minutes - Branch and Bound
  5. (Size 28) 8 days 0 hours 49 minutes - subtour
  6. (Size 36) 8 days 13 hours 31 minutes - subtour
  7. (Size 45) 9 days 10 hours 15 minutes
  8. (Size 55) 10 days 12 hours 2 minutes
  9. (Size 66) 10 days 17 hours 29 minutes
  10. (Size 78) 9 days 14 hours 53 minutes
• South India
  1. (Size 18)3 days 5 hours 20 minutes - subtour (optimal)
  2. (Size 25) 7 days 11 hours 40 minutes - subtour (optimal)
  3. (Size 36) 8 days 11 hours 40 minutes -subtour
  4. (Size 49) 12 days 11 hours 45 minutes - subtour
  5. (Size 66) 9 days 11 hours 45 minutes - subtour
  6. (Size 75) 9 days 21 hours 15 minutes