Network Flows
Abstract
Perhaps no subfield of mathematical programming is more alluring than network optimization. Highway, rail, electrical, communication and many other physical networks pervade our everyday lives. As a consequence, even non-specialists recognize the practical importance and the wide ranging applicability of networks. Moreover, because the physical operating characteristics of networks (e.g., flows on arcs and mass balance at nodes) have natural mathematical representations, practitioners and non-specialists can readily understand the mathematical descriptions of network optimization problems and the basic nature of techniques used to solve these problems. This combination of widespread applicability and ease of assimilation has undoubtedly been instrumental in the evolution of network planning models as one of the most widely used modeling techniques in all of operations research and applied mathematics. The aim of this paper is to summarize many of the fundamental ideas of network optimization. In particular, we concentrate on network flow problems and highlight a number of recent theoretical and algorithmic advances. We have divided the discussion into the following broad major topics: (1) Applications; (2) Basic Properties of Network Flows; (3) Shortest Path Problems; (4) Maximum Flow Problems; (5) Minimum Cost Flow Problems; and (6) Assignment Problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1988
- Accession Number
- ADA594171
Entities
People
- James B. Orlin
- Ravindra K. Ahuja
- Thomas L. Magnanti