Детерминированное целочисленное программирование — точная оптимизация с целочисленными переменными решения
- Автор метода
- Ralph E. Gomory
- Год
- 1958
- Тип
- Exact combinatorial optimization
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Детерминированное целочисленное программирование (DIP) — это подход к математической оптимизации, который находит наилучшее решение для задач, где некоторые или все переменные решения должны принимать целочисленные значения, при полностью известных (детерминированных) данных целевой функции и ограничений.
Это классическая, нестохастическая форма целочисленного программирования, являющаяся основой исследования операций и комбинаторной оптимизации с конца 1950-х годов.
Интуиция метода
Многие реальные решения по своей сути дискретны: вы открываете объект или нет; вы назначаете работника на смену или нет. Методы непрерывной оптимизации не могут обеспечить выполнение этих требований к целым числам. Детерминированное целочисленное программирование решает эту проблему, ограничивая переменные целыми числами, в то время как все параметры задачи — затраты, мощности, потребности — известны с определенностью. Результатом является точное, доказуемо оптимальное решение при таком предположении об определенности, что делает его эталонной формулировкой, с которой сравниваются стохастические и робастные варианты.
История
Целочисленное программирование возникло из линейного программирования в конце 1950-х годов. Алгоритм отсекающих плоскостей Ральфа Гомори 1958 года был первым систематическим точным методом. Параллельно с методом «ветвей и границ» (Лэнд и Дойг, 1960) эти подходы определили область. Прилагательное «детерминированное» отличает классическую формулировку от стохастического целочисленного программирования (Бирдж и Луве, 1997) и стало стандартной терминологией по мере распространения вариантов, учитывающих неопределенность.
Когда применять
Используйте детерминированное целочисленное программирование, когда: (1) переменные решения по своей сути дискретны (назначение, планирование, выбор местоположения объекта, упаковка в контейнеры, проектирование сети); (2) все параметры задачи известны с определенностью или могут быть надежно оценены как точечные значения; (3) требуется точное оптимальное решение, а не эвристическая аппроксимация. НЕ используйте, когда: параметры неопределенны или зависят от сценария (вместо этого используйте стохастическое или робастное целочисленное программирование); масштаб задачи настолько велик, что метод «ветвей и границ» вычислительно неразрешим, а эвристики приемлемы; переменные действительно непрерывны (используйте ЛП); или необходимо одновременно сбалансировать несколько конфликтующих целей (используйте многокритериальное целочисленное программирование).
Ограничения и замечания
- Предполагает, что все параметры задачи известны точно — неопределенность реального мира игнорируется по дизайну.
- В общем случае NP-трудно; время решения в худшем случае растет экспоненциально с размером задачи.
- Большие комбинаторные задачи могут потребовать часов или дней вычислений даже с современными решателями.
- Качество формулировки модели (плотность ограничений, разбиение симметрии) сильно влияет на время решения.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Гарантирует доказуемо оптимальное решение в рамках предположений детерминированной модели.
- Естественным образом обрабатывает дискретные, комбинаторные структуры решений, которые непрерывные методы не могут.
- Поддерживается зрелыми, высокоэффективными коммерческими и открытыми решателями (CPLEX, Gurobi, SCIP).
- Предоставляет сертификат разрыва оптимальности, позволяющий обоснованно досрочно завершить работу для больших экземпляров.
- Служит эталонной моделью для сравнения эвристических и стохастических вариантов.
Применение
- Планирование и составление расписаний производства с дискретными ресурсами машин или рабочей силы
- Выбор местоположения объекта: решение о том, какие склады или заводы открыть
- Маршрутизация транспортных средств и составление расписаний экипажей в транспорте и логистике
- Капитальное бюджетирование: выбор портфеля неделимых инвестиционных проектов
- Проектирование телекоммуникационных сетей с фиксированными затратами на установку каналов
- Составление графиков медицинского персонала и планирование операционных
Как это работает
Как это работает
Определить модель оптимизации: целевая функция для минимизации (или максимизации) как линейная комбинация целочисленных переменных решения, подчиненная набору линейных неравенств или равенств. Все коэффициенты (c, A, b) фиксированы и известны — именно это делает формулировку детерминированной. Бинарные переменные (0/1) являются особым случаем для решений «да/нет».
Формула
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^nРешить релаксацию ЛП, которая временно позволяет переменным принимать непрерывные значения. Это дает нижнюю границу оптимального целочисленного значения целевой функции. Если решение релаксации ЛП уже целочисленное, оно оптимально для ЦП; в противном случае начинается ветвление.
Формула
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0Выбрать переменную с дробным значением из решения релаксации ЛП и разделить допустимую область, добавив ограничение «пол» (x_j <= floor value) в одной ветви и ограничение «потолок» (x_j >= ceil value) в другой, генерируя две подзадачи, которые решаются рекурсивно.
Формула
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilРешить релаксацию ЛП каждой подзадачи, чтобы получить границу. Если граница узла хуже, чем лучшее известное целочисленное решение (инкумбент), отсечь его. Если подзадача дает целочисленно допустимое решение, лучшее, чем инкумбент, обновить инкумбент. Процесс формирует дерево поиска «ветвей и границ».
Формула
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}Методы отсекающих плоскостей — в первую очередь отсечки Гомори — выводят дополнительные линейные неравенства из симплекс-таблицы ЛП, которые удовлетворяются всеми целочисленными решениями, но нарушаются текущим дробным решением ЛП. Добавление этих отсечек сужает релаксацию ЛП и уменьшает ветвление. Современные решатели комбинируют «ветви и границы» с отсечками в рамках «ветвей и отсечек».
Формула
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}Алгоритм завершается, когда все открытые узлы отсечены или дают целочисленные решения. Инкумбент на момент завершения является доказуемо оптимальным целочисленным решением. Решатели также сообщают о разрыве между лучшей границей и инкумбентом, который может использоваться как критерий остановки для больших задач.
Формула
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*Частые ошибки
- Обработка неопределенных параметров как детерминированных точечных оценок может привести к решениям, которые плохо работают на практике — проверьте это предположение перед применением DIP.
- Слабые релаксации ЛП (большие целочисленные разрывы) приводят к огромным деревьям «ветвей и границ»; инвестируйте в допустимые неравенства и переформулировку перед масштабированием.
- Взрыв бинарных переменных из формулировок «большого М» может численно дестабилизировать релаксацию ЛП; предпочтите более плотные переформулировки ограничений.
- Принятие допустимости за оптимальность при использовании допуска на разрыв, отличного от нуля — всегда сообщайте о разрыве вместе со значением целевой функции.
- Игнорирование симметрии в моделях (например, идентичных машин или работников) вызывает избыточное ветвление; добавьте ограничения, нарушающие симметрию.
Часто задаваемые вопросы
Чем детерминированное целочисленное программирование отличается от стохастического целочисленного программирования?
В детерминированном ЦП все параметры целевой функции и ограничений фиксированы и известны. Стохастическое ЦП явно моделирует неопределенные параметры с помощью вероятностных распределений или сценариев, производя решения, которые являются робастными или оптимальными в среднем по этим сценариям. Детерминированное ЦП проще и быстрее в решении, но игнорирует неопределенность.
Является ли бинарное программирование частным случаем целочисленного программирования?
Да. Бинарное (0-1) программирование ограничивает каждую переменную решения значениями {0, 1}. Это наиболее распространенный частный случай, используемый для решений «да/нет», таких как открытие объекта, выбор проекта или назначение работника. Общее целочисленное программирование допускает любое неотрицательное целое значение.
Когда следует перейти от детерминированного ЦП к эвристическому методу?
Когда дерево «ветвей и границ» слишком велико для исследования в пределах допустимого временного лимита, а разрыв оптимальности от хорошей эвристики (генетический алгоритм, имитация отжига, поиск в большой окрестности) приемлем для данного приложения. Сообщайте и обосновывайте разрыв при отклонении от точной оптимизации.
Может ли детерминированное ЦП обрабатывать нелинейные целевые функции или ограничения?
Классическое детерминированное ЦП предполагает линейность (целочисленное линейное программирование). Нелинейное целочисленное программирование существует, но оно значительно сложнее; многие нелинейные формы могут быть линеаризованы с помощью вспомогательных бинарных переменных и переформулировок «большого М». Квадратичное целочисленное программирование (QIP) напрямую поддерживается некоторыми современными решателями.
Какой решатель следует использовать для детерминированного ЦП на практике?
Коммерческие: Gurobi или IBM CPLEX для лучшей производительности. Академические/открытые: SCIP, CBC (через COIN-OR) или HiGHS. Все они реализуют метод «ветвей и отсечек» с автоматической предварительной обработкой. Для пользователей Python удобные интерфейсы моделирования предоставляют PuLP, Pyomo или scipy.optimize.milp.
Похожие методы
Источники
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
Открыть ссылку DOIСкопировано.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Скопировано.