Backgrounder on Robust Optimization, Stochastic Programming, and Simulation Optimization
Contact: Dan Fylstra
Simulation for risk analysis, and optimization for resource allocation are two powerful and commonly used analytical methods for business decision-making in leading companies. For the most part, they have been separate technical disciplines, with different software products leading in each category. But the common feature of most high-stakes business decisions is the need to allocate scarce resources under conditions of uncertainty and risk. How can modern software technology best meet this need?
Using Simulation Optimization
For a number of years, software for simulation optimization has partially addressed this need. In Microsoft Excel, the leading products are Decisioneering's Crystal Ball Professional with its OptQuest optimizer, Palisade's @RISK Industrial with its Evolver/RiskOptimizer, and Frontline Systems' Premium Solver V7.0 + Risk Solver V7.0 combination, which offers by far the fastest performance in simulation optimization - often 10 to 100 times faster than its competitors. However, simulation optimization has been slow, even on modern PCs, and even on relatively small problems involving tens to hundreds of decision variables and uncertain parameters. Often such applications are left to run overnight or over a weekend. The resource allocation problems faced by large enterprises have been difficult and expensive to solve, often requiring teams of experts, big development budgets, and months to years of calendar time. Solving large-scale optimization problems with uncertainty in Microsoft Excel has been unthinkable... until now.
Premium Solver Platform V8.0 Stochastic Edition, together with Risk Solver V8.0, offers breakthrough capabilities for analyzing and solving decision models that must allocate scarce resources in the presence of uncertainty. It finds optimal solutions in a fraction of a second for some models where Crystal Ball and @RISK take minutes to find an approximate solution. It can define and solve problems with 'wait and see' or recourse decisions, that can't be expressed, let alone solved, with the other products. And it can optimize models with uncertainty that have thousands, or (with plug-in Solver Engines) tens or hundreds of thousands of decision variables and constraints - unthinkable for the other products, but very doable for the Stochastic Edition. Premium Solver Platform Stochastic Edition achieves these remarkable results because it has the unique ability to analyze and transform the formulas in a Microsoft Excel model - using PSI Technology, its Polymorphic Spreadsheet Interpreter.
For models with the required structure, it can apply robust optimization and stochastic programming methods to solve the problem. For models that truly require the most general methods, it uses simulation optimization, again using PSI Technology for vectorized evaluation of simulation trials at the fastest possible speed.
Analyzing Model Structure is Key
The strength and weakness of simulation optimization is that it assumes almost nothing about the structure of the model to be optimized: Uncertain parameters may depend on decision variables, and the objective and constraints may be non-linear, non-convex or non-smooth functions of the variables. With these assumptions, simulation optimization does the best it can: Each time the optimizer proposes different values for the decision variables, a new simulation is performed to evaluate the objective and constraints. No 'rate-of-change' information is available for the problem functions, so many thousands of trial values may be needed - and for each set of trial values, a thousand or more simulation trials may be needed. In some applications, the optimization model is truly a 'black box' with no discoverable structure for the problem, and simulation optimization is the best choice.
In Microsoft Excel, Frontline's products offer by far the highest performance simulation optimization to date. But optimization models defined through Excel formulas are a 'black box' only to Frontline's competitors, whose software has no ability to analyze the model. For them, simulation optimization is the only available method, and "when your only tool is a hammer, every problem looks like a nail."
For years, both Crystal Ball and @RISK software have included example models, such as a Project Selection model and a Portfolio Mix model, that were intended to illustrate the power of simulation optimization. But when the structure of these models is analyzed, it turns out that they don't need simulation optimization at all: They are actually simple linear programming models, where the linear coefficients must be computed through sampling - by performing a single Monte Carlo simulation. Frontline's Premium Solver Platform Stochastic Edition solves these models in a fraction of a second - 100 to 1,000 times faster than the other products.
Stochastic Programming and Robust Optimization
In addition to its high performance simulation optimization capabilities, Premium Solver Platform Stochastic Edition implements two other technologies: stochastic programming and robust optimization. Frontline has drawn on the research literature, and on its own optimization expertise to advance the state of the art for these methods. Stochastic programming has a rich history dating back almost 50 years to George Dantzig (the "father of linear programming"), Beale, Charnes and Cooper, and others. Robust optimization methods are much more recent, with most research in the past ten years. While applications of stochastic programming have been reported over many years in the technical literature, and a number of applications of robust optimization have appeared recently, nearly all of these have been labor-intensive individual projects. Few software systems outside Excel, and none inside Excel, have implemented these methods prior to the Premium Solver Platform Stochastic Edition.
To the best of Frontline's knowledge, no other general-purpose commercial software has implemented robust optimization methods. These powerful methods, which are scalable to handle the problems faced by large enterprises, are not only available for the first time - they are easy to use in Premium Solver Platform Stochastic Edition.
Recourse Variables Yield Better Models and Decisions
A key modeling concept that is present in stochastic programming and robust optimization, but absent in simulation optimization (and completely missing from competitive products such as Crystal Ball and @RISK) is the ability to define 'wait and see' or recourse decision variables.In many problems with uncertainty, the uncertainty will be resolved at some known time in the future. For example, next year's interest rates and next month's rainfall are uncertain today, but they will be known with certainty in the future. Normal decision variables in a model represent decisions that must be made 'here and now,' before the uncertainty is resolved.
Recourse variables represent decisions that can be made on a 'wait and see' basis, after the uncertainty is resolved. Both kinds of decisions are included in a stochastic (i.e. uncertain) optimization problem with recourse. The recourse decisions, also called second stage decisions, are used to 'fine tune' the solution represented by the normal or first stage decisions, based on the specific outcome of the uncertain parameters in each future scenario. Simulation optimization - which was designed for situations where the uncertainty is ongoing or never resolved - has no concept of recourse decisions. Simulation optimization is also designed to support decision-dependent uncertainties, which would make recourse decisions much harder to evaluate. For these kinds of problems, simulation optimization is the method of choice.
But - partly because of available software that only supports simulation optimization - this method has often been applied in situations where the uncertainty will be resolved in the near future. In many such situations, recourse decisions can be made - and this gives the decision-maker flexibility that frequently yields better solutions, with higher profits, lower costs or risk, and the like. Modelers using simulation optimization in these cases are often solving the wrong problem. Premium Solver Platform Stochastic Edition offers a far better choice.
Making the Power Easy to Use
In the past, defining optimization models with uncertain parameters, chance constraints, and recourse decisions, and using methods such as stochastic programming and robust optimization has been the province of experts. In fact, most PhDs in operations research and management science have only heard of these methods, but have not used them to solve practical problems.All this has changed with Premium Solver Platform Stochastic Edition. Models with all these features can be defined easily and quickly in Excel, through an extended Solver Parameters dialog that will be familiar to anyone who has used the built-in Excel Solver. In fact, a user can start with an Excel Solver model, which is accepted automatically by the Stochastic Edition, and add uncertain parameters, chance constraints, and/or recourse decisions to it.
Uncertainties can be defined with a few point-and-click steps, in a manner fully compatible with Frontline's Risk Solver software - so conventional risk analysis can be performed at any time with such a model. Further, the Stochastic Edition can analyze the user's Excel model, and automatically determine whether it can be solved via stochastic programming or robust optimization methods, or will require simulation optimization methods. If the user intended to create (say) a stochastic linear programming model, but made a mistake in some Excel formula, for example by creating a non-linear dependency or a decision-dependent uncertainty, the Stochastic Edition can automatically diagnose the model and point out the specific formula where the mistake was made.
The result is that methods that were once the province of experts have become accessible to smart business users, who are willing to learn by watching the videos, reading online Help or the User Guide, and trying out the examples supplied with Premium Solver Platform Stochastic Edition. And this means that the business decisions where analytical support may have the greatest payoff - allocating scarce resources under conditions of uncertainty and risk - can be tackled by 'mere mortals' with real-world budgets and time constraints. Frontline Systems, which has seen its users achieve spectacular ROIs with its software many times before, expects to see even greater benefits in 2008 with Premium Solver Platform Stochastic Edition.
About Frontline Systems, Inc.
Frontline Systems, Inc. (www.solver.com) is a leading developer of optimization and simulation software, and the leader in spreadsheet optimization software that helps analysts and managers optimally allocate scarce resources - money, equipment, and people - to realize substantial cost savings. Frontline developed the solvers/optimizers in Microsoft Excel, Lotus 1-2-3 and Quattro Pro, distributed to more than 500 million spreadsheet users. Founded in 1987, Frontline is headquartered in Incline Village, Nevada (775-831-0300 or firstname.lastname@example.org).
Premium Solver and Risk Solver are trademarks of Frontline Systems, Inc. Crystal Ball is a registered trademark of Decisioneering, Inc. @RISK, while not a registered trademark, is the name of the popular risk analysis product from Palisade Corp.