Revised-Modified Penalties for Fixed Charge Transportation Problems

Bruce W. Lamar and Chris A. Wallace
Additional contact information
Bruce W. Lamar: MITRE Corporation, Bedford, Massachusetts 01730
Chris A. Wallace: University of Auckland, Auckland, New Zealand

Management Science, 1997, vol. 43, issue 10, 1431-1436

Abstract: 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.

Keywords: branch-and-bound; conditional penalties; fixed charge transportation problem; mixed integer programming; up and down penalties (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.43.10.1431 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:43:y:1997:i:10:p:1431-1436

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().