Improved Penalties for Fixed Cost Linear Programs Using Lagrangean Relaxation
从拉格朗日松弛角度推导出两种新的罚函数，在固定成本线性规划的分支定界求解中，比常用的Driebeek-Tomlin罚函数更有效，能减少搜索节点数和计算时间。
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.