Maximum-throughput dynamic network flows

This paper presents and solves the maximum throughput dynamic network flow problem, an infinite horizon integer programming problem which involves network flows evolving over time. The model is a finite network in which the flow on each arc not only has an associated upper and lower bound but also an associated transit time. Flow is to be sent through the network in each period so as to satisfy the upper and lower bounds and conservation of flow at each node from some fixed period on. The objective is to maximize the throughput, the net flow circulating in the network in a given period, and this throughput is shown to be the same in each period. We demonstrate that among those flows with maximum throughput there is a flow which repeats every period. Moreover, a duality result shows the maximum throughput equals the minimum capacity of an appropriately defined cut. A special case of the maximum dynamic network flow problem is the problem of minimizing the number of vehicles to meet a fixed periodic schedule. Moreover, the elegantsolution derived by Ford and Fulkerson for the finite horizon maximum dynamic flow problem may be viewed as a special case of the infinite horizon maximum dynamic flow problem and the optimality of solutions which repeat every period.     

On solving continuous-time dynamic network flows

Temporal dynamics is a crucial feature of network flow problems occurring in many practical applications. Important characteristics of real-world networks such as arc capacities, transit times, transit and storage costs, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows. While time is a continuous entity by nature, discrete-time models are often used for modeling dynamic network flows as the resulting problems are in general much easier to handle computationally. In this paper, we study a general class of dynamic network flow problems in the continuous-time model, where the input functions are assumed to be piecewise linear or piecewise constant. We give two discrete approximations of the problem by dividing the considered time range into intervals where all parameters are constant or linear. We then present two algorithms that compute, or at least converge to optimum solutions. Finally, we give an empirical analysis of the performance of both algorithms.     

Maximum flow problem on dynamic generative network flows with time-varying bounds

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.     

A note onK best network flows

It is shown that the problem of finding theK best solutions of a linear integer network flow problem can be solved by a polynomial time algorithm. This algorithm can be used in order to solve a multiple-criteria network flow problem which minimizes the maximum ofQ objectives.Partially supported by grants of the Deutsche Forschungsgemeinschaft and the HC&M programme of the European Union under ERBCHRXCT 930087.     

Simultaneous evacuation and entrance planning in complex building based on dynamic network flows

This paper presents mathematical models and a heuristic algorithm that address a simultaneous evacuation and entrance planning. For the simultaneous evacuation and entrance planning, four types of mathematical models based on the discrete time dynamic network flow model are developed to provide the optimal routes for evacuees and responders within a critical timeframe. The optimal routes obtained by the mathematical models can minimize the densification of evacuees and responders into specific areas. However, the mathematical model has a weakness in terms of long computation time for the large-size problem. To overcome the limitation, we developed a heuristic algorithm. We also analyzed the characteristics of each model and the heuristic algorithm by conducting case studies. This study pioneers area related to evacuation planning by developing and analyzing four types of mathematical models and a heuristic algorithm which take into account simultaneous evacuation and entrance planning.     

A survey of static and dynamic potential games

Potential games are noncooperative games for which there exist auxiliary functions, called potentials, such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.     

Multiterminal network flows and applications

The paper discusses the ways to use the condensation technique of Gomory/Hu in the case of non-symmetric networks. Sufficient conditions to get the value of a maximal flow as row resp. column sum of the capacity matrix are derived. Procedures to determine the cut with minimal capacity are developed and applications of the minimal cut technique to problems of optimal sequencing are given.

---

Zusammenfassung Das Papier diskutiert die Möglichkeiten, die Kondensationstechnik von Gomory/Hu auf den Fall unsymmetrischer Netzwerke zu übertragen. Es werden hinreichende Bedingungen dafür abgeleitet, daß der Wert eines maximalen Flusses mit der Zeilenbzw. Spaltensumme der Kapazitätsmatrix übereinstimmt. Es werden Verfahren entwickelt, den Schnitt minimaler Kapazität zu bestimmen. Anwendungen der minimalen Schnitt-Technik auf Probleme der optimalen Reihenfolge werden vorgestellt.

     

Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning

In this paper we combine two modeling tools to predict and evaluate evacuation plans: (dynamic) network flows and locational analysis. We present three exact algorithms to solve the single facility version 1-FlowLoc of this problem and compare their running times. After proving the $\mathcal{NP}$ -completeness of the multi facility q-FlowLoc problem, a mixed integer programming formulation and a heuristic for q-FlowLoc are proposed. The paper is concluded by discussing some generalizations of the FlowLoc problem, such as the multi-terminal problem, interdiction problem, the parametric problem and the generalization of the FlowLoc problem to matroids.     

Maximal dynamic polymatroid flows and applications

The concept of dynamic polymatroid flows is introduced. It is shown that the time expanded network algorithm which is well known for dynamic network flows works for polymatroid flows as well. As applications we discuss dynamic matroid intersection and dynamic matroid partitionings.     

