Генерация столбца - Column generation

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

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

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

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

Во многих случаях это позволяет решать большие линейные программы, которые ранее считались неразрешимыми. Классическим примером проблемы, в которой это успешно используется, является проблема с режущим материалом. Одним из конкретных методов линейного программирования, в котором используется такой подход, является Разложение Данцига – Вульфа алгоритм. Кроме того, создание столбцов применялось ко многим задачам, таким как расписание экипажа, движение транспорта, а емкостная задача p-медианы.