SIAM Short Course on
Questions? E-mail [email protected]
Harvey J. Greenberg, University of Colorado, Denver
In linear programming, little is written in texts about post-optimal sensitivity analysis from an interior (nonbasic) solution, but new results have accrued over the past 6-7 years. In integer programming, particularly combinatorial optimization problems, new results have been obtained only recently. In nonlinear programming, the focus has been on continuity and differentiability properties, and Lagrange multipliers have been the dominate means for marginal analysis; there is very little on more realistic analyses, especially for non-convex programming problems. In all types of mathematical programs, there are few expository papers and books on debugging, such as diagnosing infeasibility. For all of these reasons, this course is a timely survey of what we know and what questions are open for further research.
This course will begin with some background and quickly review relevant elements of duality. The classical linear programming analysis is cast into a framework called "compatibility theory," whose introduction was for basic solutions. Then, sensitivity analysis from an interior solution will highlight the information value of an optimal partition with applications in several areas. Sometimes the structure of a model, apart from the specific numerical values of data, can be enough to answer some post-solution analysis questions. This is called "qualitative analysis," and we shall consider a few examples to illustrate rich theories that have developed over the past two decades. We then consider infeasibility diagnosis, which includes several strategies and how they compare, for various examples. After a comprehensive survey of LP post-solution analysis, attention shifts to integer programming problems, which includes combinatorial optimization. A recent published survey will provide a starting point, and we shall focus on stability region analysis for classes of combinatorial optimization problems. This will include the advent of animation (e.g., for TSP, if we have web access). Infeasibility diagnosis will include methods logical inference and recent connections between computational logic and integer programming. The last category is nonlinear programs, where much of the published work stems from Lagrange multipliers. The pooling problem will be used to illustrate a geometric approach to a non-convex problem. The course will conclude with a survey of software systems that provide post-solution analysis capabilities beyond the usual printing of dual values.
For additional information, see http://www.cudenver.edu/~hgreenbe/sessions/siam99.html.
Attendees will obtain an understanding of the state-of-the-art in post-optimal analysis;an understanding of how to debug an infeasible instance; information value in solutions; information value in model relations; and knowledge of the literature to continue this avenue of study
Level of Material
Who Should Attend
Engineers, economists and applied mathematicians with responsibilities that include mathematical programming modeling and analysis.
First year graduate knowledge of linear, integer and nonlinear programming. A minimum knowledge is exemplified by the book: W.L. Winston, S.C. Albright and M. Broadie, Practical Management Science, Duxbury Press, Belmont, CA, 1997. Most of the material will be more advanced, and the attendee is expected to know underlying mathematics, notably linear algebra. The following references contain additional background on the primary subjects: T. Gal and H.J. Greenberg, 1997. Advances in Sensitivity Analysis and Parametric Programming, Kluwer Academic Press, Boston, MA.; H.J. Greenberg, 1997-8. LP Short Course, http://www-math.cudenver.edu/~hgreenbe/courseware/LPshort/intro.html S.G. Nash and A. Sofer, 1994. Linear and Nonlinear Programming; McGraw-Hill, New York, NY.
Professor Greenberg has been Professor of Mathematics at the University of Colorado since 1983. Previously, he held positions in government, industry and academia. Since receiving his Ph.D. from The Johns Hopkins University in 1968, he has published about 100 papers and 3 books. He has also co-edited 2 books and 5 proceedings. Professor Greenberg serves on 5 editorial boards and was the founding editor of INFORMS Journal on Computing. He was the first recipient of the INFORMS/CSTS Award for "research excellence in the interfaces between operations research and computer science." He has received several honors since then, the most recent being the Harold Larnder Prize, to be awarded in 1999 by the Canadian Operational Research Society. Among his current research interests is the development of an intelligent mathematical programming system, which uses the advanced analysis techniques covered in this short course.
Allen Holder recently completed Ph.D. studies at the University of Colorado at Denver under the tutelage of Professor Harvey Greenberg. His thesis dealt with the sensitivity of the analytic central path, which is the geometric structure that allows the the class of linear programming problems to have polynomial complexity. Over the last couple of years, he has (co)authored 5 articles, two of which are about to appear in print. Allen Holder's current research interests include the generalized convergence of the central path under parameterization, polyhedral representations, and applications in the medical field of radiation oncology.
8:00 - 8:30 1. Background and Basic Concepts
8:30 - 10:00 2. Linear Programming
10:00 - 10:30 Coffee
10:30 - 12:00 Linear Programming (continued)
12:00 - 2:00 Lunch
2:00 -3:30 3. Integer Programming/Combinatorial Optimization
3:30 - 4:00 Coffee
4:00 - 5:00 4. Nonlinear Programming
5:00 - 5:30 5. Survey of Software for Post-solution Analysis
5:30 Short Course adjourns
Seats are limited. We urge attendees to register in advance. To register, please complete the online Preregistration Form and submit to SIAM. Registration fee for the course includes course notes, coffee breaks, and lunch on Sunday, May 9.
This short course will be in Atlanta 1. The coffee breaks will be in Convention Lobby; lunch will be in Capitol South.