Lagrangian Relaxation

Monique Guignard

ABSTRACT

This article presents material necessary for understanding and designing efficient Lagrangian relaxations for integer programming problems. It suggests various ways in which Lagrangian relaxation can be applied and presents possible extensions. It reviews essential properties of the Lagrangian function, and describes several algorithms to solve the Lagrangian dual problem. Finally it mentions Lagrangian heuristics, ad hoc or generic, as these are an integral part of any Lagrangian approximation scheme.