Optimal Decision Analytics

Challenging Research Topics

To launch the New Year, the Optimal Decision Analytics Blog is featuring a series of articles about research topics that are ripe for exploration, whether in the form of projects by seasoned researchers or in studies carried out as doctoral thesis investigations.

The articles will cut across the areas of metaheuristics and classical optimization, running a gamut of topics of interest to researchers and practitioners alike.

Subjects to be covered will range from mixed integer programming to data mining, with excursions into simulation, risk analysis, stochastic & nonlinear programming and black box optimization.

You are invited to respond with comments not only about the topic currently posted, but also about additional topics you would like to see covered.

The first topic examined falls in the area of metaheuristic strategies that may be used to enhance mixed integer programming methods.

 

Metaheuristic Multi-start Strategies for Mixed Integer Programming

Classical branch-and-bound and branch-and-cut strategies for mixed integer programming (MIP) have an intriguing relationship to multi-start (M-S) procedures that have emerged in metaheuristic optimization. Successes of metaheuristic strategies in a variety of settings have been attracting a growing number of researchers to give attention to these approaches. It is by now well known that, although they do not guarantee optimality, metaheuristics have found an important place in the quest to obtain high quality solutions for problems where certifiably optimal solutions are hard to come by, and where classical optimization methods have chalked up a less-than-spectacular performance record. Within the metaheuristic domain, multi-start strategies have carved out a well-earned place both as stand-alone methods and as supporting procedures to enhance the performance of other metaheuristics. The conspicuous relationship of mult-start methods to “forward phases” of tree search strategies embedded in classical MIP branch-and-bound and branch-and-cut methods stimulates the speculation that perhaps some of the multi-start ideas might be fruitfully transplanted to the MIP area.

Background and Suggestions for Combining Multi-Start and MIP Methods

There has been no dearth of attempts to marry metaheuristic optimization with classical optimization – in fact, the term “matheuristics” has been coined to give recognition to the burgeoning efforts in this realm – but so far relatively little attention has been devoted to broaching the domain of MIP problems formulated in their abstract form. For MIP problems that don’t readily lend themselves to more specialized formulations recourse almost inevitably is made to procedures that marry state-of-the-art linear programming (LP) solvers with tree search and cutting plane methods.  Consequently, commercial MIP solvers have grown up hand-in-hand with the development of the leading LP solvers. Meanwhile, only scattered efforts have been made to embed metaheuristic strategies within such MIP solution machinery, focusing chiefly on isolated special cases. This is not surprising, given that metaheuristics perform best for problems exhibiting special structures that can be exploited by flexible and ingenious artifices, as opposed to problems that we only know how to express in abstract mathematical formulations.

Still, it’s hard to miss the fact that the tree search framework underlying branch-and-bound and branch-and-cut methods is well suited to be addressed by multi-start strategies developed in the metaheuristic domain. The formal classical approaches and the metaheuristic approaches both contend with the same challenge of executing sequential decision steps that build a solution in stages (performed in the MIP setting by progressively narrowing bounds imposed on integer variables). Both types of approaches interrupt the forward progression when a fully realized candidate solution is obtained, or when no feasible continuations exist, and then pick up again at some point in a previous sequence of steps. (Most M-S methods re-start from scratch after concluding their forward progression, but others – based on strategic oscillation – dismantle some subset of decisions underlying a current construction as a prelude to rebuilding.)

Consequently, the same schemes that have been invented to enable state-of-the-art LP solvers to be joined with decision strategies for MIP problems are susceptible to being used by M-S procedures. In addition, commercial MIP packages are becoming increasingly accessible to researchers who want to experiment with alternative decision strategies, thus paving the way for linking multi-start methods with these packages

Implementation challenges

The greatest limitation to implementing more general M-S procedures within the setting of current MIP solvers lies in the fact that tools have not been created for these solvers with an eye to flexibly dismantling solutions. This limitation most strongly affects the implementation of strategic oscillation approaches given that current solvers focus chiefly on decisions that involve forward steps, rather than considering the possibility of making “backward step” decisions that would modify sequences previously established in the forward direction. Consequently, M-S strategies for MIP must largely be confined at present to those that generate a forward decision sequence from scratch. Nevertheless, this still leaves room for innovative ideas and implementations that can be expanded as the “hooks” to operations within commercial solvers are made more comprehensive.

As in current multi-start procedures that invoke  improvement methods to take over when the construction phase is completed, these MIP multi-start methods could make provision for a commercial MIP solver to continue exploration for a period after the M-S approach reaches the end of a forward pass (whether or not feasibility has been achieved).

