linear-programming - 单纯形法求解 tsp 的速度有多快？

Question

与蛮力或任何其他算法相比，单纯形法解决 ts 问题的速度有多快？

Answer 1

您不能用“纯”LP 问题(具有连续变量)对 TS 问题建模。您可以使用整数规划公式，这将在研究树的每个节点上使用单纯形法(分支定界法或分支切割法)。它适用于小问题，但速度很慢，因为问题很难:例如，每条边有一个二进制变量，您需要大量约束来模拟路径是一个循环这一事实。

蛮力是棘手的(问题是指数级的)，除非你有一个非常的小问题，否则不要尝试它。使用 MIP 公式，即使是小问题。

对于大问题，你应该使用某种启发式方法(我认为模拟退火在这个问题上会给出很好的结果)，或者如果你想要一个精确的解决方案，你的问题的“智能”建模(例如列生成)。