Linear Optimization Problems With Inexact Data

In practical applications of linear programming, a significant issue is that the coefficients of a linear programming problem may not be known exactly. This research monograph discusses three approaches to the problem, including interval linear programming, linear programming with polyhedral set coefficients, and fuzzy linear programming. Two other approaches not discussed in this volume are stochastic linear programming and the robust optimization approach of Ben-Tal and Nemirovski [1].

In the first chapter, Fiedler provides a review of linear algebra and matrix theory. Chapters two and three, by Rohn, discuss systems of linear inequalities and linear programming problems in which the coefficients are inexact but lie within specified intervals. In chapter four, Nedoma and Ramik discuss a more general model in which the coefficients of the problem lie in polyhedral uncertainty sets instead of intervals. In chapter five, Ramik discusses linear programming with coefficients described by fuzzy sets. The final chapter by Zimmerman is on optimization over max-algebras.

The exclusion of stochastic linear programming is understandable since stochastic optimization is a well established subject with its own literature. However, the exclusion of any serious discussion of the work of Ben-Tal and Nemirovski on robust optimization with elliptical uncertainty sets is not justifiable. Their research has generalized earlier work on interval linear programming to a more general class of uncertain coefficients in sets defined by the intersections of ellipsoids and extended the approach from linear programming to a broader class of conic optimization problems. Without a discussion of the work of Ben-Tal and Nemirovski, this book can not be considered an up-to-date survey of methods for linear optimization problems with inexact data.

Additional problems with the book relate to its structure as a collection of chapters written by different authors. The introductory chapter reviewing linear algebra and matrix theory contains a lot of material that is simply not referenced elsewhere in the book. Other chapters needlessly duplicate definitions and theory that have been developed elsewhere in the book. Connections between methods for interval linear programming problems and problems with polyhedral set coefficients are not made clear. The chapter on optimization over max-algebras by Zimmerman has little or no connection to the other chapters in the book.

Overall, this book fails in its goal of presenting "a comprehensive treatment of linear optimization with inexact data." However, the book may still be of interest to readers interested in the particular approaches that are treated by the authors.

---

References

[1] A. Ben-Tal and A. Nemirovski, Robust Optimization - Methodology and Applications, Mathematical Programming 92(2002):453-480.

---

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.