Search

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.

The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms. Among many findings, our study concludes that the preflow-push algorithms are substantially faster than other classes of algorithms, and the highest-label preflow-push algorithm is the fastest maximum flow algorithm for which the growth rate in the computational time is O ( n 1.5 ) on four out of five of our problem classes. Further, in contrast to the results of the worst-case analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes.

In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.

In the first part of the paper a general maximum flow procedure, which finds a maximum preflow and converts it into a maximum flow, is defined using a non-standard presentation of the maximum flow problem, which is viewed as a particular case of the maximum preflow one. This procedure enables several significant max-flow algorithms to be derived by instantiation, including the ones based on Goldberg's approach and the so-called ‘distance directed’ algorithms. Moreover, with this procedure a new max-flow algorithm can be defined, parametric with respect to the bound k on the lenght of the flow push paths. This procedure represents a generalization both of Goldberg's approach and of the ‘distance directed’ algorithm DD 1. In the second part, some interesting results from a wide computational experimentation on max-flow algorithms are presented.