algorithm - 将旅行商表示为线性表达式

Question

我在网上看到有人可以将旅行商问题写成一个线性表达式，然后使用 CPLEX for java 等软件对其进行计算。

我有 1000 个城镇，需要找到一个短距离。我计划将这 1000 个城镇划分为大约 100 个城镇的集群，并对这些单独的集群执行一些线性规划算法。

我的问题是，我该如何将其准确表示为线性表达式。

所以我有 100 个城镇，我相信每个人都知道 TSP 的运作方式。

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

有人可以向我解释这是如何完成的，或者给我发送一个链接来清楚地解释它，因为我已经进行了很多研究，但似乎找不到任何东西。

编辑:

我发现的一些额外信息:

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

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

约束是:

i) 每个城市都是从另一个城市到达的

ii) 从每个城市出发到另一个城市

iii) 这条路线没有分成单独的岛屿。

同样，这对我来说完全有意义，但我仍然无法将这些约束写成线性表达式。显然这是一个足够简单的矩阵。

感谢您的帮助!

Answer 1

根据这个Wikipedia article旅行商问题可以建模为一个整数 线性程序，我认为这是问题的关键问题。这个想法是在 {0,1} 中有允许值的决策变量，它对图中选择的边进行建模。合适的约束必须确保所选边覆盖每个节点，所选边形成一组循环并且只有一个连通分量(这总共意味着恰好有一个循环包含每个节点)。请注意，该文章还给出了明确的公式并解释了约束的解释。

由于旅行商问题是NP-hard，除非P=NP，否则无法通过(非积分)线性规划求解。