Efficient cuts in Lagrangean ‘relax-and-cut’ schemes

Lagrangean relaxation produces bounds on the optimal value of (mixed) integer programming problems. These bounds, together with integer feasible solution values, provide intervals bracketing the optimal value of the original problem. When the residual gap, i.e., the relative size of the interval, is too large for the approximations to be deemed satisfactory, it is desirable to ‘strengthen’ the Lagrangean bounds. One possible strengthening technique consists of identifying cuts which are violated by the current Langrangean solution, and dualizing them. Unfortunately not every valid inequality that is currently violated will improve the Lagrangean relaxation bound when dualized. This paper investigates what makes a violated cut ‘efficient’ in improving bounds. It also provides examples of efficient cuts for several (mixed) integer programming problems.