Maximum network flows with concave gains

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs. Supported by a Grant-in-Aid for Scientific Research (No. 13780351 and No.14380188) from The Ministry of Education, Culture, Sports, Science and Technology of Japan.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

New algorithms for generalized network flows

This paper, of which a preliminary version appeared in ISTCS'92, is concerned with generalized network flow problems. In a generalized network, each edgee = (u, v) has a positive flow multipliera _e associated with it. The interpretation is that if a flow ofx _e enters the edge at nodeu, then a flow ofa _e x _e exits the edge atv. The uncapacitated generalized transshipment problem (UGT) is defined on a generalized network where demands and supplies (real numbers) are associated with the vertices and costs (real numbers) are associated with the edges. The goal is to find a flow such that the excess or deficit at each vertex equals the desired value of the supply or demand, and the sum over the edges of the product of the cost and the flow is minimized. Adler and Cosares [Operations Research 39 (1991) 955–960] reduced the restricted uncapacitated generalized transshipment problem, where only demand nodes are present, to a system of linear inequalities with two variables per inequality. The algorithms presented by the authors in [SIAM Journal on Computing, to appear result in a faster algorithm for restricted UGT.Generalized circulation is defined on a generalized network with demands at the nodes and capacity constraints on the edges (i.e., upper bounds on the amount of flow). The goal is to find a flow such that the excesses at the nodes are proportional to the demands and maximized. We present a new algorithm that solves the capacitated generalized flow problem by iteratively solving instances of UGT. The algorithm can be used to find an optimal flow or an approximation thereof. When used to find a constant factor approximation, the algorithm is not only more efficient than previous algorithms but also strongly polynomial. It is believed to be the first strongly polynomial approximation algorithm for generalized circulation. The existence of such an approximation algorithm is interesting since it is not known whether the exact problem has a strongly polynomial algorithm.Corresponding author. Research was done while the first author was attending Stanford University and IBM Almaden Research Center. Research partially supported by ONR-N00014-91-C-0026 and by NSF PYI Grant CCR-8858097, matching funds from AT&T and DEC.Research partially supported by ONR-N00014-91-C-0026.     

Heavy-traffic limits for stationary network flows

This paper studies stationary customer flows in an open queueing network. The flows are the processes counting customers flowing from one queue to another or out of the network. We establish the existence of unique stationary flows in generalized Jackson networks and convergence to the stationary flows as time increases. We establish heavy-traffic limits for the stationary flows, allowing an arbitrary subset of the queues to be critically loaded. The heavy-traffic limit with a single bottleneck queue is especially tractable because it yields limit processes involving one-dimensional reflected Brownian motion. That limit plays an important role in our new nonparametric decomposition approximation of the steady-state performance using indices of dispersion and robust optimization.

     

A dynamic logistic regression for network link prediction

In social network analysis, link prediction is a problem of fundamental importance. How to conduct a comprehensive and principled link prediction, by taking various network structure information into consideration, is of great interest. To this end, we propose here a dynamic logistic regression method. Specifically, we assume that one has observed a time series of network structure. Then the proposed model dynamically predicts future links by studying the network structure in the past. To estimate the model, we find that the standard maximum likelihood estimation (MLE) is computationally forbidden. To solve the problem, we introduce a novel conditional maximum likelihood estimation (CMLE) method, which is computationally feasible for large-scale networks. We demonstrate the performance of the proposed method by extensive numerical studies.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

A quadratic network optimization model for equilibrium single commodity trade flows

When supply and demand curves for a single commodity are approximately linear in each ofN regions and interregional transportation costs are linear, then equilibrium trade flows can be computed by solving a quadratic program of special structure. An equilibrium trade flow exists in which the routes carrying positive flow form a forest, and this solution can be efficiently computed by a tree growing algorithm.     

Solving a combinatorial problem with network flows

In this paper we present an algorithm based on network flow techniques which provides a solution for a combinatorial problem. Then, in order to provide all the solutions of this problem, we make use of an algorithm that given the bipartite graphG=(V ₁ ∪V ₂,E, w) outputs the enumeration of all bipartite matchings of given cardinalityv and costc.     

Two commodity network flows and linear programming

This paper shows that the linear programming formulation of the two-commodity network flow problem leads to a direct derivation of the known results concerning this problem. An algorithm for solving the problem is given which essentially consists of two applications of the Ford—Fulkerson max flow computation. Moreover, the algorithm provides constructive proofs for the results. Some new facts concerning feasible integer flows are also given.     

A survey of the perturbation analysis of discrete event dynamic systems

This paper introduces an analysis and optimization technique for discrete event dynamic systems, such as flexible manufacturing systems (FMSs), and other discrete part production processes. It can also be used for enhancement of the simulation results of, or the monitoring of the operations of such systems in real time. Extensive references are given where readers may pursue futher details.