Improving traditional subgradient scheme for Lagrangean relaxation: An application to location problems

Lagrangean relaxation is largely used to solve combinatorial optimization problems. A known problem for Lagrangean relaxation application is the definition of convenient step size control in subgradient like methods. Even preserving theoretical convergence properties, a wrongly defined control can reflect in performance and increase computational times, a critical point in large scale instances. We show in this work how to accelerate a classical subgradient method, using the local information of the surrogate constraints relaxed in the Lagrangean relaxation. It results in a one-dimensional search that corrects the step size and is independent of the step size control used. The application of Capacitated and Uncapacitated Facility Location problems is shown. Several computational tests confirm the superiority of this scheme.