A. Geoffrion
UCLA Anderson School of
Management
Last revised May, 2005
This commentary organizes my writings into four major categories. Three are
for research, herein called theory-driven, application-driven,
and foundational. They overlap considerably in chronology and are
related: the second builds directly on the first, and the third is a child
of the other two. The fourth category, professional writings, addresses
practitioners and those who share an interest in the evolution of OR/MS.
My theory-driven work, from 1965 through about 1977, was devoted to mainstream mathematical programming. My aim was to better understand available mathematical programming theory and algorithms, and to improve and augment these along lines I believed fundamental or applicable (although typically with no particular application in mind).
My application-driven work, roughly 1972 through 1985, focused on using mathematical programming models to solve a variety of real problems. I particularly sought out opportunities for pioneering applications requiring the development of novel or advanced optimization techniques.
By the mid-1970s, my practical experience was reshaping my views on the kinds of research needed to make modeling and mainstream mathematical programming more applicable. It became increasingly evident that available foundations were seriously inadequate in several key areas on the boundary between theory, technique, and practice, and that the practical achievements of modeling and mathematical programming will forever remain far short of their full potential until some of these deficiencies are remedied. Thus began, about 1977, certain efforts that I call “foundational” for want of a better word. The modeling context of this work evolved to become considerably broader than my original field of mathematical programming.
My professional writings began in the latter 1970s as an effort to capture some of my interactions with practitioners, to integrate the theoretical and applied aspects of OR/MS, and to understand the requirements for the future health of the profession.
Fully elaborated, the topical classification of my writings is as follows:
I. THEORY-DRIVEN
A. Parametric Concave Programming: c3+c5, c9, f1II. APPLICATION-DRIVEN
B. Integer Programming: *c7, *c11, *c15, *c19, c25
C. Multi-Criterion Optimization: *c6, *c10, *c17, b2+g2, g3
D. Large-Scale Optimization and Decomposition: c4, c12, *c13+c1, *c16, c26, g1
E. Other Optimization Topics: c8, *c14, d1
A. Supply Chain Management: *c18, *c29, c35+b3III. FOUNDATIONAL
B. Other Application Domains: c22, c34, d3, f2, f3
A. Auxiliary Models: c24, c30, b4
B. Approximation and Aggregation Theory: c27, c28, f4, g5, g6, g7
C. Modeling:
Computer-based Modeling Environments: c38, c40, c44+d5+g10, d6
Foundations of Modeling (Structured Modeling): *c37+g8, c39, c41+g11, c42+c43+g9+g12, c46+f5+f6, c47, b5, d4, c49
IV. PROFESSIONAL (non-research)
A. Intended for Managers and Practitioners: c20, c21, c23, c31, c32, c33, c48, b6, d2
B. Evolution of OR/MS: c36, c45, g4
C. Commentaries on OR/MS and the Emerging Digital Economy: c50, c51+c52, c53, c54+c55
The same numbering is used here as in my comprehensive on-line List of Publications. A "+" is used to combine items best viewed as a single unit. Items marked by an asterisk [*] identify the ones most frequently cited in the open literature (more than 100 citations at last count).
Below I explain briefly the topics listed and sketch the focus of the papers.
However, I make no systematic attempt to summarize my contributions to these
topics.
Parametric programming seeks an optimal solution to each of an entire continuum of optimization problems that are all identical except for the value of a numerical parameter. This generalization of the classical parametric LP problem is important for such tasks as computing the trade-off curve and efficient solution set when there are two objectives, probing the influence of selected parameters on the optimal value and optimal solution, coping with uncertainty in the values of problem coefficients, and overcoming difficulties posed by certain types of objective function nonlinearity.
This topic was central to my dissertation f1. The focus of c3 and c5 is on developing a new parametric algorithm that exploits continuity properties of the Kuhn-Tucker optimality conditions. The focus of c9 (which could have been classified under topic I.C) is on showing how to exploit available parametric programming algorithms for the purpose of solving certain stochastic programming models, and on showing how to usefully interpret the by-products of such computations.
Integer programming addresses discrete-valued decision variables in optimization models, possibly in combination with continuous-valued decision variables. Discrete-valued variables are commonly used to model indivisibility (e.g., fractions of people cannot be transported), to represent binary decisions (e.g., accept or reject a candidate project), to embody logic (e.g., multiple choice constraints), and to deal with certain types of nonlinearity in an otherwise linear model.
My algorithmic focus was initially (c7) on an improved reformulation of Balas' original implicit enumeration method, then on reconciling this with the generally more efficient LP-based branch-and-bound approach (c11), next on developing a unified algorithmic framework covering the major known computational approaches (c15), and finally on theoretical foundations for parametric and postoptimality techniques (c25).
The work just mentioned addressed arbitrary integer linear programming models. Article c19 established Langrangean relaxation as a technique for exploiting special model structure within the branch-and-bound context. This technique is now popular among researchers studying large-scale applications. (Although classified here, my motivation for working on Lagrangean relaxation derived from the need to solve industrial-scale supply chain design problems [topic II.A].)
Whereas classical optimization has but a single objective function, real applications often have several worthy candidates for this role, and possibly also some constraints with discretionary limits or aspiration levels that can be viewed as objective functions. Long a popular subfield of optimization, multi-criterion optimization seeks to extend existing optimization theory and algorithms to cope with more than a single objective function.
My interest in this topic dates from my doctoral dissertation f1, and furnished the main motivation for my work on parametric concave programming. Article c6 draws on that work to develop a method for 2-criterion problems with an explicit quasiconcave overall utility function, a common case that also subsumes certain nonlinear programming problems of independent interest. Article c10 introduces proper efficiency as a refinement of the well-known concept of Pareto optimality, and gives a comprehensive analytical characterization of it. Article c17 shows that optimization algorithms can be applied to multi-criterion optimization models even when the overall utility function is implicit; such models can be solved interactively if the decision-maker can furnish, on demand, certain local information such as marginal rates of substitution. Finally, b2 extends the approach of the previous paper to hierarchically structured organizations.
The history of applied optimization teaches that practitioners have an insatiable appetite for ever-larger models. There are only three basic ways to substantially increase the size of models that can be optimized other than switching to better computer hardware: contrive superior implementation strategies (such as better data structures) for existing methods, develop fundamentally new optimization methods, and devise better ways to exploit the special structure of large models.
My work has been mainly of the last type, a very rich area because large models occurring in practice almost always possess much exploitable special structure. My first effort (c4) aimed to recast an early specialized resource allocation method into a modern framework. Then came a study (c12) of three computational approaches to coordinating resource allocation in systems composed of semi-autonomous subsystems. Next I developed a unifying conceptual framework embracing most known methods for large-scale optimization (c13+b1 and g1). Article c16 extends one such method, Benders Decomposition, from the linear to the nonlinear case, a generalization for which surprisingly many authors subsequently found application. Finally, c26 explores how two distinct streams of algorithmic research -- discrete/combinatorial optimization and convex programming -- can be combined to handle hybrid models.
I worked on two other topics, one in the mainstream and one not. The mainstream
topic was optimality and duality theory for convex programming, a subject at
the core of optimization theory that I reworked and extended using the powerful
concept of right-hand-side perturbation functions (c14).
The other topic was an algorithm for reducing convex optimization problems
with some linear inequality constraints to a sequence of similar problems with
only linear equality constraints (c8, d1).
My work in the field of logistics – a nearly $1 trillion chunk of the U.S. economy at this writing, not counting another $5 trillion for procurement – focuses on the strategic design of supply chains containing an echelon of warehouses between plants and customers. The design decisions are how many warehouses to have and where, what size they should be, which customer zones each should serve for particular products, what the inbound and outbound transportation flows should be, and how much of each product should be produced by each plant. The aim is to minimize all impacted costs (production, transportation, storage, etc.) while observing all pertinent constraints (production capacities, warehouse throughput limits, customer single-sourcing, demands to be met, etc.).
This work builds on my previous research in topical areas I.B and I.D. Article c29 further develops the theory of Lagrangean relaxation for a related classical logistics model, but c18 is the core of my work in supply chain management. It specializes Benders decomposition to the problem at hand in such a way that a separate classical transportation problem falls out for each individual product. This enabled practical multicommodity supply chain design problems to be solved efficiently for the first time.
Although I have not been directly involved for more than a decade, the approach just mentioned is the heart of a software system (c35, b3) that has continued to evolve and has been used by now to improve the supply chains of more than 200 companies. (And also for the Department of Defense: this system served as the optimizer for a 3-year, high-level study aimed at reorganizing the U.S. defense logistics system for all four armed services and the Defense Logistics Agency; further details appear in J. Hall's Management Science Update column in the August 1980 issue of Management Science. A second such column in the October 1980 issue overviews a private-sector application.)
A retrospective (c48) presents the main lessons learned during more than two decades of work in strategic supply chain design.
Two projects in production were adopted for use by the sponsors. The first developed a hybrid algorithm for the detailed scheduling of chemical reactors producing polyethylene (c22). Other potential applications exist in most continuous process industries with sequence-dependent changeover costs, and in bulk production and packaging lines in the food and consumer goods industries. The second project applied c19's Lagrangean relaxation results to production and sales planning for a manufacturer of injection molded goods (c34). Other potential applications exist for facilities that cast, mold, stamp, extrude, or press finished or nearly finished products. This work was noted in Business Week (cited in c34).
A third effort in production never reached the implementation stage. Report f2 explains how to apply the method of c16 to uranium enrichment at the Atomic Energy Commission.
My biggest applied project outside of logistics and production was financial (d3): the development of an integer programming-based system for GTE (now part of Verizon) to optimally allocate their annual 3 billion dollar capital expenditure budget while taking very detailed account of financial consequences, as well as considering impacts on service and non-financial resources.
Report f3 explains
how to apply the new approach of c17 to
university management.
Early in my career, I naively assumed that for real applications it would be sufficient technically to be able to build and solve large and complex optimization models. But it turns out that it is also necessary, for managerial understanding and acceptance in strategic applications, to be able to explain why the optimal solutions are what they are (at least at some aggregate level of detail). Such questions tend to be embarrassing to all but the most resourceful practitioners. The ad hoc approaches in use were unsatisfying. More rigorous approaches clearly were needed.
The thesis of this research stream is that small, analytically tractable models can be built as companions to detailed optimization models, and can be used to obtain satisfying explanations of why the detailed optimal solutions are what they are in important respects.
Articles c24 and c30 demonstrate this thesis to my satisfaction in the context of strategic supply chain design (see also b4). The same approach could be taken in other problem domains.
One of the shocks I received almost immediately upon undertaking practical applications was the discovery that, although real models frequently require a great deal of approximation and aggregation, there is hardly any guiding theory. Approximation issues arise, for example, when a slight change in the mathematical form of a function or of model structure would allow a dramatically more powerful solution method to be used. Aggregation issues arise when there are more customers, locations, products, time periods, etc., than could or should be treated explicitly in a model.
Hence I set out to invent approximation and aggregation methods that admit computable a priori error bounds.
I did only a little work on approximation in its pure form, obtaining some quite general results for objective function approximation (c27). But I did a good deal of work on theory and methods for model aggregation, including c28, g5, g6, and g7. My aim was a unified theory that would be broadly applicable throughout OR/MS and related model-based fields (e.g., parts of economics and information systems). A draft research monograph (f4) made considerable progress toward this aim, but I did not submit it for publication because some ideas having their genesis therein diverted my attention. Originally intending to set the monograph aside for a year or so to develop these ideas, which had been created to serve as one of the monograph's main foundation stones, to this day I have not yet begun the now-necessary revisions.
My experience with real applications soon led to the realization that the technical challenges associated with designing and solving an optimization model are only a small part of the total life-cycle of a typical optimization application. Success in practice depends on doing a lot of other things efficiently and well. Yet for reasons not difficult to discern, OR/MS academics focus most of their attention on the life-cycle phases that happen to be amenable to mathematical study. Clearly there is a major need for improved computer-based support for the entire modeling life-cycle. I call a system with such capabilities a modeling environment, and devoted the better part of a decade to work in this direction. Some of that work goes by the rubric “structured modeling”, and some does not.
My approach was systematic and comprehensive, including: a vision (c40+g8, c38, c37), a new semantic foundation for thinking about modeling (c39), a new language for describing models within this foundation (c42+c43+g9+g12), a prototype modeling environment that supports this language (c41+g11, c46+f5+f6), proposals for how model-based work could be conducted within such an environment (c37, d4), and results of independent interest on indexing in modeling languages for mathematical programming (c44+d5+g10). I consider this research stream to be complete in all essentials.
My written works in this stream, and those of other authors who have contributed to it, are described in (c49). Article c47 surveys research opportunities, and there is also an encyclopedia article (b5). If there is one pervasive theme of this research stream, it is that the ad hoc nature of existing modeling languages and systems should be replaced by rigorous foundations and rigorous design.
Much remains to be done to bring the vision to fruition. There have been
several prototype modeling systems, practical applications in Chile (d6)
and elsewhere, and influences on the design of modeling languages and systems
not in the structured modeling mold, but conditions may not yet be right for
new commercial modeling software that would support the entire modeling life-cycle
and accommodate multiple modeling paradigms as seamlessly as should be possible.
Over the years I have attempted to communicate technical developments and practical ideas in an accessible way to managers and practitioners (including practice-minded academics). Most of these efforts arose from my application-driven work in supply chain management applications (c20, c23, c31, c32, c33, c48, b6, d2), and one did not (c21).
I have a long-standing interest in the development and direction of the OR/MS profession. Article c36 is my 1982 TIMS Presidential Address, and c45 is an extended version of my 1991 Omega Rho Lecture. Both articles take a long-term view and bristle with ways in which individuals, and especially professional societies, can exploit the great opportunities provided by the milieu within which OR/MS takes place.
The last decade has seen the birth, boom, bust, and now the steadily increasing maturity of e-business. There is no turning back. The consequences for OR/MS clearly are great, but what will be the greatest opportunities and impacts? As a student of Internet applications since the 1980s and a teacher of same since 1993, I have thought a good deal about that question.
Article c50 points out some largely overlooked opportunities for OR/MS in connection with business-to-consumer e-commerce. Article c53 broadly examines mechanisms by which advances in digital technology and the digital economy shape progress in OM, a sister field of OR/MS, and points out how to use these mechanisms to better guide R&D efforts by the academic and practitioner communities.
Together with R. Krishnan, I edited a special issue of Interfaces and two special issues of Management Science on OR/MS and the emerging digital economy. The first surveys the state of practice and OR/MS opportunities from an applied perspective, and the second pair of special issues surveys the state of research. Our reflections on the articles appearing in these issues and on the implications of e-business for OR/MS appear in c51+c52 and c54+c55. Article c52 includes a detailed explanation of why OR/MS is well matched to the needs of the digital economy, and takes special pains to spell out implications for practitioners. Articles c54 and c55 offer answers to these key questions: (1) What fundamentally new research questions arise?, and (2) What kind of research enables progress on them? These special issues paint a reasonably comprehensive picture as of the date written.
