Improved Penalties for Fixed Cost Linear Programs Using Lagrangean Relaxation
A. Victor Cabot, S. Selcuk Erenguc
Management Science · 1986 · Volume 32 · Issue 7
Abstract
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.
Keywords
programming: integer algorithms, branch and bound
Enable JavaScript for citation tools and additional paper interactions.