A SET COVERING REFORMULATION OF THE PURE FIXED CHARGE TRANSPORTATION PROBLEM

The pure fixed charge transportation problem is reformulated into an e quivalent set covering problem with, in general, a large number of con straints. Two constraint generation procedures for its solution are su ggested; in both of these, new constraints are generated by the soluti on of ordinary maximum flow problems. In the first procedure, which is an optimizing Benders-type scheme, each set covering problem is solve d by a simple heuristic. Upper and lower bounds to the optimal value o f the transportation problem are provided throughout the procedure so that it can be terminated at epsilon-optimality. The second procedure, which is a heuristic, is based on the restricted Lagrangean concept. In this case the generated constraints are Lagrangean relaxed with fix ed multiplier values. These are chosen so that the optimal solution of an initial Lagrangean subproblem, being a minimum cost network flow p roblem, remains optimal. At termination, the heuristic provides a lowe r bound and a feasible solution to the transportation problem. Moreove r, the computational cost of this procedure is very low; hence it is w ell suited for incorporating in a branch and bound scheme. A possible branching technique is given. Computational results are presented for both the Benders-type and the branch and bound schemes.