Flow Optimization in Dynamic and Continuous Networks.
Abstract
The problem studied in this thesis is computing a minimum-delay time-varying routing assignment in a dynamic network where the node demands and link capacities are deterministic functions of time, and where the commodity being routed is represented by continuous variables. A single node is designated to be the destination, and a tau-maximum flow is defined to be a routing assignment which maximizes the amount of commodity reaching the destination before time tau. The key discovery used to solve the problem is that a routing assignment has minimum delay if and only if it is a tau-maximum flow for all tau. When the capacities are constant or piecewise-constant, this discovery and the well-known max-flow min-cut theorem are used to divide the problem into two smaller problems. The result is a polynomial algorithm which finds a minimum-delay routing assignment by solving a series of static maximum-flow problems. In order to apply the above ideas to dynamic networks with continuously varying capacities, a continuous network is defined whose flows and capacities are additive set functions, and a generalization of the max-flow min-cut theorem is proved. An even more general version of this theorem is proved for continuous network models whose capacities are submodular set functions. Various applications are considered, including the finite polymatroid networks of Lawler.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1985
- Accession Number
- ADA162493
Entities
People
- Richard G. Ogier
Organizations
- University of Illinois Urbana–Champaign