I am trying to use Concorde to solve some asymmetric instances of the TSP. Although the official website says Concorde does solve this kind of instances, I've seen people saying it doesn't (https://cs.stackexchange.com/a/16336, http://www.math.uwaterloo.ca/tsp/road/austria.html). I'm only doubting the official website because I have the following test instance:
NAME: test
TYPE: ATSP
DIMENSION: 4
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTION
999 | 2 | 2 | 2
2 |999| 2 | 2
2 | 2 |999| 2
2 | 2 | 2 |999
EOF
Concorde gives me, as expected:
Optimal Solution: 8.00
and on the .sol file, the route: 0 1 3 2.
But if I change the matrix to:
EDGE_WEIGHT_SECTION
999 |100| 3 |100
2 |999| 2 | 2
2 | 2 |999| 2
2 | 2 | 2 |999
EOF
The solution given now is 106 with the sequence 0 3 1 2. No matter what numbers I put in the first row, Concorde never chooses the third city (index 2, value 3).
Does anybody have any idea why that is? Am I reading the input wrong?
--EDIT--
Actually, the instances for the ATSP problem are NOT from the official website. It's from this one:
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
Because the name of this library is TSPLIB (the same as the official set of problems for Concorde) I made this confusion. I'm not sure how this TSPLIB95 is related with Concorde Solver (or if it is related whatsoever).
Concorde is only for symmetric TSP. You'll have to do the standard trick to convert an ATSP into a symmetric TSP (with additional nodes).