将CVRP的条件子圈消去转化为正规子圈消除

Question

我试图从下面的CVRP公式中消除，如果条件约束，那么。

​

​

我在纸上尝试了一些大的M方法，但是没有想出正确的方法。你能帮我找到解决办法吗？

谢谢!

Answer 1

您可以将方程分解为两个不等式，并应用大-M方法：

ui + qj <= uj + M(1-xij)
ui + qj >= uj - M(1-xij)

大M常数的模型往往是弱的和数值不稳定的，所以我建议尽可能地选择这个常数(如果可能的话，让M依赖ij )。要了解更多关于这一点的信息，请看一下“大M”的危险。