针对TSP和Christofide启发式的Subtour约束公式

Question

我正在研究旅行商问题（TSP）的不同表述的比较。特别是，我正在比较DFJ和MTZ子句约束公式。这些是使用GLPK求解器实现的（通过使用pyomo包的Python代码。由于前者中的约束非常多，TSP解决如下：

1. 放宽所有的地下限制
2. 解决MIP
3. 如果解决方案是可以接受的：完成
4. else：为当前解决方案中的每个子周期添加DFJ子树约束

这对我需要处理的实例非常有效。另一方面，MTZ配方较慢（10至10k倍）。因此，我有以下问题：

1. MTZ配方能否反复有效地解决？
2. 这10-10倍的时间增加的原因是什么？

关于第二个问题，两个不同之处在于DFJ公式包含$ O（2 ^ n）$ subour约束，而MTZ包含$ O（n ^ 2）$ subour约束，而DFJ使用$ n $变量，而MTZ使用$ 2N $。但是，由于DFJ是迭代求解的，因此不需要所有的子树约束（实际上，对于我使用的实例，少于10次迭代就足够了），我们留下了相似数量的约束。因此，我假设差异是变量的数量，但我无法弄清楚为什么这会导致如此大的差异。

作为最后一点，我认为使用启发式方法（即Christofide's algorithm）可以产生目标的上限，可以用作新约束（希望大大减少可行解的集合）。但是，如果我首先应用Christofide的启发式方法在目标上设置上限，然后在求解MIP之前将其添加到约束中，效率最多不变，最坏的情况下降低10倍。

怎么会？这与可行解决方案的新形式有关吗？我的一个朋友还假设GLPK可能没有执行适当的预处理以消除主导的约束，但我不知道这是否属实，我不知道在哪里寻找这个。

有没有人对我遇到的众多问题之一有所了解。

Answer 1

关于Christofides启发式的使用：我不认为正确的方法是将其目标作为约束。相反，您希望将目标作为求解器的上限。我不确定GLPK如何处理这个，但我猜有一种方法可以提供一个初始上限，解算器最初可以使用它来解析分支绑定树，然后找到一个可行的解决方案。比你的约束更好。

此外，Christofides具有良好的理论属性，但它通常不是TSP的最佳启发式。甚至一些非常简单的插入（例如最远的插入）平均表现更好。

不幸的是，我没有任何关于DFJ与MTZ地下消除约束的建议......