将旅行商问题表示为线性表达式

Question

我在网上看到可以将旅行商问题表示为线性表达式，并使用诸如Java的CPLEX软件进行计算。

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

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

我有100个城镇，我相信每个人都知道TSP是如何工作的。

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

有人能向我解释这是如何完成的或向我发送一个清晰解释的链接吗？因为我已经做了很多研究，但似乎找不到任何东西。

编辑：

我发现了一些额外的信息：

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

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

这些约束条件是：

i）每个城市都只能从另一个城市到达

ii）从每个城市出发，只有一个其他城市

iii）路线没有分开成单独的岛屿。

再次强调，这对我来说完全有意义，但我仍然难以将这些约束条件编写为线性表达式。显然，这是一个足够简单的矩阵。

谢谢任何帮助！

- Greg Peckory

---

我越来越意识到这可能更多涉及数学，也许应该转移到math.stackexchange？ - Greg Peckory

它不会“产生那个矩阵”，因为你不选择x_{ij}变量的值——ILP求解器会这样做。你给它一堆变量，以及对这些变量的一些约束条件和一个目标函数，并且它（有点神奇地）找到每个变量的值，满足所有约束条件并实现目标函数的最小（或最大）值。 - j_random_hacker

尽管在维基百科页面上写得非常简洁，但假设您的图中只有4个顶点1、2、3和4，则存在12条可能的有向边（每个顶点对之间有两条边——每个方向各一条），因此我们需要12个可以是0或1的变量。让我们称记录从顶点1到顶点2的边是否在最优解中的变量为x_12等等。例如，恰好有1条边离开顶点1的约束将被写为“x_12 + x_13 + x_14 = 1”。 - j_random_hacker

嗯...我觉得开始有点明白了，但我仍然不确定人工变量u及其意义。 - Greg Peckory

如果你只是想解决一些TSP实例，有一个应用程序可以做到。 - David Eisenstat

Answer 1

根据维基百科文章，旅行商问题可以建模为一个整数线性规划问题，这应该是问题的关键。其思路是让决策变量在{0,1}内取值，表示图中选定的边。适当的约束条件必须保证选定的边覆盖每个节点，选定的边构成环的集合，并且只有一个连通分量（总体意味着只有一个包含所有节点的环）。请注意，该文章还给出了明确的公式和解释约束条件的解释。

由于旅行商问题是NP-难问题，除非P=NP，否则无法通过（非整数）线性规划方法求解。

- Codor

---

正如您在上面看到的，我一直在努力理解那篇文章，但感到困惑。我能理解约束条件，但很难将它们写成线性表达式。您是在暗示像CPLEX这样的软件不能解决这样的方程组吗？还是我们必须将其指定为整数线性规划？我有点困惑。感谢您的回答。 - Greg Peckory

我不确定CPLEX是否能够解决整数线性规划问题，但我认为它可以；然而，我想表达的重点是将建模作为（非整数）线性规划很可能是不可能的。 - Codor

将其建模为非整数线性问题并不能直接给出解决方案（通常情况下），但它在分支定界中非常有用，因此可以这样做。这样，您还可以基于旅游属性添加更高级的割（组合割、花割），而不仅仅是ILP求解器中得到的标准割。当然，这意味着您仍在解决ILP问题。 - harold

Answer 2

TSP问题是一个具有组合性质的相当复杂的整数规划问题。存在几种（精确和近似）解决方法。维基百科中的模型只是其中之一：它具有确保每个节点只有一个入弧和一个出弧的约束条件，具有u变量的约束条件用于防止解决方案中的子循环。还有几种编写这些防止子循环约束条件的方法，其中一些可以在文章的4.1部分找到。该部分展示了TSP问题的一些模型（它们都可以使用CPLEX、Gurobi、MATLAB或其他整数/线性规划软件解决）。希望我能有所帮助。 (=

- pbc1303