5
$\begingroup$

Concorde is a well-known exact solver for instances of the traveling salesman problem. It can also be used to solve asymmetric TSPs, if the user implements a trick to convert ATSP to TSP.

However, if the problem size is large enough, the resulting weights can be very large. A paper on the railway TSP says the following:

For the symmetric TSP transformation, we still have some implementation-dependent problems with the big $M$ and $M'$ added to the edges costs. Trying to solve instances where the salesman visits 15 cities results in integer over- flows and the branch-and-cut algorithm can only operate with integer values. Therefore, we would like to enhance the transformation procedure to overcome this difficulty.

This can be easily empirically verified, as here is the Concorde output in such a case:

Using random seed 1653068890
Problem Name: amtrak
Problem Type: TSP
Number of Nodes: 5192
Explicit Lengths (CC_MATRIXNORM)
Set initial upperbound to 1599011938 (from tour)
  LP Value  1: 1598949533.191495  (19.84 seconds)
  LP Value  2: 1598950007.500001  (22.02 seconds)
New lower bound: 1598950007.499611
  LP Value  1: 1598950007.500002  (23.67 seconds)
New upperbound from x-heuristic: 1598999315.00
Final lower bound 1598950007.499611, upper bound 1598999315.000000
OVERFLOW in CCbigguy_addmult (4)
BIGGUY errors are fatal
FATAL ERROR - received signal SIGABRT (6/6)
sleeping 1 more hours to permit debugger access

My first thought is that this is really nothing more than an implementation issue, as I don't see a reason why numerical values in Concorde have to be stored as a specific data type. So, is there any TSP solver out there similar to Concorde that can handle such large values?

I am not interested in workarounds such as "just scale your values down" as this results in a loss of precision, and if one is using Concorde to begin with then it is clear an exact precise optimal result is desired.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.