|
Capacity Improvement, Penalties, and the Fixed Charge Transportation Problem
1999 Award Winner
Bruce W. Lamar, The MITRE Corporation
Gavin J. Bell, University of Canterbury, Christchurch, New Zealand
Chris A. Wallace, University of Auckland, Auckland, New Zealand
ABSTRACT
Capacity improvement and conditional penalties are two computational aides for fathoming subproblems in a branch-and-bound procedure. In this paper, we apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave minimization problems (rather than LP relaxations). Using the concave relaxations, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments using a standard set of FCTP test problems, the new capacity improvement and penalty techniques are responsible for a three-fold reduction in the CPU time for the branch-and-bound algorithm and nearly a tenfold reduction in the number of subproblems that need to be evaluated in the branch-and-bound enumeration tree.
Publication
Published in 1999 ©John Wiley & Sons, Inc. Naval Research Logistics, Vol. 46, pp. 341-355.
Additional Search Keywords
n/a
|
