Дискретные задачи размещения Оптимизационные алгоритмы

Главная страница библиотеки  Демонстрационная версия Оптимизационные алгоритмы

Метод Лагранжевых релаксаций

В начале 70-х годов была высказана одна идея [1, 2], которая в последствии оказалась очень продуктивной при решении дискретных экстремальных задач. Многие NP-трудные задачи можно представить как “легкие” задачи с дополнительными отягощающими ограничениями. Лагранжевы релаксации получаются путем перехода к двойственной задаче относительно этого множества дополнительных ограничений. Релаксированная задача уже легко решается и ее оптимальное решение дает оценку снизу (в задачах на минимум) для целевой функции исходной задачи. Если разрыв двойственности равен нулю, то такой подход дает возможность найти оптимальное решение задачи и доказать его оптимальность. В противном случае, когда полученная нижняя оценка не является точной, она может быть использована в методе ветвей и границ или (и) служить начальным приближением для эвристических методов [3, 4].

Использовать множители Лагранжа в задачах дискретной оптимизации впервые предложил Эверетт [5] в 1963 году. Однако бум в этой области начался после выхода в свет работы Хэлда и Карна [6], посвященной задаче коммивояжера. Эта работа послужила толчком для теоретических и прикладных исследований в данной области. В 1973 г. выходит в свет работа Фишера [7], в которой этот подход используется для задач теории расписаний. В этом же году появляется статья Шапиро и Фишера [8], в которой метод Лагранжевых релаксаций развивается применительно к общей задаче целочисленного программирования. Сам термин Лагранжева релаксация был предложен Джеоффрионом [9]. В этой статье, написанной, по выражению автора, с педагогическими целями, сформулированы и доказаны основные теоремы. Однако центральный вопрос: “Каким образом вычислять множители Лагранжа?” — оставался открытым. В 1975 г. Фишер, Норшип и Шапиро [10] дали подробные теоретические разъяснения по этому поводу, а Хэлд, Волф и Краудер [11] дали конкретные практические рекомендации. В 1979 г. Шапиро [1] публикует обзор, в котором содержится обширная библиография по применению техники Лагранжевых релаксаций в задачах целочисленного программирования. В 1981 г. выходит аналогичный обзор Фишера [2]. К настоящему времени этот метод детально разработан и опробован для задач размещения, расписаний, назначений и др.

Пусть множество ограничений исходной задачи P разбито на две части

P:	min cx Ax b, Bx d x 0, целые

Под Лагранжевой релаксацией с множителями l 0 будем понимать задачу вида

LR (l):

min cx+ l (b - Ax) Bx d x 0, целые.

Задача, двойственная к задаче P относительно ограничений Ax b, по определению есть задача вида:

D:	max v(LP(l )), l 0,

где v(LP(l )l )) — оптимальное значение соответствующей релаксированной задачи LP(l ). В общем случае v(P) v(D), но величина v(D) может существенно зависить от разбиения системы ограничений на части. Заметим, что эти части могут пересекаться.

Среди методов решения задачи D наибольшее распространение получили методы субградиентной оптимизации. Эти итеративные процедуры формируют последовательность векторов {l^k}. Начиная с некоторого начального значения l⁰ эти вектора меняются по следующему правилу

l^k+1 = l^k + t_k (A x^k -  b),

где x^k — оптимальное решение задачи , а t_k — размер шага. Фундаментальный теоретический результат заключается в  том, что [14]

.

Размер шага  на практике обычно выбирают, следуя [11],

где q ^k — скаляр, 0 < q ^k 2  и z* — верхняя граница для n(D). Обычно z* получают эвристикой для P. В методе ветвей и границ z* — текущий рекорд. Последовательность q ^k, как правило, начинается с q  ⁰=2 и затем q ^k делится пополам, через фиксированное число итераций, зависящее от размерности задачи.
        Методам субградиентной оптимизации посвящено много публикаций и это специальная тема для исследований. Литературу по этой теме можно найти, например, в [11], [12], [13].

Литература:

1. Shapiro J.F. A survey of Lagrangian techniques for discrete optimization. Ann. Discrete Math. v5 (1979), pp 113-138.

2. Fisher M.L. The Lagrangian relaxation method for solving integer programming problems.Management Science, v27 (1981), pp 1-18.

3. Кочетов Ю.А., Пащенко М.Г. Лагранжевы релаксации для задачи выбора оптимального состава системы технических средств. Управляемые системы т31 (1993), с.26-39.

4. Helsgann K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research. v126 (2000), pp 106-130.

5. Everett H. Generalized lagrange multiplier method for solving problems of optimum allocation of resources. Operations Res. v2 (1963), pp 399-417.

6. Held M., Karp R.M.  The traveling salesman problem and minimum spanning trees. Part I: Operations Res. v18 (1970), pp 1138-1162, Part II: Mathematical Programming. v1 (1971), pp 6-25.

7. Fisher M.L. Optimal solution of scheduling problems using Lagrange multipliers: Part I. Operations Res. v21 (1973), pp 1114-1127.

8. Fisher M.L., Shapiro J.F. Constructive duality in integer programming. SIAM J. Appl. Math. v27 (1974), pp 31-52.

9. Geoffrion A.M. Lagrangian relaxation  for integer programming. Math. Programming Study. v2 (1974), pp 82-114.

10. Fisher M.L., Northup W.D., Shapiro J.F. Using duality to solve discrete optimization problems: Theory and computational experience. Math. Programming Study. v3 (1975), pp56-94.

11. Held M., Wolfe P., Crowder H.D. Validation of subgradient optimization. Mathematical Programming. v6 (1974), pp 62-88.

12. Wolfe P. A method of conjugate subgradients for minimizing nondifferentable functions. Math. Programming Study. v3 (1975), pp 145-173.

13. Шор Н.З. О скорости сходимости метода обобщенного градиентного спуска с растяжением прстранства. Кибернетика №2 (1970), с. 80-85.

14. Поляк Б.Т. Минимизация негладких функционалов, ИСВМ и МФ т9 (1969), №3, с. 509-521.