Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes

For nearly 30 years, Lagrangean relaxation has been extensively used in integer programming and combinatorial optimization. Today, it is one of the most used techniques for obtaining strong bounds, although it generally provides no linear programming relaxation. Our main objective in this paper is to show how to obtain linear programming relaxations with a value improving that of the Lagrangean dual problem. We first show how the recently introduced Fenchel cutting planes solve the convexified problem associated with every Lagrangean relaxation. Moreover we show that Fenchel cutting planes are much more effective than Lagrangean cutting planes and that they have very good computational properties for the 0-1 problems treated. (C) 2000 Elsevier Science B.V. All rights reserved.