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.
본 논문은 다품목 네트웍 흐름 비용 최소화 문제( MMCNF : Multicommodity Minimal Cost Network Flow problem) 의 새로운 해법에 관한 연구이다. 본 연구의 contribution은 다음과 같다.
1. Kennington 과 Shalabey는 MMCNF 문제에 적용된 Resource-Direvtive Decomposition의 주문제를 풀기 위한 subgradient algorithm을 제시 하였는데, 본 연구에서는 이 문제에 대한 circular formulation의 적용과 artificial arc의 개념을 이용하여 subproblem의 해법으로 Primal-Dual algorithm이 쓰일 수 있게 하였다.
2. 대부분의 계산이 부문제인 single commodity problem 을 푸는 과정에서 이루어 진다. Bertekas 가 최근에 제시한 Framework 에 기초하여 부문제를 풀기위해 reoptimization 이 쉬운 Primal-Dual algorithm 을 개발하였다.
3. 보다 나은 lower bound를 얻기 위해, Lagrangean Dual procedure가 개발되었다. 최적 목적함수값에 가까운 lower bound 는 algorithm의 실제적인 이용을 위해 필수적이다.
primal procedure 와 dual procedure 를 결합함으로써, Subgrdient method의 장점인 비교적 적은 memory requirement와 계산 속도면에서의 효율성을 갖는 algorithm 을 개발하였다.
