Целочисленное программирование — ЦП и смешанное целочисленное программирование (СЦП)
- Автор метода
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- Год
- 1958
- Тип
- Mathematical optimisation — exact combinatorial method
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Целочисленное программирование (ЦП), также называемое смешанным целочисленным программированием (СЦП), когда только некоторые переменные ограничены целыми числами, является разделом математической оптимизации, в котором некоторые или все переменные решения должны принимать целочисленные или бинарные значения.
Основываясь на линейном программировании, оно было формализовано методом отсекающих плоскостей Ральфа Гомори (1958) и алгоритмом ветвей и границ Лэнда и Дуига (1960), и с тех пор стало стандартной точной основой для задач планирования, распределения, маршрутизации и распределения ресурсов.
Интуиция метода
Обычное линейное программирование находит наилучшую точку в непрерывной допустимой области. Но многие реальные решения дискретны — нельзя укомплектовать штат 2,7 медсестрами или открыть половину склада. Целочисленное программирование добавляет ограничение, что некоторые или все переменные должны быть целыми числами (или бинарными выборами 0/1). Цена этого ограничения — вычислительная: допустимое множество больше не является гладкой поверхностью, а представляет собой разрозненное множество точек, и поиск наилучшей может потребовать изучения огромного количества кандидатов. Решатели управляют этим, интеллектуально разбивая задачу на более мелкие подзадачи (ветвление) и отсекая ветви, которые не могут превзойти лучшее найденное решение (ограничение), а также сужая непрерывное приближение путем добавления неравенств (отсекающие плоскости).
История
Целочисленное программирование возникло в конце 1950-х годов, когда исследователи стремились расширить линейное программирование на дискретные решения. Ральф Гомори представил систематический метод отсекающих плоскостей в 1958 году, доказав, что любую целочисленную программу в принципе можно решить, добавив конечное число отсечений. Лэнд и Дуиг (1960) формализовали метод ветвей и границ, который стал доминирующим точным алгоритмом. Уолси (1998) и Немхаузер и Уолси (1988) предоставили канонические учебные пособия, на которые до сих пор опирается эта область. Практическая революция произошла с разработкой решателей ветвей и отсечений в 1990-х годах, объединивших обе техники с передовыми эвристиками, а затем со взрывным ростом производительности коммерческих и открытых решателей, который сегодня позволяет решать крупномасштабные реальные задачи.
Когда применять
Используйте целочисленное программирование, когда решения по своей сути дискретны — бинарные выборы да/нет, целочисленные количества или логические ограничения вкл/выкл — и когда вам нужно точное или почти точное оптимальное решение с доказуемым качественным пределом. Оно подходит для задач планирования, назначения экипажа и ресурсов, маршрутизации транспортных средств, размещения объектов, капитального бюджетирования и выбора портфеля. Минимальный размер выборки не требуется, поскольку ЦП является детерминированной оптимизационной основой, а не процедурой статистического вывода. Типы переменных могут быть бинарными, категориальными (закодированными как бинарные) или непрерывными (в смешанном целочисленном случае). Ключевым практическим требованием является то, что задача может быть смоделирована с линейной целью и линейными ограничениями; если цель или ограничения нелинейны, требуются расширения смешанного нелинейного целочисленного программирования (СНЦП).
Ограничения и замечания
- Целочисленное программирование в общем случае является NP-трудным; время решения может расти экспоненциально с размером задачи и плохой формулировкой.
- Слабое ЛП-расслабление (большой разрыв целочисленности) приводит к глубоким, дорогостоящим деревьям поиска и длительному времени выполнения.
- Бинарное разложение категориальных переменных с большой кардинальностью может привести к взрыву размера модели.
- Для очень больших экземпляров решатели могут потребоваться досрочно завершить с допуском по разрыву, а не достичь нулевого разрыва.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Производит точные оптимальные решения с сертифицированным разрывом оптимальности, в отличие от эвристик, которые не дают гарантии качества.
- Обрабатывает бинарные и общие целочисленные переменные нативно, что делает его естественной основой для комбинаторных решений.
- Применимо к широкому спектру прикладных задач — планирование, маршрутизация, распределение, задача о рюкзаке — с использованием одного и того же математического аппарата.
- Современные решатели ветвей и отсечений могут решать задачи с миллионами переменных и ограничений, которые десятилетия назад были бы неразрешимы.
Применение
- Планирование персонала и медсестер — назначение смен для удовлетворения требований к охвату при соблюдении правил рабочего времени.
- Маршрутизация транспортных средств и логистика — поиск маршрутов доставки с минимальными затратами при ограничениях по вместимости и временным окнам.
- Размещение объектов — решение о том, какие склады или заводы открыть, чтобы минимизировать общие затраты на распределение.
- Капитальное бюджетирование — выбор портфеля инвестиционных проектов в рамках бюджета для максимизации общей доходности.
- Планирование производства — определение целочисленных размеров партий в различные периоды времени для балансировки затрат на наладку и затрат на хранение.
- Проектирование сетей — выбор, какие каналы связи или транспортные сети установить.
Как это работает
Как это работает
Задача формулируется как математическая программа: определить переменные решения (которые должны быть объявлены как целочисленные или бинарные, где это требуется задачей), записать линейную целевую функцию для минимизации или максимизации и перечислить все линейные ограничения. Точная формулировка — та, чье непрерывное (ЛП) расслабление максимально приближено к истинному целочисленному оптимуму — значительно сокращает время решения.
Ограничения целочисленности временно снимаются для получения ЛП-расслабления. Решение этого расслабления происходит быстро и дает границу: его оптимальное значение всегда не хуже истинного целочисленного оптимума (нижняя граница для минимизации). Если решение расслабления случайно оказывается полностью целочисленным, задача решена. В противном случае разрыв между расслаблением и целочисленностью направляет поиск.
Дробная переменная в решении расслабления выбирается, и задача разбивается на две подзадачи — одна требует округления этой переменной вниз, другая — вверх. Каждая подзадача сама по себе расслабляется и решается, создавая дерево поиска. Ветви, чья граница расслабления хуже лучшего найденного целочисленного решения, отсекаются без дальнейшего исследования.
Отсекающие плоскости — это допустимые линейные неравенства, которые отсекают часть допустимой области ЛП-расслабления, не удаляя ни одной целочисленной допустимой точки. Добавление сильных отсечений (отсечения Гомори, неравенства покрытия, кликовые неравенства) сужает ЛП-границу и уменьшает количество узлов, которые должен исследовать решатель.
Лучшее целочисленное допустимое решение, найденное во всех исследованных узлах, возвращается как оптимальное. Сообщается о разрыве оптимальности — процентной разнице между лучшим целочисленным решением и лучшей оставшейся границей; разрыв в ноль сертифицирует глобальную оптимальность. Для больших NP-трудных экземпляров решатель может завершиться досрочно с заданным пользователем допуском по разрыву, возвращая почти оптимальное решение с доказуемой границей.
Частые ошибки
- Объявление переменных как непрерывных, когда они должны быть целочисленными — или наоборот — молчаливо приводит к неправильным решениям; всегда проверяйте, соответствуют ли типы переменных физической реальности задачи.
- Слабая формулировка с большим разрывом ЛП-расслабления вызывает чрезмерное ветвление; инвестируйте время в уточнение формулировки (сильные неравенства, разбиение симметрии) перед решением.
- Игнорирование разрыва целочисленности в выходных данных решателя: сообщенное значение цели является лишь лучшим найденным целочисленным решением, а не обязательно глобальным оптимумом, если разрыв не равен нулю.
- Применение ЦП к задачам, цель или ограничения которых нелинейны, без соответствующей обработки СНЦП приведет к некорректным моделям.
- Для задач планирования или маршрутизации, не добавление допустимых неравенств (таких как кликовые или покрытия) оставляет существенные выгоды в производительности неиспользованными.
Часто задаваемые вопросы
В чем разница между ЦП и СЦП?
В чистом целочисленном программировании (ЦП) каждая переменная решения должна быть целым числом. В смешанном целочисленном программировании (СЦП) некоторые переменные являются целочисленными или бинарными, в то время как другие могут быть непрерывными. СЦП является более общей и чаще используемой основой на практике, поскольку большинство реальных задач сочетают дискретные выборы с непрерывными количествами.
Почему целочисленное программирование NP-трудно, если линейное программирование полиномиально?
Линейное программирование оптимизирует выпуклый многогранник и может быть решено за полиномиальное время методами симплекс или внутренних точек. Добавление ограничений целочисленности разрушает эту выпуклость: допустимое множество становится конечным, но потенциально астрономически большим множеством целочисленных точек, и ни один полиномиальный алгоритм в общем случае неизвестен для поиска лучшей из них. ЛП-расслабление дает границу, но не прямое решение.
Как узнать, оптимально ли мое решение?
Решатель сообщает о разрыве оптимальности — процентной разнице между лучшим найденным целочисленным решением и лучшей оставшейся нижней границей. Разрыв в 0% гарантирует глобальную оптимальность. Для больших задач вы можете установить допуск по разрыву (например, 1%) и принять почти оптимальное решение; граница по-прежнему гарантирует, что истинный оптимум не может быть лучше более чем на этот процент.
Что делает формулировку «точной» и почему это важно?
Точная формулировка — это та, чье ЛП-расслабление дает границу, близкую к целочисленному оптимуму, оставляя небольшой разрыв целочисленности. Когда разрыв мал, ветвям и границам требуется исследовать меньше узлов, и они завершаются быстрее. Добавление допустимых неравенств, таких как отсечения Гомори, неравенства покрытия или кликовые неравенства, уточняет формулировку и часто является наиболее эффективным способом ускорения работы решателя.
Похожие методы
Источники
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN: 9780471283669Скопировано.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN: 9780471359432Скопировано.