A Model and Method for Finding the Maximum Structured Flow in a Graph with Multiple Edge Weights

Abstract

This article presents a network model in the form of a graph, where the edge weights are subsets of integers that characterize the throughput and constrain the flows through the edges. A special type of flow should be formed between s and t nodes in this network. This flow is subject to additional requirements: each edge along the route from s to t should have an identical subset of adjacent ordered elements, the number of which determines the magnitude of the flow. We are interested in finding a subset of such flows that have no common elements and can be simultaneously implemented, with the sum of their magnitudes being maximal for a given network. The presented model and method based on integer linear programming can be used to analyze the throughput of graphs with multiple edge weights.