Смешанное целочисленное программирование с множеством целевых функций
- Автор метода
- Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
- Год
- 1980s–2000s
- Тип
- Mathematical optimization
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Смешанное целочисленное программирование с множеством целевых функций (MO-MIP) — это оптимизационная структура, которая одновременно оптимизирует две или более конфликтующие целевые функции при линейных или нелинейных ограничениях, где некоторые переменные решения ограничены целочисленными значениями, а другие являются непрерывными.
Оно широко применяется в проектировании, планировании цепочек поставок, распределении ресурсов и задачах составления расписаний, требующих дискретных выборов наряду с непрерывными величинами.
Интуиция метода
Многие реальные решения включают как дискретные выборы (сколько объектов открыть, какие проекты финансировать, покупать ли станок), так и непрерывные решения (сколько производить, как распределить бюджет). Когда эти выборы одновременно влияют на несколько конфликтующих целей — например, минимизировать затраты при одновременном максимизации уровня обслуживания — не существует единственного оптимального решения. Вместо этого MO-MIP исследует границу компромиссов (множество Парето) всех недоминируемых решений, предоставляя лицам, принимающим решения, структурированную карту допустимых компромиссов, а не единственно навязанный ответ.
История
Смешанное целочисленное программирование было формализовано в 1950-х–1960-х годах благодаря работам Гомори и Лэнда и Дойг. Многоцелевые расширения появились в 1970-х–1980-х годах, когда исследователи осознали, что многие задачи проектирования и исследования операций включают конкурирующие цели. Систематическое рассмотрение было консолидировано Эргготтом (2005) и Мавротасом (2009), чья реализация метода эпсилон-ограничений остается широко цитируемым источником для практического MO-MIP.
Когда применять
Используйте MO-MIP, когда задача принятия решений естественным образом включает целочисленные или бинарные переменные (выбор местоположения объектов, выбор проектов, составление расписаний) наряду с непрерывными величинами, и когда необходимо явно учитывать компромиссы между двумя или более конфликтующими целями. Он подходит, когда требуются точные или близкие к точным решения Парето, и вычислительные ресурсы позволяют использовать поиск методом ветвей и границ. НЕ используйте его, когда все переменные непрерывны (вместо этого используйте линейное программирование с множеством целевых функций или нелинейное программирование), когда масштаб задачи делает точное решение MIP неразрешимым, а метаэвристики более практичны, или когда достаточно одной агрегированной цели, и многоцелевой анализ не добавляет ценности для принятия решений.
Ограничения и замечания
- Вычислительная стоимость экспоненциально растет с увеличением числа целочисленных переменных и размера задачи; большие экземпляры могут быть неразрешимы для точных методов.
- Требует точной формулировки всех целей и ограничений в математической форме, что может быть затруднительно для качественных или неоднозначных реальных целей.
- Методы скаляризации, такие как взвешенная сумма, не могут обнаружить решения в невыпуклых областях фронта Парето, потенциально упуская важные компромиссы.
- Генерация плотного фронта Парето требует решения множества подзадач MIP, что увеличивает общее время вычислений.
- Результаты чувствительны к формулировке ограничений и точности данных задачи; недопустимые или плохо ограниченные модели дают бесполезный результат.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Предоставляет доказуемо оптимальные или близкие к оптимальным решения для каждой скаляризованной подзадачи, гарантируя качество фронта Парето для решаемых размеров задач.
- Естественным образом обрабатывает реальные дискретные выборы (бинарные решения, целочисленные величины), которые непрерывные релаксации не могут точно представить.
- Дает полный фронт Парето, предоставляя лицам, принимающим решения, прозрачную, структурированную информацию о компромиссах, а не один вынужденный компромисс.
- Метод эпсилон-ограничений и другие систематические скаляризации позволяют контролируемое, плотное исследование недоминируемого множества решений.
- Совместим с широким спектром коммерческих и открытых решателей (CPLEX, Gurobi, GLPK, CBC), которые обрабатывают крупномасштабные задачи MIP.
Применение
- Размещение объектов и проектирование сетей поставок: одновременная минимизация затрат и максимизация охвата обслуживания клиентов с использованием бинарных переменных открытия/закрытия.
- Бюджетирование капитала и выбор портфеля проектов: максимизация доходности и минимизация риска при ограничениях бюджета и ресурсов с использованием бинарных переменных выбора проектов.
- Планирование производства: одновременная минимизация времени выполнения и опозданий с использованием целочисленных размеров партий и бинарных переменных назначения машин.
- Планирование энергетических систем: оптимизация затрат и выбросов CO2 для смешанного парка электростанций с дискретными решениями об инвестициях и непрерывными переменными диспетчеризации.
- Распределение ресурсов здравоохранения: максимизация охвата пациентов и справедливости при одновременной минимизации расходов с использованием целочисленных переменных штатного расписания и бинарных переменных объектов.
- Транспорт и логистика: одновременная минимизация времени в пути и выбросов с использованием целочисленных переменных парка транспортных средств и маршрутизации.
Как это работает
Как это работает
Сформулируйте задачу, определив k целевых функций f_1(x), ..., f_k(x), которые нужно минимизировать или максимизировать, набор линейных или нелинейных ограничений Ax <= b и области переменных, где некоторые переменные являются целочисленными (например, бинарными 0/1), а другие — непрерывными. Четко определите границы и данные перед решением.
Примените стратегию скаляризации или декомпозиции для преобразования многоцелевой задачи в последовательность одноцелевых подзадач MIP. Распространенные стратегии включают метод взвешенной суммы (минимизировать сумму w_i * f_i), метод эпсилон-ограничений (оптимизировать одну цель, ограничивая другие пороговыми значениями) и функции достижения скаляризации.
Решите каждую скаляризованную подзадачу MIP, используя метод ветвей и границ (branch-and-bound), ветвей и отсечений (branch-and-cut) или другой точный решатель (например, CPLEX, Gurobi, GLPK). Для каждой подзадачи решатель исследует целочисленное допустимое пространство решений, применяя релаксации ЛП в каждом узле и отсекая недопустимые или доминируемые ветви.
Соберите все недоминируемые решения из всех запусков подзадач для аппроксимации или точного построения множества Парето. Два решения недоминируемы, если ни одно из них не является строго лучше другого по всем целям. Повторяйте цикл скаляризации-решения с измененными параметрами, чтобы уплотнить фронт.
Представьте множество Парето лицам, принимающим решения, с поддерживающими визуализациями (диаграммы рассеяния, графики параллельных координат). Примените правила принятия решений по нескольким критериям, предпочтения заинтересованных сторон или лексикографический порядок для выбора предпочтительного решения из недоминируемого множества для реализации.
Частые ошибки
- Использование метода взвешенной суммы в невыпуклых пространствах целей приведет к упущению целых сегментов фронта Парето; в таких случаях предпочтительнее использовать метод эпсилон-ограничений или дополненные функции достижения скаляризации.
- Рассмотрение целочисленных переменных как непрерывных в релаксации с последующим округлением не гарантирует Парето-оптимальности и может привести к недопустимым или доминируемым решениям.
- Пренебрежение проверкой избыточности или жесткости ограничений перед решением может привести к чрезмерному времени выполнения решателя или ложным сообщениям о недопустимости.
- Представление всех решений Парето лицам, принимающим решения, без фильтрации или руководства по визуализации приводит к параличу принятия решений; всегда сопровождайте результаты структурированной поддержкой выбора.
- Предположение о полноте фронта Парето после слишком малого числа запусков скаляризации может привести к чрезмерно уверенным выводам; проверьте покрытие, проверив недоминируемость всех собранных решений.
Часто задаваемые вопросы
Чем MO-MIP отличается от стандартного линейного программирования с множеством целевых функций?
В линейном программировании с множеством целевых функций все переменные решения являются непрерывными, поэтому эффективные решения Парето могут быть найдены в вершинах выпуклого многогранника. MO-MIP требует, чтобы некоторые или все переменные были целочисленными, что делает допустимое множество невыпуклым и дискретным, что требует поиска методом ветвей и границ вместо методов на основе симплекс-метода.
Могу ли я использовать метаэвристики, такие как NSGA-II, вместо точных решателей MIP?
Да, и для крупномасштабных или комбинаторно сложных задач метаэвристики часто предпочтительнее, поскольку они лучше масштабируются. Компромисс заключается в том, что они предоставляют приближенные фронты Парето без гарантий оптимальности, в то время как точные решатели MO-MIP гарантируют недоминируемость найденных решений.
Что такое метод эпсилон-ограничений и почему он рекомендуется?
Метод эпсилон-ограничений оптимизирует одну цель, ограничивая все остальные, чтобы они не были хуже заданных границ (эпсилон). Он может обнаруживать решения в невыпуклых областях Парето, которые упускает метод взвешенной суммы, что делает его более надежным для общих задач MO-MIP.
Сколько решений Парето следует генерировать?
Это зависит от количества целей и требуемой детализации для принятия решений. Для двух целей обычно достаточно 20–50 равномерно распределенных решений для характеристики фронта. Для трех и более целей количество растет комбинаторно; для избежания перегрузки решениями рекомендуются интерактивные методы или методы, управляемые предпочтениями.
Подходит ли MO-MIP для задач с неопределенностью в данных?
Стандартный MO-MIP предполагает детерминированные данные. Когда входные данные неопределенны, его следует комбинировать с расширениями робастной оптимизации или стохастического программирования — например, двухэтапным стохастическим MO-MIP или робастным MO-MIP с оценкой целей в наихудшем случае.
Похожие методы
Источники
Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.
ISBN: 9783540213987Скопировано.Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.
Открыть ссылку DOIСкопировано.