Point/Feasibility Benders 分解的削减

Question

我正在学习 Benders 分解，现在，我正在处理文件 bendersatsp.py。我知道在其中编程的模型 (ATSP) 中没有必要添加可行性削减。我想看一个玩具示例，其中有必要使用与此文件中相同的代码结构添加可行性削减，以便了解如何执行此操作。

我一直在想：

有必要在函数def separate里面添加一个新的条件if :

if cpx.solution.get_status() == cpx.solution.status.MIP_optimal:

可以这样选择吗？

非常感谢！

Answer 1

我认为你弄错了：示例 仅 将可行性削减分开。

不过，您将挂接到函数 separate 以实现最优性削减的想法是正确的。但是，由于子问题是 LP 而不是 MIP，因此您必须检查 cpx.solution.status.optimal 的状态。

目前 Python 中没有这方面的示例代码。另一方面，仅采用 Benders 的任何教科书描述，将其与您引用的 Python 示例对齐，然后自己扩展分离可能并不难。

在 cplex/examples/src/remotec/parbenders.c 中，您有一个 Benders 实现将两种类型的切割分开。此实现在 C 中，但可能鉴于 Python 和 C API 相似，这可能对您有所帮助。