二次有界TSP转化集群形式后，Concorde求解可行性咨询

核心结论 #

Concorde原生不支持直接处理二次TSP，你提到的节点拆分转化方案本质是试图将二次TSP映射为标准TSP，但转化逻辑存在关键缺陷，导致Concorde无法正常处理，并非单纯的参数设置错误。

转化方案的本质问题 #

你的思路是将原节点拆分为n个副本（对应从不同前驱节点到达该节点的状态），试图通过标准TSP的边成本间接表达三元依赖的二次成本f(i,j,k)，但存在以下致命矛盾：

• Concorde仅支持二元成本函数（即边(i,j)的成本仅依赖i和j两个节点），无法识别你定义的三元组合成本逻辑。你试图用无穷大成本约束路径合法性，但标准TSP的求解逻辑无法理解这种隐含的三元依赖规则，会导致成本矩阵出现逻辑冲突，触发参数异常。
• 节点拆分后，你需要强制每个原节点对应的集群仅被访问一次，但Concorde作为专用TSP求解器，原生不支持这类集群访问限制的约束，必须额外引入整数规划层面的约束，而Concorde无法处理这类扩展逻辑。

可行的替代方向 #

如果要继续用类似Concorde的TSP求解工具，需要调整转化策略：

• 仅当二次成本f(i,j,k)可拆解为可叠加的二元项（如f(i,j,k)=c(i,j)+d(j,k)）时，才能将其转化为标准TSP的边成本，适配Concorde的求解逻辑，但这种拆解仅适用于部分二次TSP场景。
• 改用支持路径依赖成本的通用优化求解器（如Gurobi、CPLEX），直接建模三元成本约束和集群访问限制，这类工具可以处理带扩展约束的TSP变种问题。

报错原因补充 #

你遇到的参数异常，大概率是因为构造的成本矩阵中存在大量无穷大值，导致Concorde的预处理模块（如Lin-Kernighan算法）无法处理非正定或逻辑矛盾的输入矩阵——这类专用TSP求解器对输入的合法性、合理性要求极高，无法识别隐含的约束逻辑。

内容的提问来源于stack exchange，提问作者Mr.X