|
Article Excerpt
Practitioners of optimization-based decision support advise commerce and government on how to coordinate the activities of millions of people who employ assets worth trillions of dollars. The contributions of these practitioners substantially improve planning methods that benefit our security and welfare. The success of realworld optimization applications depends on a few trade secrets that are essential, but that rarely, if at all, appear in textbooks. This paper summarizes a set of these secrets and uses examples to discuss each.
"Thou shalt never get such a secret from me but by a parable." Shakespeare, The Two Gentlemen of Verona
Key words: decision-support systems; integer programming applications; linear programming applications. History: This paper was refereed.
**********
Clients consult specialists because they have realworld problems to be solved. Clarifying a problem statement by talking with a client or, better, getting first-hand experience with the client organization is very different from reading a textbook case study. (However, some clients might feel that your success would threaten their jobs.) In this paper, we offer advice that we learned from completing hundreds of optimization-based decision-support engagements over several decades. These are hard-won lessons based on field experience. As a practitioner of our optimization art, you must obtain some experience beyond textbook coursework before these suggestions will make complete sense to you. Thus, you will not find this material highlighted in any textbook. Providing decision support in the real world is difficult because it requires that you deal with enterprise data systems, legacy procedures, and human beings who might not share your passion for making things better.
We receive many phone calls from colleagues and ex-students who are working with optimization. Sadly, too many of these callers do not extol the wonders of optimization; rather, they lament practitioner problems in getting things to work right. Unfortunately, this may have given us a distorted view of the issues we address here.
In this paper, we present our tradecraft in the topical categories that we have used to collect our lessons learned. Even if you are not a practicing optimizer, we suspect you will find insights here.
Design Before You Build
We have had an astonishing number of opportunities to address problems with optimization models that have been implemented, but are behaving badly (e.g., they are very hard to solve, too large to solve, or produce strange results) and are not documented. They have been built without a design!
Documentation must--not should, must--include these three critical components:
* A nonmathematical executive summary,
* A mathematical formulation, and
* A verbal description of the formulation (Figure 1). A nonmathematical executive summary must answer the following five questions, preferably in this order (Brown 2004a):
* What is the problem?
* Why is this problem important?
* How would the problem be solved if you were not involved?
* What are you doing to solve this problem?
* How will we know when you have succeeded?
[FIGURE 1 OMITTED]
Express your executive summary in your executive sponsor's language, rather than in technical jargon. If you have trouble writing such a summary in less than five pages, you are not ready to proceed. The following tricks will make writing your summary easier and more effective:
* Have a nonanalyst read your executive summary to you, out loud,
* Ask this reader to explain your executive summary to you,
* Listen well, and
* Revise and repeat.
A mathematical formulation should include the following in this order (Brown and Dell 2007):
* Index use (define problem dimensions),
* Given data (and units),
* Decision variables (and units),
* Objectives and constraints, and
* (perhaps) a dual formulation.
Remember to define terms before using them. The earliest definition of such a standard formulation format appears in Beale et al. (1974). To distinguish inputs from outputs, adopt a convention such as using lowercase for indexes and data, and uppercase for decision variables.
A verbal description of the formulation (Figure 1) explains, in plain English and in your executive sponsor's language, what each decision variable, objective, and constraint adds to the mathematical model. It gives you the opportunity to define what the mathematics means and why each feature appears in your model. Avoid literally translating mathematics into English. For example, avoid saying "the sum of X over item subscripts i must be no more than m for each time subscript t." Instead, say "the total production of all items must not consume more raw material than will be available in any year." Do state and justify any simplifying assumptions (some examples include "our planning time fidelity is monthly, with a 10-year planning horizon," and "we allow fractional production quantities of these large volumes").
Bound All Decisions
Bounds restrict the domain of every decision. An unbounded variable does not exist in our real, OR analyst's world. Establishing bounds for each decision variable is a trivial concept that is often ignored. While any reasonable optimization solver will do this automatically, the solver cannot tell you that its analysis is based on bogus data or missing features in your model. If you manually apply simple ratio tests (e.g., "If I had all the steel the world produced this year, how many automobiles could I build?") and get ridiculous answers (e.g., "2.1 autos," or "10 trillion autos"), you have discovered an error either in the data or in the description of the manner in which automobile production consumes steel. These conversions reveal an erroneous steel consumption rate per auto or a constraint that has no influence on your model; thus, you can jettison them.
Do you remember all the formal "neighborhood" assumptions that underlie your optimization method? Taylor's theorem makes any continuous function appear linear if you bound your decision neighborhood tightly enough. All your costs and technology likely exhibit nonlinear effects across widely varying magnitudes; however, they might not exhibit the same effects over a small neighborhood--the domain for which you are planning.
It is easier to branch-and-bound enumerate models with integer variables if the bounds on the integer variables are as tight as possible. This is worth addressing before you try to solve large models. If the tightest bounds that you can state permit a "large" integer domain, relax the integrality requirement and round the continuous result to the...
|
