Dual algorithms for network flow problems with set-constarints

Abstract

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.