我在网上看到，人们可以将旅行商问题写为线性表达式，并使用CPLEX for Java之类的软件对其进行计算。
我有1000个城镇，需要寻找一小段距离。我计划将这1000个城镇划分为约100个城镇的集群，并对这些单个集群执行一些线性编程算法。
我的问题是，如何准确地将其表示为线性表达式。
因此，我有100个城镇，我敢肯定，每个人都知道TSP的运作方式。
我实际上不知道如何编写满足TSP的线性约束，目标和变量。
有人可以向我解释这是如何完成的，或者可以给我发送一个链接来清楚地说明这一点，因为我一直在研究很多，而且似乎找不到任何东西。
编辑:
我发现了一些额外的信息:
我们用数字0到n标记城市并定义矩阵:
这样会得出以下5个镇的矩阵吗？
约束是:
i)每个城市都恰好是另一个城市
ii)每个城市都有一个确切的出发地
iii)路线没有分成多个单独的岛屿。
同样，这对我来说完全有意义，但是我仍然很难将这些约束作为线性表达式编写。显然，这是一个足够简单的矩阵。
谢谢你的帮助 !
最佳答案
根据这个Wikipedia article，可以将旅行商问题建模为整数线性程序，我认为这是该问题的关键问题。想法是在{0,1}中具有允许值的决策变量，以对图形中的选定边进行建模。适当的约束条件必须确保选定的边覆盖每个节点，选定的边形成一个循环的集合，并且只有一个连接的组件(总的来说，恰好有一个循环包含每个节点)。请注意，本文还给出了明确的表述并解释了约束的解释。
由于旅行商问题是NP-hard，因此，除非使用P=NP，否则无法通过(非整数)线性规划解决该问题。
关于algorithm - 将旅行推销员表示为线性表达式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29917133/