But commercial MIP solvers are not the only option for providing the machinery for such a marriage. Conceivably, a good computer programmer might be able to “get inside” an open source MIP solver to create routines for an M-S method, making it possible to produce strategies that are more versatile than those produced by joining such a method with a commercial MIP code. The resulting software would not be able to compete in efficiency with the commercial solvers, but could be the basis for a proof-of-concept study that examines relative merits of different ways of combining multi-start strategies with current MIP methods.

Issues for Consideration

Several interesting questions arise when contemplating a marriage of multi-start and MIP methods:

• Can an M-S method prove useful in the role of providing a preliminary solution stage to accelerate the convergence of a standard MIP solver?
• To what extent should an MIP solver be employed at the conclusion of a pass of an M-S method to search for enhanced solutions before launching a new pass?
• Can an M-S solver be useful by itself as a means of obtaining good solutions (without seeking to establish convergence to optimality)?
• What types of memory can be useful for M-S strategies associated with memory-based methods such as strategic oscillation and tabu search?

Another interesting question involves the use of metaheuristic improvement approaches to supplement a multi-start procedure for MIP optimization. For example, studies of the GRASP multi-start approach have disclosed that significant improvements often result when the procedure is supplemented by path relinking. It would be an intriguing challenge to see whether current MIP machinery is sufficiently malleable to enable such a supplementary method to be implemented efficiently.

Additional crucial issues will be to determine if the branch-evaluation rules used by an MIP solver can be made available to allow a user to rank different branching decisions for an M-S method like GRASP, or to weight such decisions probabilistically for a method like probabilistic TS. In the case where different types of branch-evaluations are made available, another intriguing challenge will be to devise processes for integrating these evaluations (e.g., by some variant of a “voting” process) as a basis for choosing branches. In some types of M-S approaches – particularly those incorporating strategic oscillation or tabu search – it will be essential to differentiate branches that are forced (conditional upon branches previously made on a given path of a tree) and those that are freely selected. In any event, an initial study need not examine all of these issues. Focusing on a few key questions can yield valuable preliminary insights and set the stage for an ongoing stream of research investigations.

Point of Departure

The following references are suggested as basis for developing ideas that may provide a useful point of departure.

F. Glover (2000) "Multi-Start and Strategic Oscillation Methods - Principles to Exploit Adaptive Memory," Interfaces in Computer Science and Operations Research, M. Laguna and J.L. Gonzales Velarde, Eds., Kluwer, pp. 1-24.

M. Resende, C. Ribeiro, F. Glover and R. Marti (2010) “Scatter Search and Path Relinking: Fundamentals, Advances and Applications,” Handbook of Metaheuristics, M. Gendreau and J-Y. Potvin, eds., Kluwer.

M.G.C. Resende and C.C. Ribeiro (2010) “GRASP: Greedy Randomized Adaptive Search Procedures,” Search Methodologies, 2nd edition, E. Burke and G. Kendall (Eds.), Springer.

F. Glover and J-K. Hao (2011) “The Case for Strategic Oscillation,” Annals of Operations Research, Vol. 183, No. 1, pp. 163-173.

P. Festa and M.G.C. Resende (2011) “Hybridizations of GRASP with path-relinking,” Hybrid Metaheuristics, E-G. Talbi, Editor, Studies in Computational Intelligence, vol. 434, pp. 135-155, 2013, Springer

R. Martí, M.G.C. Resende, and C.C. Ribeiro (2012) “Multi-start methods for combinatorial optimization

Additional sources of useful information can be found in the references cited in these articles.

Winning Reader Contributions - Sex and Metaheuristic Metaphors

Based on reader votes, the winners of the contest for additional Principles for Courtship Algorithms have now been determined. A tally of email responses (together with a few posted on the web) identifies the top three entries to be as follows:

 

---

First Place (a tie):

"Do you have a sister?" (Neighborhood search may pay dividends.)  - Paul Rubin

"Don't do _that_ again ... at least not immediately" (Tabu search)  - Maurice Clerc

Second Place

"Let's go to a bar separately and pretend I'm picking you up..." (Recast a difficult problem into a simpler problem with a more rapid convergence to a satisfactory solution.)  - Frank Grange

---

 

Several readers commented that overall the contributions were very impressive. (As one individual remarked, "I didn’t realize we had so many witty people in the metaheuristics community!")

Each of the three winners is awarded a prize consisting of a National Geographic video titled "Human Footprint" (which is described as being about "what makes up an average human life today and how everything we do has impact on the world about us").

