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, Cabot and Erenguc, and Palekar et al. 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.