Привет, я пытаюсь решить проблемы с эксплуатацией с помощью ortools или gurobi. Мне интересно, если я предоставлю некоторые явные ограничения, например, переменные должны попадать в [a, b], ускорит ли это скорость работы или сделает ее еще более сложной, чем раньше?
Будет ли Ortools/gurobi работать быстрее, если ввести больше ограничений?
Ответы (2)
В смешанной целочисленной оптимизации часто рекомендуется добавлять дополнительные ограничения, если они отсекают линейные решения, которые не удовлетворяют ограничениям интегрируемости. Эти разрезы смешанных целых чисел предназначены для приближения оптимального линейного решения к оптимальному целочисленному решению и иногда может привести к значительному ускорению. Коммерческие решатели, такие как gurobi, автоматически генерируют некоторые из этих разрезов.
Кроме того, коммерческие решатели, скорее всего, будут игнорировать добавленные вами избыточные ограничения, если они не помогут. Так что обычно вы не теряете производительность.
Поэтому обычно рекомендуется добавлять такие ограничения.
Обратите внимание, что иногда изменение задачи также меняет порядок ответвлений и разрезов. Так что может случиться так, что вам повезло раньше и вы получили целочисленное решение быстро, а новые решения требуют больше времени из-за другого ветвления. Поэтому при решении MIP вы иногда видите нелогичное поведение во время выполнения.
person
SimonT
schedule
29.07.2020
Уменьшенные домены, скорее всего, помогут. Добавление дополнительных ограничений может помочь. Это зависит от их сложности и их количества.
Когда вы говорите или-инструменты, что вы имеете в виду?
person
Laurent Perron
schedule
28.07.2020
Большое спасибо! Сначала я попробовал решатель MIP, но похоже, что не может быть приемлемого решения проблемы с 10000 переменными. Но когда я переключился на CP-SAT и добавил приведенные выше ограничения, у него действительно было оптимальное решение, и он работал намного быстрее, чем раньше.
- person Han Zhu; 28.07.2020