It is clear from the reader responses that Courtship Algorithms is an area of Analytics that warrants closer scrutiny. Perhaps National Geographic will be inspired to create a future video release on this topic to which some of our readers will become contributors.

 

Added Note: For those who are interested, a summary of the contributions is given below. Also included at the end is a late submission which didn’t arrive in time to be in the contest, but which deserves an honorable mention.

Summary of Reader Contributions

---

"Darling, finally, I mean ..." (Termination based on a number of non-improving iterations.)  - Peter Greistorfer

If at first you don’t succeed, try, try again … (Restarting in new areas to find better results.)  - Joshua Snyder

Things are moving too quickly … (Don’t be afraid to be thorough.)  - Joshua Snyder

"Your brains and my beauty" (generate combinations based on different criteria, e.g. rigorous and esthetic, quantitative and qualitative).  - Zbyszek Michalewicz

"Don't do _that_ again ... at least not immediately" (Tabu search)  - Maurice Clerc

May I offer you these flowers? (In case of dynamic or imprecise optimisation: reevaluate)  - Maurice Clerc

"Do you have a sister?" (Neighborhood search may pay dividends.)  - Paul Rubin

"Bring a wingman." (Exploit parallel processing as appropriate.)  - Paul Rubin

"Let's go to a bar separately and pretend I'm picking you up..." (Recast a difficult problem into a simpler problem with a more rapid convergence to a satisfactory solution.)   - Frank Grange

I'm not sure I'm ready for this. (Alternate between intensification and diversification strategies.)   - Kenneth Sorensen

Timing is everything (If you need this explained, you need a lot of help!)  - Suvrajeet Sen

Do you think we should? (Evaluate consequences from more than one perspective.)  - Ann Richmond

"Slow and easy" can be rewarding! (Simulated annealing - slow progress can pave the way for greater gains.)  - Markus Sothby

Some choices are tabu for good reason. Let’s experiment to find which tabu choices shouldn’t be. (Determine good aspirations for overcoming tabus.)  - Enrique Cardenas

Why not? (Be prepared to pursue promising options.)  - Elise Farber

I’m not the kind of person you can easily lead astray. But don’t give up just because things aren’t easy! (Move ahead when there are indications of potential benefit.)  - Gina Villana

Late Contribution: Honorable Mention

"Honey, let’s do that again, our next high will likely be even higher" (don’t settle for a local optimum if you may be close to joining the mile-high club) - Huybert Groenendaal

Sex and Metaheuristic Metaphors – Reader Contributions

A number of readers have provided comments to suggest additional “Principles” for Courtship Algorithms. These comments have added further intriguing refinements to this new class of  metaheuristic strategies.

You are invited to vote on your three favorites. Authors of the three selections that receive the most votes will be awarded a prize.

Each principle below is first stated in the context of human courtship, followed by the corresponding concept expressed as a metaheuristic strategy.

---

"Darling, finally, I mean ..." (Termination based on a number of non-improving iterations.)  - Peter Greistorfer

If at first you don’t succeed, try, try again … (Restarting in new areas to find better results.)  - Joshua Snyder

Things are moving too quickly … (Don’t be afraid to be thorough.)  - Joshua Snyder

"Your brains and my beauty" (generate combinations based on different criteria, e.g. rigorous and esthetic, quantitative and qualitative).  - Zbyszek Michalewicz

"Don't do _that_ again ... at least not immediately" (Tabu search)  - Maurice Clerc

May I offer you these flowers? (In case of dynamic or imprecise optimisation: reevaluate)  - Maurice Clerc

”Do you have a sister?” (Neighborhood search may pay dividends.)  - Paul Rubin

"Bring a wingman." (Exploit parallel processing as appropriate.)  - Paul Rubin

"Let's go to a bar separately and pretend I'm picking you up..." (Recast a difficult problem into a simpler problem with a more rapid convergence to a satisfactory solution.)   - Frank Grange

I'm not sure I'm ready for this. (Alternate between intensification and diversification strategies.)   - Kenneth Sorensen

Timing is everything (If you need this explained, you need a lot of help!)  - Suvrajeet Sen

Do you think we should? (Evaluate consequences from more than one perspective.)  - Ann Richmond

“Slow and easy” can be rewarding! (Simulated annealing - slow progress can pave the way for greater gains.)  - Markus Sothby

Some choices are tabu for good reason. Let’s experiment to find which tabu choices shouldn’t be. (Determine good aspirations for overcoming tabus.)  - Enrique Cardenas

