Выявить ограничение неосуществимости и ослабить / удалить его в Python с помощью Pulp?

Question

Я пытался решить проблему MILP с использованием мякоти питона, и решение неосуществимо. Итак, я хочу найти, куда приходит неосуществимость, и хочу расслабить или убрать это, чтобы найти возможное решение. трудно проверить вручную в файле LP, потому что присутствует большое количество ограничений. Итак, как мне справиться с этой проблемой?

Я просмотрел несколько статей, в которых упоминалось, что они проверяют вручную в файле LP, но это очень трудно сделать вручную для огромного числа переменных / ограничений.

Даёт просто неосуществимость

Answer 1

В общем, это не так просто. Некоторые указатели:

• Если вы можете создать реальное, но не обязательно оптимальное решение для вашей проблемы, подключите его, и вы очень легко найдете виновных.
• У некоторых продвинутых решателей есть инструментыэто может помочь (IIS, Уточнение конфликтов). Они могут указывать или не указывать на реальную проблему.
• Обратите внимание, что модель может быть LP неосуществимой или просто целочисленной.
• В некоторых случаях возможно просто ослабить подозрительный блок ограниченийи посмотрим, что произойдет.
• Более структурный подход, который я часто использую, состоит в том, чтобы сформулировать упругую модель: позволить ограничениям нарушать, но за плату. Это часто имеет некоторый экономический смысл: нанимать временных работников, арендовать дополнительные мощности, покупать у третьих лиц и т. Д.

Answer 2

Я использую некоторое правило для проверки невозможности.

• Всегда начинайте с небольшого набора данных, который вы можете проверить больше вручную.

• После расслабления все целочисленные переменные. Если это расслабление неосуществимо, ваша проблема линейно неосуществима. У вас могут быть ограничения, такие как x> 3 и x <2; </p>

• Если линейная релаксация возможна, то деактивируйте каждое ограничение один раз. Часто вы обнаруживаете, что некоторые очевидные ограничения недопустимы, такие как sum (i, x_i) = 1. Но если вы деактивируете одно за другим, вы можете обнаружить, что другой более сложный набор ограничений вызывает невозможность, и там вы могли бы исследовать лучше.