SIAM Short Course on
Post-Solution Analysis in Mathematical Programming

Sunday, May 9
Sheraton Spirit of Atlanta Hotel, Atlanta, Georgia

Contents

Questions? E-mail [email protected].

OP99 Home

 

 

Organizer

Harvey J. Greenberg, University of Colorado, Denver

Rationale

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.

Course Description

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.

Course Objectives

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

Introductory 5%
Intermediate 85%
Advanced 10%

Who Should Attend

Engineers, economists and applied mathematicians with responsibilities that include mathematical programming modeling and analysis.

Recommended Background

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.

Instructors

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.

New 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.

Program

Morning

8:00 Registration

8:00 - 8:30 1. Background and Basic Concepts

8:30 - 10:00 2. Linear Programming

  • 2.1 Basic compatibility theory

  • 2.2 Sensitivity analysis from an interior solution
  • 2.3 Infeasibility diagnosis
  • 2.4 Qualitative sensitivity analysis

10:00 - 10:30 Coffee

10:30 - 12:00 Linear Programming (continued)

Afternoon

12:00 - 2:00 Lunch

2:00 -3:30 3. Integer Programming/Combinatorial Optimization

  • 3.1 General approaches

  • 3.2 Stability analysis for particular problem classes (e.g., scheduling)
  • 3.3 Infeasibility diagnosis

3:30 - 4:00 Coffee

4:00 - 5:00 4. Nonlinear Programming

  • 4.1 Sources of nonlinearity: Convex and Nonconvex Problems

  • 4.2 Beyond Lagrange multipliers
  • 4.3 Infeasibility diagnosis

5:00 - 5:30 5. Survey of Software for Post-solution Analysis

5:30 Short Course adjourns

Registration

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.

Location

This short course will be in Atlanta 1. The coffee breaks will be in Convention Lobby; lunch will be in Capitol South.

MMD Created: 12/21/98 Updated: 3/1/99