Improved Penalties for Fixed Cost Linear Programs Using Lagrangean Relaxation

The most commonly used penalty in branch and bound approaches to integer programming is the Driebeek--Tomlin penalty. It has been used successfully in solving fixed cost linear programs by Kennington and Unger and by Barr, Glover and Klingman. It is well known that the Driebeek--Tomlin penalty can be derived from a Lagrangean relaxation of the integer programming problem. We show, however, that the Lagrangean relaxation for fixed cost problems not only yields the Driebeek--Tomlin penalty, but two penalties which sometimes dominate it. We show the strength of the new penalties by solving a series of text problems and comparing the number of nodes generated on the branch and bound tree and the total computer time needed to solve each problem.