| Article ID: | iaor19982424 |
| Country: | Belgium |
| Volume: | 35 |
| Issue: | 3/4 |
| Start Page Number: | 5 |
| End Page Number: | 21 |
| Publication Date: | Jan 1995 |
| Journal: | Belgian Journal of Operations Research, Statistics and Computer Science |
| Authors: | Giugnard M. |
| Keywords: | Lagrangean relaxation |
This paper presents the necessary background for understanding and designing efficient Lagrangean relaxations for integer programming problems. It suggests various ways in which Lagrangean relaxation can be applied and presents possible extensions. It reviews essential properties of the Lagrangean function, and describes several algorithms to solve Lagrangean duals. Lagrangean heuristics are an integral part of a Lagrangean approximation scheme, and may be ad-hoc or generic. A special effort has been made to give geometric interpretations whenever possible, and to illustrate the text with figures.