Генерация столбцов

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

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

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

Процесс работает следующим образом. Решаем основную задачу, из решения получаем двойственные переменные для каждого ограничения исходной задачи. Эта информация используется в целевой функции подзадачи. Решаем подзадачу. Если целевая функция подзадачи будет отрицательной, переменная с отрицательной приведённой ценой найдена и эту переменную добавляем в основную задачу и производим очередное решение основной задачи. Новое оптимальное решение основной задачи даст новые двойственные переменные, и процесс повторяется, пока решения подзадачи дают отрицательные значения. Когда решение подзадачи даст положительное значение целевой функции, мы можем заключить, что оптимальное решение основной задачи найдено.

Во многих случаях такой подход позволяет решать большие задачи линейного программирования. Классическим примером применения метода генерации столбцов является задача раскроя. Одна из техник линейного программирования, использующая тот же подход — разложение Данцига — Вулфа. Кроме того, генерация столбцов используется во многих задачах, таких как график работ[1], составление маршрутов и задача о p-медиане с ограничениями[2][3].

Генерация строк в методе переменного базиса

При решении больших задач методом переменного базиса (смотрите симплекс-метод, раздел «Метод переменного базиса») часто возникает подобный случай, когда можно генерировать не только столбцы, но и строки. Метод переменного базиса использует тот факт, что в больших задачах линейного программирования, в которых большинство ограничений задано неравенствами, большая часть ограничений не выходят на строгое ограничение (дополнительная переменная не равна нулю), а значит, такое ограничение можно не рассматривать в конечном решении. При решении задач методом переменного базиса можно решать ещё одну подзадачу — определение выводимого столбца. Используя такой подход можно решать некоторые задачи теории игр (смотрите, например, Игры Блотто), содержащие миллионы строк и столбцов.

Примечания
  1. Per Sjörgen. Solving the Master Linear Program in Column Generation Algorithms for Airline Crew Scheduling using a Subgradient Method. — 2009.
  2. Luiz A. N. Lorena, Edson L. F. Senne. Задача о p-медиане с ограничениями.
  3. P. Avella, A. Sassano, I. Vasil’ev. Computational study of large-scale p-median problems Technical Report 08-03. — Universit`a di Roma «La Sapienza», 2003. Приводится метод ветвей и границ для решения больших задач p-медиан. Используется метод генерации столбцов и строк для решения ослабленной задачи линейного программирования и отсекающих гиперплоскостей для усиления условий. Авторы утверждают, что удалось решить задачи с более чем 900 дугами графа.

Литература
  • J. Desaulniers, J. Desrosiers, M. Solomon. Column Generation. — New York: Springer, 2005.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.