Why not? (Be prepared to pursue promising options.)  - Elise Farber

I’m not the kind of person you can easily lead astray. But don’t give up just because things aren’t easy! (Move ahead when there are indications of potential benefit.)  - Gina Villana

---

Indicate the three selections above that you like best, listing them in the order of your preference, and email them to glover@opttek.com. Your choices will be weighted by giving 5 points to your first choice, 4 points to your second and 3 points to your third. The three selections that receive the most points will be the winners. Please send your choices by January 31, 2012 (and only one vote per person!). Winners will be notified via email and will be announced in a future blog posting.

Sex and Metaheuristic Metaphors

As metaheuristics continue to play an increasingly important role in the field of Analytics, the connection between metaheuristics and Analytics invites closer examination. This leads, improbably but interestingly, to the topic of metaheuristic metaphors and – as I’ll describe in a moment – to the topic of sex.   

To set the stage, it is useful to observe where the link between metaheuristics and Analytics comes from. As noted in other installments of this blog, the Analytics field depends greatly on the domain of optimization for some of its most successful approaches.  And within optimization, the realm of metaheuristics is responsible for some of the most impressive recent advances in solving hard optimization problems, particularly those encountered in real world applications.[i]

Scores of “nature metaphors” for metaheuristics have emerged in recent years, ranging widely from thermodynamics to genetics to zoology to quantum mechanics. Even if such metaphors often appear to be more strongly based on a quest to achieve brand name recognition than to establish useful insights, there has been no inhibition in trying to squeeze metaphorical content out of anything that remotely offers an opportunity. Reflecting on this situation when the proliferation of these metaphors was in its infancy, Manuel Laguna and I couldn’t resist writing.[ii]

Models of nature that are relied upon for inspiration [in creating new metaheuristics] are ubiquitous, and it is easy to conjure up examples whose metaphorical possibilities have not yet been tapped. To take an excursion in the lighter side of such possibilities (though not too far from the lanes currently traveled), we may observe that a beehive offers a notable example of a system that possesses problem solving abilities.  Bees produce hives of exceptional quality and complexity, coordinate diverse tasks among different types of individuals, perform spatial navigation, and communicate via multiple media.  (It is perhaps surprising in retrospect that the behavior of bees has not been selected as a basis for one of the “new” problem solving methods.)

Those who follow the fashions in metaheuristic metaphors know that a number of years after these words were written, metaheuristics have indeed begun to appear that claim to be based on the behavior of bees.

All this spirited activity to come up with catchy new metaphors to promote various metaheuristic proposals, if viewed from the standpoint of overall efficacy, discloses a clear shortcoming. The metaphors currently in vogue, to put it charitably, are decidedly stodgy. More to the point, they lack the power to stir primordial responses within the psyche of their intended audience.

This leads to the main thesis of this current writing. The world of advertising has long taught us that nothing sells like sex, and I would maintain that we should not hesitate to take advantage of this fundamental truth. Admittedly, on a plane that may be appreciated by a circle of academics, there is already a natural candidate for the title of “the sexiest metaheuristic.” Given that all sex is based on genetics, the class of genetic algorithms should unquestionably take top billing. Yet the topic of cavorting chromosomes isn’t the sort of thing that would play well in a commercial slot on prime-time TV. After all, given that the developers and users of metaheuristics are humans, it’s human sex rather than chromosomal sex that is more apt to attract our attention.

In addition, if the goal is to have a metaphor that can be a model for complex problem solving, I suspect a focus on the primitive biological processes such as gene transmission harbors a more telling deficiency. It would be hard to say how smart a chromosome might be when confronted with a task like building a space satellite or a biotech lab, but I’d be willing to bet that humans are better suited to handling these kinds of challenges. If so, why not develop a metaheuristic based on a metaphor of human sex?

More particularly, it would seem worthwhile to focus on the aspect of human sex that most fully draws upon our inherent ingenuity. I refer, of course, to courtship. Throughout the millennia we have generated a rich array of strategies to handle the intricacies of courtship as a means to navigate the tumultuous seas of human relationships as affected by varying social and cultural norms (which we seem to have perversely created to make the process of courtship more difficult).

In short, Courtship Algorithms provide a natural foundation for developing new metaheuristic processes. To inform such processes, it is possible to formulate a collection of Key Strategic Principles, as embodied in time-honored expressions that people have applied to courtship. Below I undertake to show how these expressions translate directly into principles for metaheuristic methods, listing first the classical version of these principles, followed by their associated metaheuristic counterparts in parentheses.

