TSP和Christofide启发式的子游约束公式

Question

我正在比较旅行商问题（TSP）的不同公式。特别是，我比较了DFJ和MTZ次目标约束公式。这些都是使用GLPK解算器（通过Python代码和pyomo包）实现的。由于前者中有大量约束，TSP的解决方法如下：

1. 放松所有子任务约束
2. 求解MIP
3. 如果解决方案可行：完成
4. 否则：为当前解决方案中的每个子周期添加DFJ subtour约束

这在我需要处理的实例上非常有效。另一方面，MTZ配方要慢得多（在10到10k倍之间）。因此，我有以下问题：

1. MTZ公式也能有效地迭代求解吗

关于第二个问题，两个区别是DFJ公式包含$O（2^n）$subTour约束，而MTZ包含$O（n^2）$subTour约束，DFJ使用$n$变量，而MTZ使用$2n$。然而，由于DFJ是迭代求解的，因此不需要所有的subTour约束（实际上对于我使用的实例来说，少于10次迭代就足够了），我们只剩下类似数量的约束。因此，我假设差异是变量的数量，但我不知道为什么这会导致如此大的差异。

最后，我认为使用启发式方法（即Christofide算法）可以产生目标的上界，可以用作新的约束条件（希望大幅减少可行解集）。然而，如果我首先应用赫里斯托菲德的启发式方法来确定目标的上界，然后在求解MIP之前将其添加到约束中，那么效率最多保持不变，最坏的情况下会降低10倍。

为什么？这与可行解决方案集的新形状有关吗？我的一个朋友也假设GLPK可能不会执行适当的预处理来消除支配约束，但我不知道这是否正确，我也不知道去哪里找这个。

有人对我的众多问题中的一个有想法吗？

Answer 1

关于赫里斯托菲德斯启发式的使用：我认为正确的方法不是将其目标作为约束。相反，您希望为解算器提供目标作为上限。我不知道GLPK是如何处理这个问题的，但我想有一种方法可以提供一个初始上界，在它找到一个比你的上界更好的可行解决方案之前，解算器可以先用它来了解分支和边界树。

此外，赫里斯托菲德（Christofides）具有很好的理论性质，但一般来说，它不是TSP的最佳启发式。即使是像“最远插入”这样非常简单的方法，平均性能也会更好。

不幸的是，我没有任何关于DFJ与MTZ子目标消除约束的建议。。。