optimization - 将 CVRP 的条件子旅游消除转换为正常的子旅游消除

Question

我试图从以下 CVRP 公式中消除if 条件约束。

我在纸上尝试了一些大 M 方法，但未能提出适当的重新表述。你能帮我找到解决办法吗？

谢谢！

标签： optimizationlinear-programminglinearization

Answer 1

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

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

具有大 M 常数的模型往往较弱且数值不稳定，因此我建议选择尽可能小的常数（即，如果可能，使 M 取决于 ij）。要了解更多信息，请查看“Big M”的危险。