Снижение точек / осуществимости в разложении Бендерс

Question

Я узнаю о разложении Бендера, и сейчас я работаю с файлом bendersatsp.py.Я понимаю, что в модели (ATSP), которая запрограммирована в нем, нет необходимости добавлять сокращения возможностей.Я хотел бы увидеть игрушечный пример, в котором необходимо добавить сокращения осуществимости, используя ту же структуру кода, что и в этом файле, чтобы понять, как это сделать.

Я думал об этом:

Необходимо добавить новое условие if внутри функции def separate:

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

Может ли это быть опцией?

Спасибомного!

Answer 1

Я думаю, что вы ошиблись: пример только разделяет сокращения осуществимости.

Ваша идея использовать функцию separate для оптимальных сокращений верна. Однако, поскольку подзадача является LP, а не MIP, вам придется проверить состояние для cpx.solution.status.optimal.

В настоящее время нет примера кода для этого в Python. С другой стороны, возможно, не так уж сложно просто взять любое описание учебника Бендера, привести его в соответствие с примером Python, который вы процитировали, а затем расширить разделение самостоятельно.

В cplex/examples/src/remotec/parbenders.c имеется реализация Benders, которая разделяет оба типа разрезов. Эта реализация написана на C, но, учитывая, что Python и C API похожи, это может вам помочь.