代表旅行推销员作为线性表达

Question

我在网上看到,人们可以将旅行商问题写成线性表达式,并使用CPLEX for java等软件进行计算.

我有1000个城镇,需要找一小段距离.我计划将这1000个城镇划分为约100个城镇的集群,并在这些单独的集群上执行一些线性规划算法.

我的问题是,我究竟如何将其表示为线性表达式.

所以我有100个城镇,我相信每个人都知道TSP是如何工作的.

我完全不知道如何编写满足TSP的线性约束,目标和变量.

有人可以向我解释这是如何完成的,或者给我一个清楚解释它的链接,因为我一直在研究很多,似乎找不到任何东西.

编辑:

我找到了一些额外的信息:

我们用数字0到n标记城市并定义矩阵:

这会为5个城镇产生以下矩阵吗？

限制是:

i)每个城市都来自其他城市

ii)从每个城市出发前往另一个城市

iii)该路线不会分成不同的岛屿.

同样,这对我来说是完全合理的,但我仍然无法将这些约束写为线性表达式.显然它是一个简单的矩阵.

谢谢你的帮助 !

Answer 1

根据这篇维基百科文章，旅行商问题可以建模为整数线性程序，我认为这是该问题的关键问题。这个想法是拥有允许值的决策变量，其中{0,1}模型选择图中的边。适当的约束必须确保所选边覆盖每个节点，所选边形成循环的集合，并且只有一个连通分量（这总共意味着存在一个包含每个节点的循环）。请注意，本文还给出了明确的表述并解释了约束的解释。

由于旅行商问题是NP困难的，因此不能通过（非积分）线性规划来解决，除非P=NP。