TSP和赫里斯托赖德启发式的子旅游约束公式

Question

我正在对旅行商问题(TSP)的不同公式进行比较。特别是，我比较了DFJ和MTZ子图约束公式。这些都是使用GLPK解决程序实现的(通过带有pyomo包的Python代码实现)。由于前者有很大的限制，TSP的解决办法如下：

1. 放松所有的子旅游约束
2. 解MIP
3. 如果可接受解决方案:完成
4. else:为当前解决方案中的每个子周期添加DFJ子循环约束

对于我需要处理的实例来说，这是非常有效的。另一方面，MTZ的配方要慢得多(在10到10k之间)。因此，我有以下问题：

1. MTZ公式也能有效地迭代求解吗？
2. 是什么原因造成这10-10k倍的时间增长？

对于第二个问题，两个区别是DFJ公式包含$O(2^n)$子图约束，而MTZ包含$O(n^2)$子图约束，DFJ与$n$变量一起工作，而MTZ工作在$2n$。但是，由于DFJ是迭代求解的，所以不需要所有的子遍历约束(实际上，对于我使用的实例来说，少于10次迭代就足够了)，所以剩下的约束数量也是相同的。因此，我假设差异是变量的数量，但我不知道为什么会有这么大的差异。

最后，我认为使用一种启发式方法(即赫里斯托赖德算法)可以产生一个关于目标的上限，这个上限可以作为一个新的约束(希望大大减少可行的解集)。然而，如果我首先应用赫里斯托菲的启发式方法对目标有一个上界，然后在求解MIP之前将其添加到约束中，效率最好是不变的，在最坏的情况下，效率会下降10倍。

怎么会这样?这与一组可行解的新形状有关吗？我的一位朋友还假设GLPK可能不执行适当的预处理以消除主导的约束，但我不知道这是否是真的，我也不知道在哪里寻找这个。

有谁对我的众多问题中的一个有什么想法吗？

Answer 1

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

另外，赫里斯托菲德有很好的理论性质，但总的来说，它并不是TSP的最佳启发。即使是一些真正简单的，比如最远的插入，平均表现也更好。

不幸的是，我没有任何关于DFJ与MTZ子旅游消除限制的建议.