我在网上看到,人们可以将旅行商问题写成线性表达式,并使用CPLEX for java等软件进行计算 .
我有1000个城镇,需要找一小段距离 . 我计划将这1000个城镇划分为约100个城镇的集群,并在这些单独的集群上执行一些线性规划算法 .
我的问题是,我究竟如何将其表示为线性表达式 .
所以我有100个城镇,我相信每个人都知道TSP是如何工作的 .
我完全不知道如何编写满足TSP的线性约束,目标和变量 .
有人可以向我解释这是如何完成的,或者给我一个清楚解释它的链接,因为我一直在研究很多,似乎找不到任何东西 .
编辑:
我找到了一些额外的信息:
我们用数字0到n标记城市并定义矩阵:
这会为5个城镇产生以下矩阵吗?
限制是:
i)每个城市都来自其他城市
ii)从每个城市出发前往另一个城市
iii)该路线不会分成不同的岛屿 .
同样,这对我来说是完全合理的,但我仍然无法将这些约束写为线性表达式 . 显然它是一个简单的矩阵 .
谢谢你的帮助 !
2 回答
根据这个Wikipedia article,旅行商问题可以建模为整数线性程序,我认为这是问题的关键问题 . 我们的想法是在
{0,1}
中设置允许值的决策变量,该变量对图中的选定边进行建模 . 合适的约束必须确保所选边缘覆盖每个节点,所选边缘形成一组循环,并且只有一个连接组件(总的来说,这意味着只有一个循环包含每个节点) . 请注意,该文章还给出了明确的表述,并解释了约束的解释 .由于旅行商问题是
NP
-hard,除非P=NP
,否则无法通过(非整数)线性编程解决 .由于其组合性质,TSP问题是一个相当复杂的整数规划问题 . 有几种(精确的和近似的)技术可以解决它 . Wikipedia中的模型只是其中之一:它具有约束以确保每个节点中只有一个传入和传出弧,而具有u变量的约束用于防止解决方案中的子循环 . 还有几种方法可以编写这个子循环来防止约束,其中一些可以在article的第4.1节中找到 . 本节介绍了TSP问题的一些模型(所有这些模型都可以使用CPLEX,Gurobi,MATLAB或其他整数/线性编程软件来解决 .
希望我可以提供任何帮助 . (=