Network Flows and Monotropic Optimization

Preface:

This book is aimed at the kinds of optimization problems in which duality is as important a tool in computation as it is in theory and interpretation. These problems are characterized by a very rich interplay between combinatorial structure and convexity properties. They fill the spectrum between integer programming on one hand, and general convex programming on the other. Network programming, linear programming, and a broader subject that we call monotropic programming all are included.

Problems concerning flows and potentials in networks start us out at one end of the spectrum. The study of such problems abounds in results of combinatorial nature about paths, cuts, trees, and other objects, and such results are essential to the design of almost every algorithm. General linear programming problems also exhibit a combinatorial substructure. This is sometimes regarded as centering on the geometry of convex polyhedra, but tableau representations of linear systems of variables are an even more important part. A whole school of thought has grown up around the possible or desirable patterns of signs among the coefficients in such tableaus and the techniques for achieving them by a sequence of pivoting transformations.

In both network programming and linear programming, conditions for feasibility or optimality typically concern the relationships between a primal problem and a dual problem, and these relationships have a deep practical significance. One is not so much involved with constraint functions and their associated Lagrange multipliers, which are the prime focus in convex and nonconvex programming more generally, as one is with pairs of primal and dual variables whose values must fall into a certain pattern with respect to each other. Such a pattern can be anything from a complementary slackness condition to Ohm's law.

What we have attempted to do in this book is to take these common ideas, develop them in such a way as to illuminate the strong connections between linear and network programming and thereby enhance both subjects, and finally use this as a springboard in treating a much larger class of problems where the ideas find their full realization. The larger class encompasses all problems where a preseparable convex function is minimized subject to linear constraints. (A convex function is preseparable if it is the sum of linear functions composed with convex functions of a single variable, as is any quadratic convex function, for instance.) These we call monotropic programming problems, because of the characteristic relationships they require between primal and dual variables; "monotropic" means "changing in one direction only" and is a term which we propose as pertaining to the monotonicity properties of convex functions of a single variable.

Monotropic programming problems enjoy a remarkably complete and symmetric duality theory, almost every bit as constructively useful as the one for linear programming problems. But they also have inherent combinatorial properties. The latter are related to the possible tableau representations for the underlying linear systems of variables. On an abstract level these properties are the substance of the theory of oriented real matroids. They lead to a development of pivoting algorithms of such a form that specialization to combinatorial subroutines, like the generation of appropriate paths or cuts in the network case instead of the algebraic manipulation of coefficient matrices, is readily accomplished.

In line with our overall purpose, we emphasize the aspects of network programming that lend themselves to generalization and, at the other end of the spectrum, forego discussion of topics that do not reside in the special nature of monotropic programming. Thus we omit combinatorial results about networks, even ones involving duality, if they are not ultimately tied in with network flows or useful for later purposes of analogy. On the other hand, we ignore computational methods of general convex programming that might in particular be applied in monotropic programming, and we never even come to the definition of the conjugate of a convex function of several variables, despite the fact that such functions in the case of a single variable form the foundation for our theory of duality.

Nevertheless, in order to flesh out the book as an introduction and make it more widely useful, we include many examples and details that would not be truly essential. We also provide an extensive list of exercises. The exercises serve a double purpose. They should be useful to anyone trying to learn the subject, but they also act as a repository for numerous results and observations that ought to be recorded somewhere and yet do not belong in the chapters proper, because they would take too much space, obscure the main points, or break the continuity. These exercises, in case where they contain facts that are important enough to be cited at various places in the text, are supplied with extensive hints that amount to an outline of proof.

Each chapter begins with some remarks intended to orient the reader and ends with a section of supplementary notes and references to the literature.

A few words should be said about our treatment of algorithms. Although we try to indicate the various modes in which a procedure can be implemented, and to suggest advantages or disadvantages associated with different options, we hold back from stating algorithms in immediately programmable form, and we spend little time in discussing computational complexity. Some readers may feel this to be a serious lack; the emphasis on computers nowadays is all-pervasive. Our approach is partly just a matter of personal inclination, but there are some sound reasons behind it too.

Our objective is to forge theoretical links between problems and procedures that at first might seem quite different. We want to use these links to enrich, by way of analogy, the possible approaches that can be used in a given case, as well as to identify seemingly different approaches as being essentially the same. This requires us to view each algorithm first in its most basic form and only then consider how it might be elaborated with tricks and numerical shortcuts.

We hoe that readers will recognize the long-run value of this conceptual method, as a complement t other ways of proceeding, and not be disappointed that we have not simply presented a "best" way of carrying out each computational task. In fact for much of what we discuss, there is no one "best" algorithm, nor is there yet a theory of computational complexity that is capable of making meaningful comparisons. Even for the entirely combinatorial subroutines in network programming, since we are interested in them mainly as components in other procedures, we cannot pass judgment on them in isolation. We must take into account various features of their structure and behavior that might seem irrelevant to the narrow purpose at hand.

In truth, many of the codes procedures now available, such as shortest path algorithms, schemes for executing pivoting transformations and the like, do not seem well adapted to the intrinsic needs of our larger subject. rather than trying to squeeze the subject into a preconceived mold, it makes more sense to develop it along its own natural lines. One can hope that this will provide stimulus for further work on the algorithms in question.

Besides the development of a general framework for a branch of optimization theory that has not hitherto been treated as a unit, this book offers some more specific contributions. In network programming it brings out the full role of potentials in duality with that of flows. This has long been perceived in electrical theory, but the ideas have not yet found their way to the hearts of economists and mathematical programmers. The book also contains the first comprehensive treatment of network programming problems with nonlinear costs. It presents the theory of conjugate convex functions of a single variable in a constructive manner with numerous examples and demonstrates its applications. This may help to popularize ideas that could be put to use much more widely than they have been.

In the area of monotropic programming, the text expounds duality results that have not previously been available in book form. It puts matroidal concepts in a form that is appropriate for tracing their role and that of duality in the design of algorithms. Among the by-products of this are extensions of the simplex method of linear programming and the out-of-kilter algorithm of network programming to general piecewise linear programming and beyond.

Although the first nine chapters deal with networks and only the last two exclusively with monotropic programming, 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. Many of the proofs then carry over with little change. However, readers interested mainly in finding out about monotropic programming should be able to dive right into Chapter 10 and refer back to earlier material only as needed.

For readers who wish to approach the whole subject but would appreciate some guidance and shortcuts, we have designated with an asterisk * those sections that can most easily be skipped over on the first round.

Any book of this length is a long time in the making, if not in the writing, and in the present case it has been both. Many of the ideas have fascinated the author since the early 1960s but have not previously been put into print. Lecture notes on network programming from a course given at the University of Grenoble in 1973-74 formed the written nucleus out of which the book finally grew. The main job of writing extended from May 1976 to July 1979, with gaps, of course, for other activities. A final effort in the summer of 1982 went into updating the references and expanding the material on monotropic programming in the last two chapters in order to make it more accessible and self-contained.

During all that time there were many students and colleagues who helped by going through portions of the text and providing criticisms. Most notable among these was Jonathan Spingarn, who spent months at the task. The faithful and conscientious typist almost from the beginning has been Patricia Monohon, and it was she also who in fine style executed all the figures. The Air Force Office of Scientific Research, through the guidance of Dr. Joseph Bram, provided under grants AF-AFOSR-77-3204 and F4960-82-K-0012 many months of salary support without which this enormous project could never have come to fruition. The Air Force Office of Scientific Research and the University of Washington are to be commended for fostering the kind of circumstances in which such a long-term effort can be made.

Seattle, Washington, April 1984