Courtship Algorithms
Key Strategic Principles
Have we met before? (Use memory to exploit recurrences.)
Your place or mine?  (Consider the benefits of regional exploration.)
Variety is spice. (Employ diversification at all levels.)
Would you like to see my etchings? (Decide what is worth exploring.)
Try it, you'll like it. (Experiment and probe beyond the surface.)
Opposites attract.  (Join diversification (via opposites) and intensification (via attraction).)
Familiarity breeds … (Watch for important affinities.)
When in Rome …  (Adapt to the terrain.)
Once is not enough. (Iterate over good options.)
Play the field. (Don’t be restricted to a single move or strategy.)
Are there any more at home like you? (Employ comparative analysis.)
Two’s company, three’s a crowd. (Sometimes paired combinations work well.)
Ménage à trois (And sometimes it can be worthwhile to go beyond pairs.)
The more the merrier. (And then sometimes …)
Am I getting warmer?  (Test the setting to determine the next move.)
Don’t stop now!  (Take advantage of momentum.)
Be gentle.  (But do so prudently.)
What will you think of me in the morning?  (Consider downstream consequences.)
Be prepared. (Initial strategies can set the stage for later ones.)
Let’s compare our …  (Discover advantageous similarities and differences.)
Be selective. (Sift through options.)
Don’t leave things to chance. (Random behavior can sometimes be counterproductive.)
When you’re hot you’re hot. (Launch intensification at propitious moments.)
No need to be timid.  (Well-timed aggressive moves can pay off.)
Go with the moment. (Include short term strategies for congenial terrain.)
Find the sweet spot(s).  (Allow guidance by multiple criteria of attractiveness.)
Trust your instincts.  (Intuitive exploration can supplement strict analysis.)
Go for the prize.  (Don’t get bogged down with trivia.)
We’ve got to stop meeting like this! (Introduce variation to avoid cycling traps.)
The bar is closing. Let’s find someplace more interesting to go!  (Establish limits and follow through with exploration of new terrain.)

Undoubtedly I’ve barely scratched the surface of the potential that resides in the realm of human courtship as a source of new metaheuristic processes. It is tempting to speculate that courtship algorithms may not only offer a useful foundation for future study, but may possibly offer a chance to elevate the area of metaheuristics to new heights. The field of analytics – which benefits from advances in metaheuristics – might then in turn experience significant gains.

Note: The reader is invited to contribute additional Strategic Principles of Courtship Algorithms in their comments. These will be assembled and posted on a subsequent blog where viewers will be able to vote on their favorites and a (sexy) prize will be awarded to the winner.

 

