A New Branch-and-Bound Algorithm for the Fixed-Charge Transportation Problem

A new branch-and-bound procedure specialized for the fixed-charge transportation problem has been developed. The technique strongly exploits the underlying transportation structure. The relaxed problem assumes this form and simple penalties are easily constructed from the optimal solution of this transportation problem. These penalties are used in the standard branch-and-bound tasks of fathoming and guiding separation. The procedure has been coded, and over sixty test problems have been solved.