(A) new subgradient algorithm for multicommodity minimal cast network flow problems

Abstract

This thesis presents a new subgradient algorithm for the multicommodity network flow problems. The primal resource-directive procedure suggested by Kennington and Shalabey is refined. Adopting a circular formulation and using the concept of artificial arc, an primal-dual algorithm with which reoptimization is easy is used for solving the subproblems. For improving the lower bound of the objective value, a Largrangean dual procedure is developed. The new algorithm which is a hybrid of the primal and the dual procedure is coded with PASCAL, and some computational experiments are performed.