ON OPTIMAL PATTERN FLOWS

概要

論文の詳細を見る
In this paper, we shall present some algorithms for finding the optimum solution of flow problems, in which several constraints of non-network flow type are imposed on special arc flows. For example, the flow on a certain arc must be divided into flows on the succeeding arcs in proportion to a given ratio. These constraints may be linear, nonlinear, or combinatorial. We call them pattern constraints, because in many cases they are associated with certain patterns of flows on special arcs. Also, we call such flows pattern flows. To find a maximal pattern flow and a minimal cost pattern flow and to show an extension of the Critical Path Method are main objects of this paper. In general, we can not solve them by usual network flow algorithms. They are concerned both with network flow problems and with more general mathematical programing problems. In this connection, we shall use Benders' decomposition to find optimal pattern flows. The computational complexity of our algorithms depends mainly on the complexity of algorithms for solving subproblem related to pattern constraints and that of network flow algorithms.
社団法人日本オペレーションズ・リサーチ学会の論文