Revised-Modified Penalties for Fixed Charge Transportation Problems
指出固定费用运输问题中常用的“改进罚则”存在缺陷，导致分支定界算法在近四分之一测试问题中无法找到最优解；通过简单修正恢复其有效性，且计算效率优于其他罚则。
Conditional penalties are used to obtain lower bounds to subproblems in a branch-and-bound procedure that can be tighter than the LP relaxation of the subproblems. For the fixed charge transportation problem (FCTP), branch-and-bound algorithms have been implemented using conditional penalties proposed by Driebeek (Driebeek, N. 1966. An algorithm for the solution of mixed integer programming problems. Management Sci. 12 576–587.), Cabot and Erenguc (Cabot, A. V., S. S. Erenguc. 1984. Some branch-and-bound procedures for fixed-cost transportation problems. Naval Res. Logistics 31 145–154.), and Palekar et al. (Palekar, V. S., M. H. Karwan, S. Zionts. 1990. A branch-and-bound method for the fixed charge transportation problem. Management Sci. 36 1092–1105.). The last conditional penalties are referred to as the “modified” penalties. In this paper, we show that the modified penalties are not valid conditional penalties. In fact, in nearly a quarter of the test problems examined, the modified penalties prevented the branch-and-bound algorithm from properly identifying the optimal solution to the FCTP. A simple change, which corrects a subcase in the penalty calculation, restores the validity of the modified penalties while retaining their efficiency. Computational tests indicate that the “revised-modified” penalties continue to dominate the Driebeek and the Cabot and Erenguc penalties.