Skip to main content

Über dieses Buch

This volume chronicles the high impact research career of Harvey Greenberg (1940-2018), and in particular, it reviews historical contributions, presents current research projects, and suggests future pursuits. This volume addresses several of his most distinguished hallmarks, including model analysis, model generation, infeasibility diagnosis, sensitivity analysis, parametric programming, energy modeling, and computational biology. There is also an overview chapter on the emergence of computational OR, and in particular, how literature venues have changed the course of OR research.

He developed Computer-Assisted Analysis in the 1970s and 80s, creating an artificially intelligent environment for analyzing mathematical programming models and their results. This earned him the first INFORMS Computing Society (ICS) Prize for "research excellence in the interfaces between operations research and computer science" in 1986, notably for his software system, ANALYZE.

In 1993, he wrote the first book in the Springer OR/CS Series entitled A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User’s Guide for ANALYZE. He applied OR methods to CS problems, ranging from using queuing theory for optimal list structure design to using integer programming for bioinformatic database search. He also applied CS to OR problems, ranging from super-sparse information structures to the use of compiler design in ANALYZE. This book can serve as a guide to new researchers, and will report the historical trajectory of OR as it solves current problems and forecasts future applications through the accomplishments of Harvey Greenberg.



Chapter 1. A Commemorative Review of Harvey Greenberg’s Career

Harvey J. Greenberg’s career in Operations Research (OR) and Computer Science (CS) spanned the half-century from his Ph.D. dissertation in 1968 to his death in 2018. The magnitude of his accomplishments in those 50 years is profound, enough so that it is difficult to communicate his legacy’s entire imprint. Harvey had outstanding academic success, but he also played critical roles in guiding public policy, in advancing OR’s industrial employ, and in building community. Most OR professionals could pridefully review their careers with noteworthy success in just one of these categories, but Harvey’s substantive influence in each has distinguished him as one of his era’s definitive bellwethers. Harvey’s era was of particular note because it witnessed OR blossom from its military and industrial origins to its expansive embrace of modern algorithms and computing.
Allen Holder

Chapter 2. How the Work That Harvey and I Did at the Federal Energy Administration (Later Department of Energy) Shaped Our Research Careers and Led to Our Decades Long Collaboration and Friendship

Harvey and I began working together at the Federal Energy Administration, the predecessor to the Energy Information Administration. Our most intense period was when we were doing research on the fly to model the impacts of policies that were under consideration when the White House Energy Policy Office was developing Carter’s National Energy Plan. I describe here the equilibrium modeling and analysis we did to estimate the impacts of the National Energy Plan and other policy proposals. Because we were in untrodden territory, we wound up with decades worth of research questions from that short, intense period. I cover some of these areas and describe some of our work together after leaving Washington, and I mention the current state of the art in these areas and the areas where our research took different paths. I also point out some of the research questions that still need answers.
Frederic H. Murphy

Chapter 3. Software for an Intelligent Mathematical Programming System

Creating and understanding optimization models, instances, and solutions of any significant size present a serious challenge, even to experts in the field. Greenberg pursued an initiative in the 1980s and 1990s to support research and development of computer-assisted technologies to aid decision makers in developing models and investigating model, instance, and solution structures and implications, which he dubbed the Intelligent Mathematical Programming System (IMPS). Among Greenberg’s contributions is a suite of software tools that demonstrated the potential for the initiative, including MODLER (a structured model and instance builder), RANDMOD (a structured randomization tool), and ANALYZE (a system for analyzing the structure of model instances and solutions). This paper surveys the capabilities of these tools and their underlying technologies.
Matthew J. Saltzman

Chapter 4. Harvey Greenberg: Analyzing Infeasible Mathematical Programs

