The use of surrogate and Lagrangean relaxations in integer programming problems

Relaxations of an integer programming problem produce bounds on its optimal solution. The linear programming, Lagrangean, surrogate and combined Lagrangean–surrogate (L–S) relaxations are the most commonly used in the solution of an integer programming problem. We present a brief review of these relaxations, solution methods for the respective duals and theoretical relationships that exist among them. We give special emphasis to surrogate and combined L–S relaxations.