Network flows and monotropic optimization. (English) Zbl 0596.90055

Rockafellar, R. T.

Pure and Applied Mathematics. A Wiley-Interscience Publication. New York etc.: John Wiley & Sons. XIII, 616 p. (1984).

This book develops the theory of the mathematical problems related to the optimization of flows and potentials in networks. The term ”monotropic” which was created by the author, is introduced here for the first time. It encompasses all problems where a preseparable convex function is minimized subject to linear constraints. (A convex function is called preseparable if it is the sum of liner functions composed with convex functions of a single variable, as is any quadratic convex function, for instance.) Monotropic programming problems enjoy a complete and symmetric duality theory, almost as constructively useful as the one for linear programming problems. Using the new framework, the author explains the connection between combinatorial structures such as paths and cuts in a network, and matroidal structures associated with pivoting algorithms. No prior knowledge of networks, graph theory, or linear programming is required.
The first nine chapters deal with networks (1. Networks, 2. Paths and cuts, 3. Flows and capacities, 4. Analysis of flows, 5. Matching theory and assignment problems, 6. Potentials and spans, 7. networks with linear costs, 8. Optimal flows and potentials, 9. Algorithms for convex costs) whereas the last two (10. Linear systems of variables, 11. Monotropic programming) deal exclusively with monotropic programming. But as the author writes ”this division of space is more apparent than real. The network chapters gradually build up the concepts to where the transition to the broader domain is very well motivated and ripe with analogies”.
The blend of very readable introductory text (with numerous figures, examples and exercises) and the new findings - at the frontiers of research - makes this book extremely useful for both beginners and professionals who already possess a strong background in the field.

Reviewer: L.E.Faibusovich

MSC:

90C35	Programming involving graphs or networks
49M37	Numerical methods based on nonlinear programming
90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C30	Nonlinear programming
05C35	Extremal problems in graph theory
90B10	Deterministic network models in operations research

Keywords:

monotropic optimization; optimization of flows and potentials in networks; preseparable convex function; linear constraints; combinatorial structures; paths and cuts; matroidal structures; pivoting algorithms