A set covering reformulation of the pure fixed charge transportation problem

A set covering reformulation of the pure fixed charge transportation problem

0.00 Avg rating0 Votes
Article ID: iaor1995632
Country: Netherlands
Volume: 48
Issue: 3
Start Page Number: 245
End Page Number: 259
Publication Date: Feb 1994
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: networks: flow
Abstract:

The pure fixed charge transportation problem is reformulated into an equivalent set covering problem with, in general, a large number of constraints. Two constraint generation procedures for its solution are suggested; in both of these, new constraints are generated by the solution of ordinary maximum flow problems. In the first procedure, which is an optimizing Benders-type scheme, each set covering problem is solved by a simple heuristic. Upper and lower bounds to the optimal value of the transportation problem are provided throughout the procedure so that it can be terminated at •-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 fixed multiplier values. These are chosen so that the optimal solution of an initial Lagrangean subproblem, being a minimum cost network flow problem, remains optimal. At termination, the heuristic provides a lower bound and a feasible solution to the transportation problem. Moreover, the computational cost of this procedure is very low; hence it is well 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.

Reviews

Required fields are marked *. Your email address will not be published.