Lagrangean relaxation

This paper reviews some of the most intriguing results and questions related to Lagrangean relaxation. It recalls essential properties of the Lagrangean relaxation and of the Lagrangean function, describes several algorithms to solve the Lagrangean dual problem and considers Lagrangean heuristics, ad-hoc or generic, because these are an integral part of any Lagrangean approximation scheme. It discusses schemes that can potentially improve the Lagrangean relaxation bound, and describes several applications of Lagrangean relaxation, which demonstrate the flexibility of the approach, and permit either the computation of strong bounds on the optimal value of the MIP problem, or the use of a Lagrangean heuristic, possibly followed by an iterative improvement heuristic. The paper also analyzes several interesting questions, such as why it is sometimes possible to get a strong bound by solving simple problems, and why an a-priori weaker relaxation can sometimes be “just as good” as an a-priori stronger one.