与蛮力或任何其他算法相比，单纯形法解决 ts 问题的速度有多快？
问问题
2333 次
1 回答
3
您不能使用“纯”LP 问题（具有连续变量）来建模 TS 问题。您可以使用整数规划公式，它将在研究树的每个节点上使用单纯形法（分支和绑定或分支和切割方法）。它适用于小问题，但速度很慢，因为问题很困难：例如，对于每条边都有一个二进制变量，您需要很多约束来模拟路径是一个循环的事实。
蛮力是棘手的（问题是指数级的），除非你有一个非常小的问题，否则不要尝试。使用 MIP 公式，即使是小问题。
对于大问题，你应该使用某种启发式方法（我认为模拟退火在这个问题上会给出很好的结果），或者如果你想要一个精确的解决方案，你应该对你的问题进行“智能”建模（例如列生成）。
于 2012-12-06T07:37:59.120 回答