Dual algorithms for network flow problems with set-constarints = 집합적 제약이 있는 네트워크 흐름 문제의 쌍대해법에 관한 연구

The set-constrained network flow problem differs from the ordinary network flow problem in the flow bound constraints. In the polymatroidal network flow problem(PN), the set-constraints are imposed on subsets of arcs incident to a node, while in the submodular flow problem(SF), imposed on subsets of nodes. The major concern of this thesis is on the development of dual algorithms for PN and SF, respectively. The potential applicability of the set-constrained network flow model is demonstrated through a scheduling problem arising in a parallel processor system. Based on Martel``s model of PN for obtaining a feasible schedule, the job requirements are allocated to each processor in a fair manner so that the processor may have more equitable workloads. We develop an algorithm for the weighted PN (WPN) where the arc weight is taken into consideration. Presented is a version of the greedy algorithm which, rooted in the weight splitting technique, solves an equivalent weighted polymatroid intersection problem(WPI). The problem structure is exploited to detect unnecessary cases of weight splitting. Finally, developed is an algorithm for SF which monotonically increases the dual objective function value. There are two key constructs of our algorithm, the one of finding ``improving set`` which imply ascent directions and the other of adjusting dual values of the selected set. Improving sets are confined to only three types, and dual values are adjusted through the procedure ASCENT. At each iteration, the algorithm proceeds to the satisfaction of the complementary slackness conditions, and then to locate the ``best improving set``. The procedure TREESEARCH is activated for the best improving set and, if it fails to find such an improving set, an optimal flow is determined via complementary slackness. An illustrative example is presented.
Tcha, Dong-Wanresearcher차동완researcher
Issue Date
61788/325007 / 000775141

학위논문(박사) - 한국과학기술원 : 경영과학과, 1991.2, [ iv, 94 p. ]

Appears in Collection
Files in This Item
There are no files associated with this item.
  • Hit : 57
  • Download : 0
  • Cited 0 times in thomson ci


  • mendeley


rss_1.0 rss_2.0 atom_1.0