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.

• 저널Management Science · 43(10) · 1431–1436
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.43.10.1431
• 저자Bruce W. Lamar, Chris A. Wallace