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.