Смешанное целочисленное программирование — точная оптимизация по непрерывным и целочисленным решениям
- Автор метода
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- Год
- 1958–1960
- Тип
- Mathematical optimization
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Смешанное целочисленное программирование (MIP) — это математическая модель оптимизации, в которой некоторые переменные решения должны принимать целочисленные значения, а другие могут быть непрерывными.
Она обобщает линейное программирование и широко используется в исследовании операций, логистике, планировании, распределении ресурсов и проектировании, где ограничения на неделимость — такие как решения «да/нет» или количества целых единиц — возникают естественным образом.
Интуиция метода
Многие реальные задачи оптимизации включают решения, которые нельзя разделить — вы либо открываете предприятие, либо нет, назначаете ровно одного работника на смену, заказываете целые единицы. Непрерывное линейное программирование игнорирует эти реалии и может давать невыполнимые дробные ответы. MIP обеспечивает целочисленность непосредственно в модели. Решатель систематически исследует пространство допустимых целочисленных решений с помощью метода ветвей и границ: он решает релаксированные непрерывные подзадачи для определения границы наилучшего возможного решения в каждой области, отбрасывает области, которые не могут улучшить наилучшее найденное целочисленное решение, и добавляет отсекающие плоскости для сужения поиска. Результатом является доказуемо оптимальный или близкий к оптимальному план.
История
Основы целочисленного программирования были заложены Ральфом Гомори, который ввел метод отсекающих плоскостей в 1958 году, и Лэндом и Дуайгом, которые формализовали метод ветвей и границ в 1960 году. В последующие десятилетия были разработаны теория LP-релаксации, полиэдральная комбинаторика (Эдмондс, Падберг, Грётшель), и к 1990-м годам коммерческие решатели сделали крупномасштабное MIP практичным. Обширное изложение области содержится в Nemhauser and Wolsey (1988) и Wolsey (1998).
Когда применять
Использовать MIP, когда ваша задача имеет линейную или линеаризуемую целевую функцию и ограничения и включает решения, которые должны быть целочисленными (размещение объектов, составление расписаний экипажей, бюджетные ограничения, проектирование сетей, задачи раскроя). Это предпочтительный метод, когда требуется доказуемо оптимальное решение или решение с ограниченным разрывом, а размер задачи управляем (тысячи переменных с современными решателями). НЕ использовать MIP, когда целевая функция или ограничения сильно нелинейны (использовать нелинейное или смешанное нелинейное программирование вместо этого), когда задача настолько велика, что точные методы нецелесообразны (рассмотреть эвристики или метаэвристики), или когда непрерывные аппроксимации достаточно точны (использовать LP для скорости).
Ограничения и замечания
- Хуже всего сложность NP-полная; время решения может экспоненциально расти с количеством целочисленных переменных.
- Требует точной математической формулировки; плохо сформулированные модели могут быть неразрешимыми, даже если лежащая в основе задача управляема.
- Невыпуклые или нелинейные элементы требуют дополнительной линеаризации или специализированных решателей, что увеличивает сложность модели.
- Стоимость лицензирования решателей может быть значительной для коммерческих инструментов, хотя существуют высококачественные альтернативы с открытым исходным кодом.
- Результаты хороши настолько, насколько хороша модель: неправильная спецификация ограничений приводит к бессмысленным оптимумам.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Производит доказуемо оптимальные решения с количественно определяемым разрывом оптимальности, что позволяет обоснованно обосновывать решения.
- Обрабатывает бинарные и общие целочисленные переменные нативно, учитывая реальную неделимость и логические ограничения.
- Современные решатели (Gurobi, CPLEX, SCIP) используют усовершенствованные методы ветвей и границ, отсекающие плоскости и предварительную обработку для эффективной обработки больших экземпляров.
- Прозрачное моделирование делает предположения явными и проверяемыми экспертами в предметной области.
- Поддерживает анализ чувствительности и параметрические исследования для понимания того, как решения изменяются в зависимости от входных данных.
- Широко поддерживается языками моделирования (AMPL, GAMS, Pyomo, JuMP), что позволяет быстро создавать прототипы.
Применение
- Цепочка поставок и логистика: маршрутизация транспортных средств, размещение объектов и оптимизация запасов с целочисленными количествами отгрузки.
- Планирование рабочей силы: составление расписаний медсестер, назначение экипажей и планирование смен с использованием бинарных переменных назначения.
- Бюджетное ограничение: выбор портфеля неделимых инвестиционных проектов при бюджетных ограничениях.
- Телекоммуникации и проектирование сетей: расширение мощностей и маршрутизация с бинарными решениями об активации каналов.
- Энергетические системы: согласование агрегатов в энергосетях, определяющее, какие генераторы включать или выключать каждый час.
- Производство: определение размеров партий продукции, планирование станков и задачи раскроя с целочисленными размерами партий.
Как это работает
Как это работает
Определить модель оптимизации: целевая функция (линейная комбинация переменных решения для минимизации или максимизации), линейные ограничения-неравенства и равенства, а также требования целочисленности. Непрерывные переменные обрабатывают количества, которые могут быть дробными; бинарные (0/1) или общие целочисленные переменные обрабатывают дискретные решения.
Формула
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pРешить LP-релаксацию, временно отбросив ограничения целочисленности. Это дает нижнюю границу (для минимизации) оптимальной целевой функции MIP и кандидатное решение, которое может быть дробным.
Формула
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0Выбрать дробную целочисленную переменную из решения LP-релаксации. Создать две дочерние подзадачи, добавив ограничение на округление вниз в одной и ограничение на округление вверх в другой, разделяя допустимое пространство без потери каких-либо целочисленных допустимых точек.
Формула
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilРешить LP-релаксацию каждой подзадачи. Если граница хуже, чем наилучшее найденное целочисленное решение (инкамбент), отсечь эту ветвь. Если решение LP случайно является целочисленным, обновить инкамбент, если оно улучшает целевую функцию.
Формула
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}Необязательно добавлять отсекающие плоскости — допустимые неравенства, которые отсекают дробное решение LP, не удаляя ни одной целочисленной допустимой точки. Отсечения Гомори — классический подход; специфичные для задачи отсечения (например, отсечения клик, отсечения потоков) могут значительно уменьшить размер дерева.
Формула
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}Остановиться, когда дерево ветвей и границ полностью исследовано, или когда разрыв между наилучшим целочисленным решением и глобальной нижней границей попадает в заданный пользователем допуск (например, 0,01%). Вернуть инкамбентное решение с его сертификатом оптимальности.
Формула
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonЧастые ошибки
- Выбор слишком малого допуска на разрыв оптимальности может привести к бесконечной работе решателя; всегда устанавливайте практический разрыв (например, 1%) для больших экземпляров.
- Симметрия в модели (например, взаимозаменяемые объекты) создает избыточные ветви и раздувает дерево поиска — используйте ограничения, нарушающие симметрию.
- Слабые LP-релаксации (большой целочисленный разрыв) приводят к очень большим деревьям ветвей и границ; инвестируйте время в добавление допустимых неравенств или уточнение формулировки.
- Обработка всех переменных как целочисленных, когда это необходимо только для некоторых, излишне затратна; используйте бинарные переменные только там, где этого требуют логические ограничения.
- Игнорирование начального старта с хорошим начальным допустимым решением — пустая трата времени решателя на поиск первого инкамбента.
Часто задаваемые вопросы
Чем MIP отличается от линейного программирования (LP)?
LP требует, чтобы все переменные решения были непрерывными (вещественными), что может привести к дробным решениям, которые физически невыполнимы (например, 2,7 грузовика). MIP добавляет ограничения целочисленности на некоторые или все переменные, обеспечивая целочисленные или бинарные решения ценой большей вычислительной сложности.
Когда следует использовать эвристику вместо MIP?
Когда задача имеет миллионы переменных, сильно нелинейную структуру или требует решения в режиме, близком к реальному времени, точный MIP может быть слишком медленным. Метаэвристики (генетические алгоритмы, имитация отжига) могут быстро давать хорошие решения, но без гарантий оптимальности. MIP предпочтительнее, когда важна сертификация качества решения.
Что такое разрыв оптимальности и насколько малым он должен быть?
Разрыв равен (объектив инкамбента - граница LP) / граница LP, выраженный в процентах. Он удостоверяет, насколько лучшее известное целочисленное решение может отличаться от истинного оптимума. Для большинства практических применений разрыв в 0,1–1% достаточен; более узкие разрывы требуют экспоненциально больше времени решателя.
Может ли MIP обрабатывать нелинейные целевые функции или ограничения?
Стандартный MIP предполагает линейность. Нелинейные зависимости должны быть линеаризованы (например, кусочно-линейная аппроксимация, бинарное разложение произведений) или обрабатываться решателями смешанного нелинейного программирования (MINLP), которые значительно сложнее решать.
Какие решатели рекомендуются для MIP?
Коммерческие: Gurobi и CPLEX являются отраслевыми эталонами. Открытый исходный код: SCIP, CBC (через COIN-OR) и HiGHS конкурентоспособны для задач умеренного размера. Все они поддерживают стандартные интерфейсы моделирования, такие как AMPL, Pyomo и JuMP.
Похожие методы
Источники
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN: 9780471359432Скопировано.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Скопировано.