将旅行商表示为线性表达式
Representing Travelling Salesman as Linear Expression
我在网上看到可以将旅行商问题写成线性表达式，然后使用 CPLEX 等软件计算 java。
我有 1000 个城镇，需要找到一个短距离。我计划将这 1000 个城镇划分为大约 100 个城镇的集群，并对这些单独的集群执行一些线性规划算法。
我的问题是，我如何将其精确地表示为线性表达式。
所以我有 100 个城镇，我相信每个人都知道 TSP 是如何运作的。
我完全不知道如何编写满足 TSP 的线性约束、目标和变量。
有人可以向我解释这是如何完成的，或者给我发一份 link 解释得很清楚，因为我已经研究了很多但似乎找不到任何东西。
编辑：
我发现了一些额外的信息：
我们用数字 0 到 n 标记城市并定义矩阵：
这会产生以下 5 个城镇的矩阵吗？
约束是：
i) 每个城市都是从另一个城市到达的
ii) 每个城市都有一班去另一个城市的班次
iii) 这条路线没有分成单独的岛屿。
同样，这对我来说完全有意义，但我仍然无法将这些约束写成线性表达式。显然这是一个足够简单的矩阵。
感谢您的帮助！
据此Wikipedia article旅行商问题可以建模为整数线性程序，我认为这是问题的关键问题。这个想法是在 {0,1} 中有允许值的决策变量，该模型选择图中的边。合适的约束必须确保所选边覆盖每个节点，所选边形成一组循环并且只有一个连通分量（这总共意味着恰好有一个循环包含每个节点）。请注意，该文章还给出了明确的公式并解释了约束的解释。
由于旅行商问题NP-hard，除非P=NP.
，否则不能通过（非积分）线性规划解决它
由于其组合性质，TSP 问题是一个相当复杂的整数规划问题。
有几种（精确的和近似的）技术可以解决它。 Wikipedia is just one of them: it has constraints to ensure there is only one incoming and outgoing arc in each node and the constraints with u variables are for preventing sub-cycles in the solution. There is also several ways to write this sub-cycle preventing constraints, some of them can be found on section 4.1 of this article 中的模型。本节介绍了 TSP 问题的一些模型（所有这些都可以使用 CPLEX、Gurobi、MATLAB 或其他 Integer/Linear 编程软件解决。
希望我能帮到您。 (=
我在网上看到可以将旅行商问题写成线性表达式，然后使用 CPLEX 等软件计算 java。
我有 1000 个城镇，需要找到一个短距离。我计划将这 1000 个城镇划分为大约 100 个城镇的集群，并对这些单独的集群执行一些线性规划算法。
我的问题是，我如何将其精确地表示为线性表达式。
所以我有 100 个城镇，我相信每个人都知道 TSP 是如何运作的。
我完全不知道如何编写满足 TSP 的线性约束、目标和变量。
有人可以向我解释这是如何完成的，或者给我发一份 link 解释得很清楚，因为我已经研究了很多但似乎找不到任何东西。
编辑：
我发现了一些额外的信息：
我们用数字 0 到 n 标记城市并定义矩阵：
这会产生以下 5 个城镇的矩阵吗？
约束是：
i) 每个城市都是从另一个城市到达的
ii) 每个城市都有一班去另一个城市的班次
iii) 这条路线没有分成单独的岛屿。
同样，这对我来说完全有意义，但我仍然无法将这些约束写成线性表达式。显然这是一个足够简单的矩阵。
感谢您的帮助！
据此Wikipedia article旅行商问题可以建模为整数线性程序，我认为这是问题的关键问题。这个想法是在 {0,1} 中有允许值的决策变量，该模型选择图中的边。合适的约束必须确保所选边覆盖每个节点，所选边形成一组循环并且只有一个连通分量（这总共意味着恰好有一个循环包含每个节点）。请注意，该文章还给出了明确的公式并解释了约束的解释。
由于旅行商问题NP-hard，除非P=NP.
由于其组合性质，TSP 问题是一个相当复杂的整数规划问题。 有几种（精确的和近似的）技术可以解决它。 Wikipedia is just one of them: it has constraints to ensure there is only one incoming and outgoing arc in each node and the constraints with u variables are for preventing sub-cycles in the solution. There is also several ways to write this sub-cycle preventing constraints, some of them can be found on section 4.1 of this article 中的模型。本节介绍了 TSP 问题的一些模型（所有这些都可以使用 CPLEX、Gurobi、MATLAB 或其他 Integer/Linear 编程软件解决。
希望我能帮到您。 (=