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.
네트워크 흐름문제에서 흐름을 제약하는 통상적인 조건은, 각 호선(arc) 의 용량과 각 마디(node)에서의 흐름보존 규칙이다. 이러한 조건들을 더욱 포괄적인 형태로 일반화할때, Polymatroidal 네트워크 흐름 문제 (PN)와 Submodular 네트워크 흐름 문제(SF)를 생각하게 된다. 전자는 각 마디에 인접한 호선들의 부분집합에 용량제약이 추가된 문제이고, 후자는 흐름보존 규칙대신 마디들의 부분집합에 흘러오는 순유입량이 제약되는 문제이다. 이 논문에서는 PN과 SF에 대한 각각의 새로운 쌍대 해법을 제시하고자 한다.
그에 앞서, PN과 SF의 유용성을 보이기 위해, 병행 기계 시스템에서의 스케쥴링 문제를 다룬다. 각 작업의 도착시간과 처리시한이 미리 정해져 있을때, Martel이 제시한 PN 모형은 가능한 스케쥴을 정해준다. 이 결과를 이용하여 가능한 스케쥴을 얻은 후, 이것을 각 기계에서의 작업량이 보다 평준화된 것으로 개선시킬 수 있다.
이제, 각 호선에 가중치가 부여된, PN의 보다 일반적인 문제 (WPN)에서, 이 가중치의 총합이 최대화되도록 최적 흐름량을 정한다. 이것을 해결하는 하나의 방법으로, Polymatroid에 적용되는 greedy 해법과 가중치 분할 기법을 활용한다. 먼저, WPN을 WPI (Weighted Polymatroid Intersection Problem)로 변환한 후, 체계적으로 가중치를 분할해 가면서, greedy 해법에 따라 후보해를 산출한다. 이러한 과정은 가중치의 분할 과정에 맞추어 많은 후보해를 조사해야하는 단점이 있으나, 후보해의 산출이 간편한 점이 이 단점을 보완하고 있다. 더우기, WPI의 특수한 구조를 활용하여 불필요한 가중치 분할을 미리 피할 수 있는 방법이 고안됨으로써, 이 해법의 효율을 높일 수 있게 된다. 하나의 예제가 이 효과를 보인다.
마지막으로, SF에 대한 쌍대 해법이 제시된다. 이 해법은 먼저 SF의 쌍대 목적함수 값을 단조 증가시켜 최적 쌍대해를 구한 후, 상보 여유 정리를 활용하여 최적 흐름량을 정하는 방법이다. 최적의 쌍대해를 구하기 위해서는, 상승 방향(ascent direction)을 지시해주는 마디들의 부분집합, 즉 개선 집합(improving set)을 찾고, 이 집합에 관련된 쌍대해를 조절한다. 이러한 개선 집합을 효과적으로 찾기 위해, 먼저 두 가지 형태의 부분 집합만을 조사한다. 또한, 쌍대해의 조절을 위해서는 ASCENT 절차를 고안한다. 이 절차들을 반복적으로 시행하여 상보 여유 정리가 만족되도록 하고, 그 후에는 TREESEARCH 절차를 가동시켜 최선 개선 집합을 찾는다. TREESEARCH에 의해서도 아무런 개선 집합이 발견되지 않을때는 쌍대 최적해에 도달하게 된다. 하나의 예제를 풀어가며 이 모든 절차의 설명을 돕고 있다.
