A relaxation/decomposition algorithm for the fixed charged network problem

This article makes use of relaxation in conjunction with decomposition for the solution of a fixed charge network problem. The solution technique exploits the underlying network structure. The solution approach is via the solution of a series of problem relaxation and bound adjustments. Upper bounds on the optimal objective value are obtained by use of a decomposition of the problem based on parametric changes in variable upper bounds. The Lagrangian dual provides a lower bound on the optimal objective as well as an initial allocation for the upper bounding procedure. The algorithm has been tested on 112 randomly generated problems with up to 1500 nodes, 6600 arcs, and 3000 fixed charge arcs. These test results demonstrate that even for relatively large problems, when certain convergence requirements are relaxed, the present algorithm can be very effective in generating near-optimal solutions. We obtain integer solutions that were, on the average, well within 2% of the optimum in approximately 1% of the time required by XMP to solve the continuous relaxation.