The original version of this material appears as an article in ORMS Today, October 11, 2011, pages 20-21. (See http://www.orms-today.org/.)

---

[i] A comprehensive survey appears in Sorensen, K., and Glover, F.  (in press).  “Metaheuristics,” in  Encyclopedia of Operations Research and Management Science(3e), S. I. Gass and M. C. Fu, eds., Springer, New York.

[ii] From Chapter 1 of Tabu Search by F. Glover and M. Laguna, Kluwer Academic Publishers, 1997.

Third Visit from the Analytics Genie

I was prepared for the genie’s visit this time.

When he stepped out of the mists and touched his turban in greeting, I found myself reacting as I might respond to a familiar gesture of an old friend. Nothing quite compares to the sense of anticipation that results upon confronting a genie to deliver the last of three wishes, and to observe the outcome of having the wishes granted. The genie had made it clear that I must strictly conform to the context of specifying features I would like to have in software for solving analytics problems, and that he was not going to settle for vague or non-specific wishes. 

Ultimately, ambiguities and imprecisions could never be fully escaped, which evidently implied that the job description of a genie involved stepping gingerly through a minefield of linguistic booby-traps.  I was also a bit uneasy about this, because it meant the genie was much better at negotiating such a minefield than I was. Nevertheless, I had to admit that I was enjoying the challenge of formulating the three wishes, and so I proceeded with a mixture of anticipation and wariness.

My first two wishes had been

1. The best possible simulation optimization design.
2. The best possible capability to handle multi-criteria optimization

I had given some thought to what was needed to cap these wishes off, and my reflections led me to recognize another distinguishing characteristic of good simulation optimization methods. Truly effective optimization models and methods require a means of analyzing data for patterns, to create predictions and classifications as a foundation for making intelligent decisions. Consequently, it was clear that a good simulation optimization system had to incorporate a high quality data mining component as a tool for dealing with uncertainty, risk and complexity and that such a component qualified as an indispensible property of the models and methods to be wished for.

I was obviously not alone in reaching these conclusions. Their implications have not been lost on key analysts, leading decision makers, and research professionals. Gartner, a leading provider of technical research and business advice draws similar inferences as evidenced in the following quote:

Optimization and simulation is using analytical tools and models to maximize business process and decision effectiveness by examining alternative outcomes and scenarios, before, during and after process implementation and execution. This can be viewed as a [fundamental] step in supporting operational business decisions. Fixed rules and prepared policies gave way to more informed decisions powered by the right information delivered at the right time, whether through customer relationship management (CRM) or enterprise resource planning (ERP) or other applications. The new step is to provide simulation, prediction, optimization and other analytics, not simply information, to empower even more decision flexibility at the time and place of every business process action. The new step looks into the future, predicting what can or will happen.

At this point I was prepared to list the final feature I most wanted to have in my optimization models and methods:

The best possible data mining procedures to extract key information from the solutions produced.

As I contemplated this final wish, however, I had a sudden and uncomfortable suspicion that I had overlooked something. I reviewed again in my mind the last two provisions of the Fantasy Association for Thwarting Chicanery and Cunning Evasion (FAT CHANCE) that my wishes must conform to:

• No violations of the laws of nature
• No sidestepping of personal responsibility 

Turning to the Analytics Genie, I said “When you require that my wishes must not violate the laws of nature, you mean that I can’t take advantage of technology that doesn’t presently exist. Is that right?”

The Analytics Genie smiled, and nodded.

“And this would imply,” I continued, “that when I ask for the ‘best possible’ instance of something, this must refer to an instance that is already available.”

He nodded again, and I already knew his response to my final question: “And your provision that I can’t sidestep personal responsibility implies that I must not only confine my wishes to things currently available, but I must also be the one responsible for obtaining whatever I wish for?”

The genie responded simply by saying “The process you have gone through to formulate your wishes gives you the foundation for fulfilling these wishes.”

So there it was! The Analytics Genie, living up to the genie reputation for being crafty, had not committed himself to be the agent for delivering on the promise to grant the three wishes, but had contrived so that this agent was to be me. It was never really in the cards that my wishes would be granted by the Fantasy Association known as FAT CHANCE_, or by any other outside agency. Yet perhaps the outcome was not so disappointing at that. The Analytics Genie had cleverly led me to discover what I felt was worth wishing for. And the fact that the realization of my wishes rested on my own pursuit of them was not the worst news I could have had.

Seeing my understanding, the Analytics Genie smiled again, then faded into the mists of the Genie Nether Kingdom from which he had emerged.

Second Visit from the Analytics Genie

The second visit of the Analytics Genie was fully as unexpected as the first.  The sudden appearance of mist billowing out of nowhere in the corner of my study and the image of an imposing figure in a turban materializing within it is not the sort of thing one easily gets used to.

The genie stepped forward, touching his hand to his forehead in greeting – a little less theatrical than the sweeping bow he had executed on his first visit – and addressed me in a tone as if he had only left my presence moments before.  "Have you made progress in choosing your second wish?"

As I struggled to pull my memories back into focus, the genie prodded me by saying "Or would you like to revise your first wish?"

Then it came back to me in a rush.  The Analytics Genie had stipulated that my three wishes were to be about features I wanted to have in my models and methods for analytics problems.  My first wish for such a feature had been

" … a simulation optimization capability with the best possible design."

As I reflected again on the critical elements that analytics models and methods should have, I was led back to my initial realization that an ability to handle uncertainty, risk and complexity was at the top of the list.  And simulation optimization was a pre-eminent candidate for achieving this, by combining the modeling flexibility of simulation with the capacity to uncover high quality decisions for meeting the goals of the model.  The more advanced forms simulation optimization also had the advantage of employing metaheuristic search in addition to classical optimization, making them superior to approaches that only relied on traditional optimization processes.

Still, asking for a "best possible design" of a simulation optimization capability was not enough to fully convey what I really was looking for.  There was immense variability in the quality of simulation optimization methods.  I needed to clarify the factors that define this "quality" by pinpointing the characteristics that lay at the heart of the better methods.

My reflections since the Analytics Genie’s first visit had produced the realization that a conspicuously desirable characteristic of good simulation optimization methods is to go beyond producing a single good solution.  In other words, good methods should generate a strategically varied collection of solutions.  The value of such a collection was apparent in practice.  It was no secret that managers and decision makers are often unable to envision all of the intricacies of the problems they face when they first undertake to formulate them.  The argument I had traced in my reflections went something along the following lines.  A repository of high quality candidate solutions avoids being saddled with a "best" solution that is defective – due to unanticipated limitations in the model and the difficulty of accounting for all relevant problem characteristics.  Instead, when a given solution turns out to have shortcomings, the decision maker can select among repository members that are better suited to practical implementation.  The process of reviewing alternative candidate solutions builds insights that can lead to better models and, in turn, to better solutions.

All well and good, but that still wasn't enough to differentiate "high quality" systems from others.  Another hallmark of good simulation optimization methods is an ability to handle multiple objectives.  Practical problems often occur in a context where the preferred policy is not only to maximize profit or minimize expense, for example, but simultaneously to maximize resource utilization and customer satisfaction, or to minimize idle production or detrimental environmental impact, and so forth.  Tradeoffs typically encountered in these settings render it impossible to find a solution that is best across all relevant criteria simultaneously.  A simulation optimization approach that can effectively handle multiple objectives offers a bonus, not only by accounting for such tradeoffs, but by also giving a platform for responding to uncertainty and risk.  Taking advantage of such an approach assures that the CEO and her team will not wake up the next morning and discover that an unforeseen event has wiped out their capital – as a result of a strategy that was tailored to achieve one goal at the expense of another, or that seemed highly profitable at the moment, but that fell apart when conditions changed.

In fact, the ability to deal with multiple objectives, if done intelligently, will automatically include the feature I had previously singled out as important – the feature of maintaining a repository of strategically generated solutions.  Such solutions can be relevant in a multiple objective setting even if not all of them reside on the efficient frontier of so-called "Pareto optimal" solutions, because the objectives as presently formulated may not encompass all the elements that may emerge as important.

In short, my second wish followed naturally on the first, and I did not need to keep the genie waiting to hear what I had decided.  Again, to avoid the chance of getting something less than I might hope for, it would be preferable to formulate my wish by asking for the "best possible" alternative.  I turned to the Analytics Genie who was patiently awaiting my response and said:

"My second wish for a feature to include in an analytics system is to have the best possible capability to handle multi-criteria optimization."

The genie raised an eyebrow.  But he did not seem dissatisfied, and I chose to interpret his gesture as not so much questioning my second wish as signaling his acknowledgement that it fit with the first.

"I will give you the same opportunity as before," he said. "You have the chance to change your second wish as you go through the process of selecting the third."

I thought I knew what was coming.  But instead of stepping back into the mists, the genie remained in place and the mists came to him.  As they enveloped him and he began to fade from view, he flashed a curious smile in my direction.  Something about his expression gave me the distinct impression he had not told me everything.  I resolved that the next time I saw him I would ask more questions and try to piece together more fully what was going on.

First Visit from the Analytics Genie

Long holding the conviction that genies were creatures of myth and fantasy, I was caught by surprise the other day while working in my study to notice a bluish haze rising from an unseen source in the corner and a figure in a turban materializing within it. Before I had a chance to gather my wits and make an attempt to recover my composure, the figure stepped forward, gave a sweeping bow, and introduced himself as the Analytics Genie. Taking no note of my incredulous state, he announced that the purpose of his visit was to offer me the chance to make three wishes.

Apparently he had access to sources of Secret Genie Information (e.g., the internet) because he assured me he knew of my special interest in practical applications in analytics, and stipulated my wishes should be about features I wanted to have incorporated in methods and models for solving real world analytics problems.

But there were to be a few additional conditions in the bargain. The Analytics Genie made no effort to hide that he was a creature of fantasy, and indeed seemed rather proud of the fact, but he was also evidently accustomed to encountering humans who would try to gain unwarranted concessions from those of his kind. As a result of this, he told me, he was obliged to additionally stipulate that the wishes must conform to the following provisions endorsed by the Fantasy Association for Thwarting Chicanery and Cunning Evasion (FAT CHANCE):

• No iterative or recursive expressions (no wishes asking for more wishes)
• No embedded lists (no wishes with compound conditions)
• No violations of the laws of nature (no wishes for salt shakers or zippers that work properly) 
• No sidestepping of personal responsibility  (no wishes my first grade teacher or maternal grandmother wouldn’t approve of)

I was pleased to see that this list wasn’t riddled with auxiliary clauses, as I suspected a similar document prepared by the legal staff of a human organization might be. At first glance, wishes that satisfied these provisions seemed to be easy to come by.  Immediate examples that sprung to my mind were to select features that would:

Make lots of money

Bring about greater economic and social welfare

Save the environment

Eradicate armed conflict

Eliminate poverty and disease

Protect the world from the political, economic and social policies advocated by my sister-in-law.

The Analytics Genie pointed out, however, that these were consequences of features I might hope to specify, as opposed to the features that create such consequences. I was urged to reflect on the situation a little more thoroughly.

All right, then, what could I formulate that would make good sense? Within the context of practical problem-solving the Analytics Genie had specified, I most certainly wanted to identify features that would permit such problems to be treated intelligently and competently. To have a chance of pulling this off, I required answers to a couple of questions. First, what essential component of real world problems creates the need for handling them better than current approaches are doing? Second, what are the characteristics of such problems that must be exploited if we are to do a more creditable job of solving them?

I might be able to respond to these questions by basing my wishes on “the standard line” everyone knows, that we should have models and methods that are easy to use and that exhibit supporting features such as visualization aids and interactive decision making. But a little reflection made it apparent that these features, desirable as they might be, were in reality secondary. Features that ranked highest in importance were those that made it possible to handle the “terrible triple” of uncertainty, risk and complexity. Without such an ability, there isn’t much hope that our models and methods will have significant value in the real world.

The challenges that arise in business, government and science notoriously create a need for better approaches for dealing with uncertainty, risk and complexity. Applications ranging from health care to energy to bioinformatics all exhibit one or more of these underlying factors.

So how to translate this recognition into wishes about features to embody in analytics models and methods? To answer this compelled me to take a step back and consider the nature of these models and methods that would accomplish the goals I was seeking.

First, to have a model that embraces the diverse forms of uncertainty encountered in the real world (and not just the forms treated by classical mathematical models, which are notoriously handicapped by an array of limiting assumptions) it is essential to take advantage of the modeling flexibility provided by simulation. Through its capacity to capture complex interactions and to evaluate the effects of multiple scenarios on system performance, simulation offers an essential tool for decision-makers who want to build models for practical problem solving. Second, to be able to produce high quality solutions from the model – going beyond the all-too-common practice of “playing with” the model by trial and error guesses about values for decision variables – it is necessary to bring optimization into the picture. To be able to work with a simulation model, however, requires a highly protean type of approach, which can deal with contexts where the formulation consists of more than a set of equations and inequalities that can be written down on a piece of paper. An approach is needed that is robust over the myriads of changing scenarios generated by a simulation, and beyond this, capable of handling stochastic components such as expected values, variance and percentiles.

Evidently, the answer involves a special type of marriage between simulation and optimization, the sort of marriage practitioners in the simulation industry have called simulation optimization. This term is a bit misleading, because it doesn’t refer to optimizing the structure of a simulation process, but to using simulation as a modeling tool which is integrated with an optimization approach having the ability to find high quality solutions within the complex space generated by the simulation.

Those who have been observers of the area know well that a virtual upheaval has been taking place in recent years, as researchers and practitioners have united in an effort to overcome the limitations of approaches available in the early beginnings of the simulation optimization field. Although remarkable progress has been made, observers are also aware that large differences still remain in the scope and efficacy of the approaches developed. The existence of such differences between different simulation optimization systems led me to conclude there was no sense in squandering a wish on something that fell short of being the best of its kind. With this in mind, I faced the genie and expressed my first wish.

“I wish the first feature to have in my analytics system to be a simulation optimization capability with the best possible design.”

The Analytics Genie nodded, thoughtfully rubbing the well-trimmed tuft of a beard on his chin. “Acknowledged. But I am going to do you the favor of letting you formulate all of your wishes before I grant them, should you decide to change any of them once you’ve chosen them all.” I was surprised by this gesture, which the stories I’d read suggested was very uncharacteristic for a genie, but I accepted his offer. “In that case, he concluded, I have other business to attend to – my services as an Analytics Genie are in high demand these days, as I’m sure you can appreciate – but after settling these matters I will return to learn your other two wishes.”

Waving his arm ceremoniously, the Analytics Genie gave a sweeping bow as he had on first presenting himself, and slipped back into the encircling mist to vanish from sight.

Although a little unsettled by this behavior, which I suspected marked my visitor as rather unconventional even among the unpredictable beings that populated the genie kingdom, I was happy to be given the extra time to contemplate the nature of my other two wishes. What other features did I want in my optimization models and methods, from the perspective of solving practical analytics problems? I resolved to reflect on this question and be prepared for the genie’s return, whenever that might be.

(Readers are invited to offer their suggestions and advice about good choices for these remaining wishes to convey to the Analytics Genie!)