Skip to content
Назад к результатам поиска

Целочисленное программирование — ЦП и смешанное целочисленное программирование (СЦП)

Автор метода
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-трудным; время решения может расти экспоненциально с размером задачи и плохой формулировкой.
  • Слабое ЛП-расслабление (большой разрыв целочисленности) приводит к глубоким, дорогостоящим деревьям поиска и длительному времени выполнения.
  • Бинарное разложение категориальных переменных с большой кардинальностью может привести к взрыву размера модели.
  • Для очень больших экземпляров решатели могут потребоваться досрочно завершить с допуском по разрыву, а не достичь нулевого разрыва.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Производит точные оптимальные решения с сертифицированным разрывом оптимальности, в отличие от эвристик, которые не дают гарантии качества.
  • Обрабатывает бинарные и общие целочисленные переменные нативно, что делает его естественной основой для комбинаторных решений.
  • Применимо к широкому спектру прикладных задач — планирование, маршрутизация, распределение, задача о рюкзаке — с использованием одного и того же математического аппарата.
  • Современные решатели ветвей и отсечений могут решать задачи с миллионами переменных и ограничений, которые десятилетия назад были бы неразрешимы.

Применение

  • Планирование персонала и медсестер — назначение смен для удовлетворения требований к охвату при соблюдении правил рабочего времени.
  • Маршрутизация транспортных средств и логистика — поиск маршрутов доставки с минимальными затратами при ограничениях по вместимости и временным окнам.
  • Размещение объектов — решение о том, какие склады или заводы открыть, чтобы минимизировать общие затраты на распределение.
  • Капитальное бюджетирование — выбор портфеля инвестиционных проектов в рамках бюджета для максимизации общей доходности.
  • Планирование производства — определение целочисленных размеров партий в различные периоды времени для балансировки затрат на наладку и затрат на хранение.
  • Проектирование сетей — выбор, какие каналы связи или транспортные сети установить.

Как это работает

Как это работает

1

Задача формулируется как математическая программа: определить переменные решения (которые должны быть объявлены как целочисленные или бинарные, где это требуется задачей), записать линейную целевую функцию для минимизации или максимизации и перечислить все линейные ограничения. Точная формулировка — та, чье непрерывное (ЛП) расслабление максимально приближено к истинному целочисленному оптимуму — значительно сокращает время решения.

2

Ограничения целочисленности временно снимаются для получения ЛП-расслабления. Решение этого расслабления происходит быстро и дает границу: его оптимальное значение всегда не хуже истинного целочисленного оптимума (нижняя граница для минимизации). Если решение расслабления случайно оказывается полностью целочисленным, задача решена. В противном случае разрыв между расслаблением и целочисленностью направляет поиск.

3

Дробная переменная в решении расслабления выбирается, и задача разбивается на две подзадачи — одна требует округления этой переменной вниз, другая — вверх. Каждая подзадача сама по себе расслабляется и решается, создавая дерево поиска. Ветви, чья граница расслабления хуже лучшего найденного целочисленного решения, отсекаются без дальнейшего исследования.

4

Отсекающие плоскости — это допустимые линейные неравенства, которые отсекают часть допустимой области ЛП-расслабления, не удаляя ни одной целочисленной допустимой точки. Добавление сильных отсечений (отсечения Гомори, неравенства покрытия, кликовые неравенства) сужает ЛП-границу и уменьшает количество узлов, которые должен исследовать решатель.

5

Лучшее целочисленное допустимое решение, найденное во всех исследованных узлах, возвращается как оптимальное. Сообщается о разрыве оптимальности — процентной разнице между лучшим целочисленным решением и лучшей оставшейся границей; разрыв в ноль сертифицирует глобальную оптимальность. Для больших NP-трудных экземпляров решатель может завершиться досрочно с заданным пользователем допуском по разрыву, возвращая почти оптимальное решение с доказуемой границей.

Частые ошибки

  • Объявление переменных как непрерывных, когда они должны быть целочисленными — или наоборот — молчаливо приводит к неправильным решениям; всегда проверяйте, соответствуют ли типы переменных физической реальности задачи.
  • Слабая формулировка с большим разрывом ЛП-расслабления вызывает чрезмерное ветвление; инвестируйте время в уточнение формулировки (сильные неравенства, разбиение симметрии) перед решением.
  • Игнорирование разрыва целочисленности в выходных данных решателя: сообщенное значение цели является лишь лучшим найденным целочисленным решением, а не обязательно глобальным оптимумом, если разрыв не равен нулю.
  • Применение ЦП к задачам, цель или ограничения которых нелинейны, без соответствующей обработки СНЦП приведет к некорректным моделям.
  • Для задач планирования или маршрутизации, не добавление допустимых неравенств (таких как кликовые или покрытия) оставляет существенные выгоды в производительности неиспользованными.

Часто задаваемые вопросы

В чем разница между ЦП и СЦП?

В чистом целочисленном программировании (ЦП) каждая переменная решения должна быть целым числом. В смешанном целочисленном программировании (СЦП) некоторые переменные являются целочисленными или бинарными, в то время как другие могут быть непрерывными. СЦП является более общей и чаще используемой основой на практике, поскольку большинство реальных задач сочетают дискретные выборы с непрерывными количествами.

Почему целочисленное программирование NP-трудно, если линейное программирование полиномиально?

Линейное программирование оптимизирует выпуклый многогранник и может быть решено за полиномиальное время методами симплекс или внутренних точек. Добавление ограничений целочисленности разрушает эту выпуклость: допустимое множество становится конечным, но потенциально астрономически большим множеством целочисленных точек, и ни один полиномиальный алгоритм в общем случае неизвестен для поиска лучшей из них. ЛП-расслабление дает границу, но не прямое решение.

Как узнать, оптимально ли мое решение?

Решатель сообщает о разрыве оптимальности — процентной разнице между лучшим найденным целочисленным решением и лучшей оставшейся нижней границей. Разрыв в 0% гарантирует глобальную оптимальность. Для больших задач вы можете установить допуск по разрыву (например, 1%) и принять почти оптимальное решение; граница по-прежнему гарантирует, что истинный оптимум не может быть лучше более чем на этот процент.

Что делает формулировку «точной» и почему это важно?

Точная формулировка — это та, чье ЛП-расслабление дает границу, близкую к целочисленному оптимуму, оставляя небольшой разрыв целочисленности. Когда разрыв мал, ветвям и границам требуется исследовать меньше узлов, и они завершаются быстрее. Добавление допустимых неравенств, таких как отсечения Гомори, неравенства покрытия или кликовые неравенства, уточняет формулировку и часто является наиболее эффективным способом ускорения работы решателя.

Похожие методы

Источники

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN: 9780471283669
    Скопировано.
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN: 9780471359432
    Скопировано.