A LAGRANGEAN RELAXATION APPROACH TO THE GENERALIZED FIXED CHARGE MULTICOMMODITY MINIMAL COST NETWORK FLOW PROBLEM

This research is concerned with the development of Lagrangean relaxation techniques which may be incorporated in branch-and-bound schemes for the solution of the generalized fixed charge multicommodity minimal cost network flow problems. It is shown that for candidate subproblems derived during the branching process, the optimal objective value for the partial convex hull relaxation lies between the optimal objective values for the continuous relaxation and mixed integer subproblem itself. Further, it is shown that for these subproblems the optimal objective value for the partial convex hull relaxation is identical with the optimal objective value obtained by maximizing the optimal objective value of its Lagrangean relaxation over all admissable multipliers. A simple greedy algorithm is presented for obtaining the solution to any Lagrangean relaxation of a candidate subproblem with fixed multipliers.;A survey of efficient computational devices for general linear programming is included. The techniques presented make many of the approaches to the solution of the continuous relaxation of the candidate subproblems which rely heavily on standard simplex operations more computationally attractive. Most of the material presented deals with the factorizations of the basis inverse and reinversion techniques.;A discussion of subgradient optimization techniques and a development of some associated convergence results is given. Two applications of this technique are discussed: its use in solving the continuous relaxation of candidate subproblems by resource-directive decomposition, and its use in maximizing the Lagrangean relaxation of candidate subproblems over admissable multipliers. Also included is a discussion of projection techniques in Euclidean space, which are a vital part of the subgradient procedures.;A computational study is provided showing the effectiveness of the Lagrangean relaxation techniques when incorporated in a branch-and-bound procedure for solution of a practical problem. This problem is derived from the United States Air Force air freight network, LOGAIR.;Also presented is a survey and nearly self-contained development of the primal methods which can be used to solve the continuous relaxation subproblems by bringing to bear the powerful primal solution techniques developed for minimum cost single-commodity network flow problems. A complete development of the single-commodity techniques and a discussion of their implementation technology is also included.