Генерация столбцов (Данциг-Вольф)
- Автор метода
- George B. Dantzig and Philip Wolfe
- Год
- 1960
- Тип
- algorithm
- Семейство
- Optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Генерация столбцов, разработанная Джорджем Б. Данцигом и Филипом Вулфом в 1960 году, представляет собой мощный метод оптимизации для решения крупномасштабных задач линейного программирования со специальной структурой.
Также известная как декомпозиция Данцига-Вулфа, она декомпозирует задачу на главную задачу (ограниченную подмножеством переменных/столбцов) и подзадачу ценообразования (идентифицирующую новые переменные), итеративно улучшая решение путем введения только релевантных столбцов.
Интуиция метода
Метод признает, что многие крупные оптимизационные задачи имеют особую структуру: множество переменных, но мало действительно важных ограничений, или естественно декомпозируемые подзадачи. Вместо решения полной задачи со всеми возможными переменными, генерация столбцов поддерживает только небольшое подмножество перспективных столбцов (переменных). Подзадача ценообразования, решаемая с использованием приведенных стоимостей и структуры задачи, идентифицирует новые столбцы, которые улучшают главное решение. Путем итеративного добавления наиболее перспективных столбцов алгоритм эффективно строит решение, избегая вычислительной нагрузки, связанной с одновременной обработкой всех столбцов.
История
Данциг и Вулф ввели принцип декомпозиции для линейных программ в 1960 году, заложив теоретическую основу. Гилмор и Гомори (1961) применили его к задаче раскроя, продемонстрировав практическую мощь. Метод получил известность для задач маршрутизации транспортных средств и составления расписаний в 1980-90-х годах. Интеграция с методом ветвей и границ, создание алгоритмов branch-and-price, расширила применимость к целочисленному программированию. Современные приложения включают составление расписаний экипажей авиакомпаний, маршрутизацию судов и крупномасштабную оптимизацию логистики.
Когда применять
Применяйте генерацию столбцов при решении крупномасштабных линейных программ со специальной структурой, особенно когда число переменных огромно, но небольшое подмножество доминирует в оптимальном решении. Она идеально подходит для задач раскроя, маршрутизации транспортных средств, составления расписаний экипажей и упаковки в контейнеры. Используйте ее, когда структура задачи позволяет эффективно решать подзадачу ценообразования. Для задач без эксплуатируемой структуры или умеренного размера стандартные решатели линейного программирования более практичны.
Ограничения и замечания
- Требует структуры задачи, обеспечивающей эффективное решение подзадачи ценообразования.
- Сходимость может быть медленной, особенно вблизи оптимальности (эффект «хвостового затухания»).
- Решение подзадачи ценообразования должно быть надежным и эффективным, иначе выигрыш в эффективности теряется.
- Сложность реализации выше, чем у стандартных методов линейного программирования.
- Проблемы численной устойчивости с большими двойственными значениями и приведенными стоимостями.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Решает крупномасштабные задачи, неразрешимые стандартными методами из-за «взрыва» числа столбцов.
- Использует структуру задачи для генерации только релевантных столбцов.
- Обеспечивает границы качества решения во время итераций.
- Естественно подходит для задач со специальной подструктурой (идентичные подзадачи, симметрия).
- Интегрируется с методом ветвей и границ для целочисленных программ (branch-and-price).
Применение
- Задача раскроя: минимизация отходов при раскрое материала на требуемые размеры.
- Маршрутизация транспортных средств: оптимизация маршрутов доставки и транспортировки с учетом временных окон и ограничений по вместимости.
- Составление расписаний экипажей: назначение членов экипажа на рейсы или смены с минимизацией общих затрат.
- Упаковка в контейнеры: эффективная упаковка предметов в контейнеры для минимизации отходов и количества контейнеров.
- Составление графиков дежурств: планирование работы сотрудников по сменам с учетом доступности и предпочтений.
- Планирование авиаперевозок: составление расписания рейсов, назначение экипажей и координация технического обслуживания самолетов.
Как это работает
Как это работает
Начните с ограниченной главной задачи, содержащей только подмножество столбцов, необходимых для начального допустимого решения.
Решите двойственную задачу текущей ограниченной главной задачи, используя симплекс-таблицу. Определите приведенные стоимости и настройте подзадачу ценообразования для поиска переменных с отрицательной приведенной стоимостью (для минимизации).
Решите подзадачу ценообразования, используя ее специальную структуру. Если найден новый столбец с отрицательной приведенной стоимостью, добавьте его к главной задаче и повторите. Если улучшающего столбца не существует, текущее решение является оптимальным.
Частые ошибки
- Выбор неэффективного алгоритма для подзадачи ценообразования, что нивелирует выигрыш в эффективности от генерации столбцов.
- Неспособность распознать структуру задачи, подходящую для декомпозиции, что приводит к низкой производительности.
- Неадекватное обнаружение сходимости или слишком строгий допуск, что приводит к потере итераций.
- Неиспользование методов стабилизации для устранения эффекта «хвостового затухания».
Часто задаваемые вопросы
Что такое подзадача ценообразования в генерации столбцов и как она связана с приведенными стоимостями?
Подзадача ценообразования идентифицирует новые переменные (столбцы) с отрицательной приведенной стоимостью, которые улучшают главное решение. Значения приведенных стоимостей берутся из двойственной задачи ограниченной главной задачи и направляют поиск в подзадаче ценообразования.
Почему генерация столбцов лучше, чем решение полной задачи со всеми столбцами?
Во многих задачах число потенциальных столбцов является экспоненциальным или бесконечным, что делает невозможным перечисление всех. Генерация столбцов генерирует только необходимые столбцы по требованию, значительно снижая вычислительную нагрузку.
Что такое эффект «хвостового затухания» и как его можно смягчить?
«Хвостовое затухание» возникает, когда генерация столбцов медленно продвигается к оптимальности, генерируя много столбцов с минимальным улучшением. Методы стабилизации (сглаживание двойственных переменных, методы доверительной области, стратегии отсечения) уменьшают его влияние.
Как branch-and-price расширяет генерацию столбцов на целочисленное программирование?
Branch-and-price объединяет генерацию столбцов с методом ветвей и границ: в каждом узле генерация столбцов решает релаксацию линейного программирования, а решения о ветвлении дополнительно ограничивают задачу, когда решения линейного программирования являются дробными.
Похожие методы
Источники
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
Открыть ссылку DOIСкопировано.Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.
Открыть ссылку DOIСкопировано.