Concorde TSP 求解器 - 非对称实例
Concorde TSP Solver - Asymmetric Instances
我正在尝试使用 Concorde 来解决 TSP 的一些不对称实例。虽然官网说协和确实解决了这种情况，但我看到有人说它没有（https://cs.stackexchange.com/a/16336, http://www.math.uwaterloo.ca/tsp/road/austria.html）。我只是怀疑官方网站，因为我有以下测试实例：
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
协和给了我，如我所料：
最优解：8.00
在 .sol 文件中，路由：0 1 3 2.
但是如果我将矩阵更改为：
EDGE_WEIGHT_SECTION
999 |100| 3 |100
2 |999| 2 | 2
2 | 2 |999| 2
2 | 2 | 2 |999
EOF
现在给出的解是106，序列为0 3 1 2。
无论我在第一行输入什么数字，协和都不会选择第三个城市（索引 2，值 3）。
有人知道这是为什么吗？我读错了吗？
--编辑--
实际上，ATSP 问题的实例并非来自官方网站。它来自这个：
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
因为这个库的名字是TSPLIB（和Concorde的官方题集一样）所以造成了这个混淆。我不确定这个 TSPLIB95 与 Concorde Solver 有什么关系（或者它是否有任何关系）。
Concorde 仅适用于对称 TSP。您必须执行标准技巧才能将 ATSP 转换为对称 TSP（具有附加节点）。
我正在尝试使用 Concorde 来解决 TSP 的一些不对称实例。虽然官网说协和确实解决了这种情况，但我看到有人说它没有（https://cs.stackexchange.com/a/16336, http://www.math.uwaterloo.ca/tsp/road/austria.html）。我只是怀疑官方网站，因为我有以下测试实例：
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
协和给了我，如我所料：
最优解：8.00
在 .sol 文件中，路由：0 1 3 2.
但是如果我将矩阵更改为：
EDGE_WEIGHT_SECTION
999 |100| 3 |100
2 |999| 2 | 2
2 | 2 |999| 2
2 | 2 | 2 |999
EOF
现在给出的解是106，序列为0 3 1 2。 无论我在第一行输入什么数字，协和都不会选择第三个城市（索引 2，值 3）。
有人知道这是为什么吗？我读错了吗？
--编辑--
实际上，ATSP 问题的实例并非来自官方网站。它来自这个：
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
因为这个库的名字是TSPLIB（和Concorde的官方题集一样）所以造成了这个混淆。我不确定这个 TSPLIB95 与 Concorde Solver 有什么关系（或者它是否有任何关系）。
Concorde 仅适用于对称 TSP。您必须执行标准技巧才能将 ATSP 转换为对称 TSP（具有附加节点）。