Linear programming and network models

Linear programming and network models

Book Those interested in designing software for general network optimization problems will find in the paper of Grigoriades on “An efficient implemen...

203KB Sizes 0 Downloads 27 Views


Those interested in designing software for general network optimization problems will find in the paper of Grigoriades on “An efficient implementation of the network simplex method”, a detailed and excellent guideline for such purposes. TO end this list of examples limiting it to only the full papers (and within them to those most appealing to the reviewer) I will include two important topics in the network optimization field: network design and transportation analysis. Network design problems from the Benders decomposition approach is the subject of a full joint paper by Magna& Mireault and Wong, that complements earlier works of the same authors on that subject. Nonlinear cost network models in transportation analysis is the title of a wide and suggestive paper by M. Florian that also extends and complements earlier papers offering possibilities for future research work and a sound basis for practitioners. Last but not least it is useful to mention the titles of a few other papers to give the interested reader a short idea of what he can find: “Algorithms for the rural postman problem on directed graphs” (Christofides, Campos, Corberan and Mota), “Matching algorithms” (U. Derigs), “All optimal solutions to the network flow problem” (Christofides, Valls), multicommodity network flow” (G. Saviozzi), nonlinear network problems (Escudero, Dembo), etc. Jaime BARCELd Pau Gargallo, 5 Barcelona, Spain

SK. GUPTA Linear Programming and Network Models

Affiliated East-West Press, 104 Nirmal Tower, 26 Barakhamba Road, New Delhi, 1985, viii + 232 pages, Rs39.50 The wealth of literature and textbooks in the field of LP and network models makes it a difficult task to write a new and different book on these subjects. One has to design the book for a special readership, present the material (or part of it) in a novel way, include the latest research results, or likewise.



The present book, authored by S.K. Gupta, professor of mathematics at the Indian Institute of Technology, is an introductory text in which the geometric aspects of LP deliberately are almost completely ignored in favour of an algebraic approach. Much effort/space is devoted to post-optimality analysis and to extensive sets of problems for each chapter. The text, according to the publishers, “would serve as a text for those students in engineering, mathematics, statistics, and management requiring an exposure to a rigorous treatment at the introductory level”. The book has 5 chapters with well-known titles: The Simplex Algorithm - Duality Theory - PostOptimality Analysis - Transportation and Assignment Models - Network Models. Here, Network Models encompass minimum cost flow, maximum flow and shortest paths. In the preface, the author states that such aspects as modelling, computational efficiency, data structures and ‘often quoted algorithms’ have deliberately been left out, partly due to the intended readership. The book hereby, however, in my opinion misses any potential readership: the math student will be dissatisfied with the missing link between algebra and geometry, the engineering student will miss the computational and algorithmic aspects, and the management student needs at least an introduction to modelling. Especially the remarkable lack of comments on the efficiency of the described algorithms combined with the fact that computational complexity is not mentioned with one word is particularly serious to me-possibly due to my background in computer science. The annotation of almost all algorithms including e.g. Dijkstra’s shortest path algorithm and the labelling algorithm for the max flow problem reduces to ‘the algorithm is finite’. To illustrate the extent to which important recent results have been left out, I mention a few of these: The ellipsoid method, Karmarkar’s algorithm, and Dinic’s algorithm for max flow (and all its successors). Concluding my remarks on the contents of the book, no comments on future trends (impact of e.g. microcomputers or parallelism) are given. Each chapter of the book is, as mentioned, succeeded by an unusually large set of problems, some of which unfortunately contain essential points. Also a list of suggested readings follows each chapter; these lists, however, are nowhere


annotated, and all works referred to are published before 1977-an unexcusable deficit. Finally, I find it very unfortunate that the names of Dijkstra and Warshall are misspelled both in the text and the headlines. Such misprints affect the ‘credibility’ of the book heavily. Concluding, the main advantages and drawbacks of the book are: +: -.

extensive treatment of post-optimality; many problems to each chapter; the book is cheap. many important subjects are left out; references far from up to date; the approach taken with respect to geometry questionable (to say the least); the quality of paper, printing, etc. is low (matching the low price).

Even the price taken into consideration, I think the quality/price ratio is low compared with the average for textbooks in the field. Jens CLA USEN DIKV, Sigurdsgarde 41 Copenhagen, Denmark



Convexity and Duality in Optimization: Proceedings of the Symposium on Convexity and Duality in Optimization, Held at the University of Groningen, The Netherlands, June 22, 1984

Volume 256 in: Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, 1985, v + 142 pages, DM27.00 The book is a collection of four papers plus a historical overview presented at the symposium on Convexity and Duality in dptimization held at the University of Groningen at the occasion of conferring the Honorary Degree in Mathematics and the Sciences to Professor R.T. Rockafellar. All papers describe theoretical extensions in one direction or another of the classical theory of convexity and duality that owes so much to Rockafellar. The first paper, by Rockafellar, gives an introduction to the theory of Monotropic Programming, based on his book on the same topic. Monotropic Progr amming can be described as an extension of linear programming into the areas of equilibrium, primal-dual pairs, and piecewise linear programming, and many of the properties from

linear programming, including the pivoting solution process, are shown to carry over to the more general case. The second paper, by Hirriart-Urruty, analyzes the properties of differences between convex functions (d.c. functions). These functions are very general; note for example that a concave function is a d.c. function since it is the difference between a constant and a convex function. The papers give a thorough description of how to recognize d.c. functions, how to decompose them, and how optimality conditions specialize in terms of d.c. functions. A final section looks at the prospects for using d.c. functions in practical optimization. The third paper, by Ponstein, is entitled “From convex to mixed programming”. The paper looks at the extensions of classical convex programming to the case when there are two sets of variables, convex and nonconvex, and develops a new theory to analyze various forms of optimal control problems. In addition, the paper looks at regularity conditions within the more general framework. The last paper, by Haneveld, describes “Some linear programs in probabilities and their duals”. The problem addressed in the paper is to find probability measures over a certain space with prescribed moments or marginals, minimizing some criterion. Some interesting concepts of constraints and duality arise because of the probabilistic nature of the problems. All papers are very mathematically oriented. The book can be recommended to researchers with interest in deep mathematical properties of mathematical programming, duality, and convexity. It is probably too complex for the average operations research practitioner. Arne DRUD Analytic Support Unit, Development Research Department, The World Bank Washington, USA P.R. KRISHNAIAH Nonparametric

and PK. SEN (eds.)


Volume 4 in: Handbook of Statistics, North-Holland, Amsterdam, 1984, xx + 968 pages, Dfl.325.00 This is the 4th volume in the series Handbook of Statistics (general editor P.R. Krishnaiah).