As part of his Intelligent Mathematical Programming System project, Harvey Greenberg investigated theory and developed methods for diagnosing the cause of infeasibility. The emphasis was on developing useful and practical tools for isolating the problem to a small part of a large model and arriving at an understandable explanation, or diagnosis, of the infeasibility. He leveraged known mathematical theorems—and developed new ones—to create the requisite tools for incorporation into his ANALYZE software. This chapter summarizes his contributions to practical methods for analyzing infeasible mathematical programs.
John W. Chinneck

Chapter 5. Development of Publications and Community at the Interface Between Operations Research and Computing

Harvey J. Greenberg’s energy and dedication to the field of operations research yielded an impressive array of contributions in undergraduate and graduate education, research, and professional service. This chapter focuses on his instrumental role in creating a journal, book series, and professional society, all of which remain strong and influential today. The journal is now the INFORMS Journal on Computing and is currently publishing its 31st volume. The TutORials in Operations Research book series is currently publishing its 15th annual volume, and the ever-growing INFORMS Computing Society traces its roots back over 40 years from the time it was a special interest group within ORSA.
J. Cole Smith

Chapter 6. Parametric Stochastic Programming with One Chance Constraint: Gaining Insights from Response Space Analysis

We consider stochastic programs with discrete scenario probabilities where scenario-specific constraints must hold with some probability, which we vary parametrically. We thus obtain minimum cost as a function of constraint-satisfaction probability. We characterize this trade-off using Everett’s response space and introduce an efficient construction of the response space frontier based on tangential approximation, a method introduced for one specified right-hand side. Generated points in the response space are optimal for a finite set of probabilities, with Lagrangian bounds equal to the piece-wise linear functional value. We apply our procedures to a number of illustrative stochastic mixed-integer programming models, emphasizing insights obtained and tactics for gaining more information about the trade-off between solution cost and probability of scenario satisfaction. Our code is an extension of the PySP stochastic programming library, included with the Pyomo (Python Optimization Modeling Objects) open-source optimization library.
Harvey J. Greenberg, Jean-Paul Watson, David L. Woodruff

Chapter 7. An Analysis of Multiple Contaminant Warning System Design Objectives for Sensor Placement Optimization in Water Distribution Networks

A key strategy for protecting municipal water supplies is the use of sensors to detect the presence of contaminants in associated water distribution systems. Deploying a contamination warning system involves the placement of a limited number of sensors—placed in order to maximize the level of protection afforded. Researchers have proposed several models and algorithms for generating such placements, each optimizing with respect to a different design objective. The use of disparate design objectives raises several questions: (1) What is the relationship between optimal sensor placements for different design objectives? and (2) Is there any risk in focusing on specific design objectives? We model the sensor placement problem via a mixed-integer programming formulation of the well-known p-median problem from facility location theory to answer these questions. Our model can express a broad range of design objectives. Using three large test networks, we show that optimal solutions with respect to one design objective are often highly sub-optimal with respect to other design objectives. However, it is sometimes possible to construct solutions that are simultaneously near-optimal with respect to a range of design objectives. The design of contamination warning systems thus requires careful and simultaneous consideration of multiple, disparate design objectives.
Jean-Paul Watson, William E. Hart, Harvey J. Greenberg, Cynthia A. Phillips

Chapter 8. A Simplex Approach to Solving Robust Metabolic Models with Low-Dimensional Uncertainty

We address the problem of solving difficult metabolic models that arise in the study of flux balance analysis (FBA). FBA problems are regularly linear due to simplifying assumptions although quadratic, combinatorial, and robust extensions are pragmatic variations. All such extensions inherit an underlying computational difficulty from the linear model, although in many instances this concern can be avoided by selecting an appropriate solution algorithm. Robust extensions unfortunately lack a trustworthy computational standard and are thus difficult to solve and problematic to employ. We show that a robust model’s optimal value can be calculated by coupling standard nonlinear schemes with a technique of successive linear approximation, and we further indicate how the computational outcome might differ from the intent of the original robust model. We test our algorithm on two simple, motivating examples and on a standard FBA problem.
Allen Holder, Bochuan Lyu
Weitere Informationen

Premium Partner