Capacity improvement, penalties, and the fixed charge transportation problem

Capacity improvement and conditional penalties are two computational aides for fathoming subproblems in a branch-and-bound procedure. In this paper, w e apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave mi nimization problems (rather than LP relaxations). Using the concave relaxat ions, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments usi ng a standard set of FCTP test problems, the new capacity improvement and p enalty techniques are responsible for a three-fold reduction in the CPU tim e 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 enu meration tree. (C) 1999 John Wiley & Sons, Inc.