The use of Lagrangean Relaxation in the solution of uncapacitated facility location problems

This paper reviews the use of Lagrangean Relaxation in the solution of uncapacitated facility location problems. This technique has been widely and successfully applied to a variety of combinatorial optimization problems. Applications to static, dynamic and covering location models are studied in detail. Within location theory, Lagrangean Relaxation has been most widely used in static uncapacitated problems. Its use for dynamic and covering models has been more restricted; future research effort in these areas holds promise for further successful use.