Определение того, является ли целочисленная программа невыполнимой

Предположим, у нас есть задача целочисленного или смешанно-целочисленного программирования с парой тысяч ограничений.

Количество ограничений не обязательно масштабируется с невозможностью: обычно ограничения ограничивают количество возможностей, которые необходимо перечислить. Другая родственная проблема — это случайный 3-SAT, где, например, самые сложные задачи — это задачи, в которых количество ограничений увеличивается примерно в четыре раза по сравнению с количеством переменных.

Как мы можем понять, что эта проблема вообще разрешима?

Доступны хорошие (смешанные) целочисленные решатели, которые могут решить некоторые (сложные) проблемы за разумное время. Тем не менее, общие задачи целочисленного программирования известны как NP-трудные. Это означает, что маловероятно найти алгоритм, решающий эти задачи вообще за разумное время. Иногда нам везет, и проблема целочисленного программирования имеет некоторую структуру, которую мы можем использовать для эффективного поиска решения, но, как сказано: в целом это сложная проблема.

Решатели обычно работают с ветвями и границами, где посредством релаксации домены переменных ограничиваются до тех пор, пока не будет достигнуто стабильное состояние. Затем решатель выбирает значение для одной из переменных (какая переменная и какое значение в первую очередь тщательно исследуются, поскольку они оказывают большое влияние на поиск решения). Затем проблема ослабляется до тех пор, пока либо не будет доказано, что решения с таким значением не существует, либо система не должна присвоить новое значение. Если доказано, что модель неудовлетворительна для заданного набора назначенных переменных, система возвращается: она отменяет некоторые назначенные переменные, переназначает им значения и продолжает поиск. В конце концов решение будет найдено (но это может занять очень много времени), или решатель может доказать, что проблема неразрешима (решение не существует). В случае, если решение найдено, мы еще не закончили: поскольку обычно нас интересует оптимальное решение относительно некоторой функции оптимизации. В этом случае мы добавляем ограничение, что с этого момента мы ищем решения, которые лучше, чем найденное до сих пор. Мы продолжаем делать это до тех пор, пока у нас не закончатся новые решения, и в этом случае мы докажем оптимальность.

Если легко найти правильные решения (относительно жестких ограничений), но сложно получить наилучшее решение, можно использовать метаэвристику для аппроксимации< /strong> лучшее решение. Здесь рассматривается «пространство решений», состоящее из решений, удовлетворяющих жестким ограничениям. Построив ряд «функций мутации», которые принимают правильное решение и превращают его в другое решение, можно сгенерировать алгоритм, который ищет наилучшее решение, итеративно манипулируя решением. Если у нас заканчивается время, мы возвращаем лучшее решение на данный момент. Хотя у нас никогда нет гарантий, что у нас есть оптимальное решение, обычно метаэвристика работает достаточно хорошо и возвращает близкое к оптимальному решение. Некоторые метаэвристики, такие как Имитация отжига, могут предоставить статистические гарантии качества решения.