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.