Целочисленное программирование: дискретная оптимизация и методы отсечения

Дискретный характер области допустимых решений переводит задачи целочисленного программирования в категорию NP-трудных. Область решений больше не является непрерывным многогранником; она представляет собой облако изолированных точек (узлов целочисленной решетки), висящих внутри этого многогранника. Огромную мощь целочисленному моделированию придает использование бинарных (булевых) переменных, принимающих только значения 0 или 1. Они позволяют алгебраически кодировать логические условия. Например, условие взаимоисключения (или строить мост, или тоннель, но не оба сразу) легко записывается как X + Y = 1. С помощью бинарных переменных можно вводить фиксированные затраты на запуск производства, моделировать ступенчатые функции и задавать приоритеты проектов в инвестиционном планировании.

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

Несмотря на теоретическую красоту метода отсечений, на практике он часто сталкивается с проблемами вычислительной нестабильности и медленной сходимости. Поэтому абсолютным индустриальным стандартом решения задач дискретной оптимизации стал метод ветвей и границ, предложенный Эйлсой Лэнд и Алигом Дойгом в 1960 году. Алгоритм также начинает с решения непрерывной задачи. Выбрав переменную с дробным значением (например, X = 3.7), алгоритм разбивает задачу на две непересекающиеся подзадачи (ветви): в первой жестко добавляется условие X меньше или равно 3, во второй — X больше или равно 4. Таким образом, область решений разрезается пополам, отбрасывая недопустимую дробную полосу.

Метод ветвей и границ выстраивает бинарное дерево подзадач. Для каждой ветви решается своя непрерывная линейная модель, которая дает локальную оценку (верхнюю или нижнюю границу целевой функции). Если оценка некой ветви оказывается хуже, чем уже найденное целочисленное (рекордное) решение на другой ветви, эта ветвь безвозвратно отсекается, избавляя компьютер от необходимости исследовать миллиарды тупиковых комбинаций. Современные коммерческие решатели (солверы), такие как Gurobi или CPLEX, используют комбинацию этих двух подходов, называемую методом ветвей и отсечений (Branch and Cut). Генерируя продвинутые алгоритмические сечения на каждом узле дерева поиска, они способны за считанные минуты находить абсолютно точные оптимальные решения для расписаний движения целых железнодорожных сетей и графиков дежурств крупных медицинских центров.