River Logic Blog | Prescriptive Analytics Blog

A Code Free Approach to Stochastic Programming

Written by Eric Kelso | Sep 16, 2015

 

The first post covered a specific list of eleven software requirements necessary for stochastic optimization. This post covers stochastic programming; industries and business applications it is used for; and why a simpler, code-free approach is best for non-technical users.

Stochastic Programming vs. Stochastic Optimization

You might be wondering: "what’s the difference between stochastic optimization and stochastic programming? Isn’t the former just the application of the later?" Yes and no. Although stochastic optimization and programming are very similar — and sometimes used interchangeably — I’m treating them as separate subjects for discussion purposes.

Stochastic optimization

As the definition above describes, stochastic optimization is incorporating randomness into an otherwise deterministic problem formulation, be it prices, costs, rates, yields, limits, etc. The random values are always defined using a probabilistic distribution and generated prior to solving the model.

Stochastic programming

Stochastic programming certainly has that aspect too, but the applications and implications extend far beyond just randomly generating a new price or limit within some known range. It's more broadly thought of as a modeling approach (or framework) that is used to describe a series of one or more inter-connected future decisions.

In stochastic programming, sometimes it’s not enough to just model sales prices using a Normal distribution with a standard deviation. Instead, it’s used to model an entire set of future decisions that depend directly on decisions made in earlier periods. Each set of decisions made in future periods can be thought of as in a different stage.

What is Stochastic Programming?

Stochastic programming can be more difficult to grasp than just optimization using Monte Carlo simulation, but the basic premise is fairly simple. Imagine you are walking down a hallway and there are three doors from which to choose (1, 2 and 3). You must select and open one, and only one, door now. Any door you choose will lead you down a completely different path, but it is not strictly a one-way trip. Once the decision is made, there may potentially be recourse options available to you to overcome a bad decision (i.e., choosing the wrong door). This is stochastic programming in a nutshell.

Most non-academic literature describing stochastic programming follows this general sequence:

    • The author first describes the multi-stage linear programs in general using some mathematical notation (e.g., Σ);
    • Then he “backtracks” to discuss an example of a relatively simple two-stage model;
    • Then he (frequently) admits that a single large linear programming problem is often used.

The reason for this progression is pretty simple; most practitioners have neither the time nor the patience to create pure multi-stage stochastic models with recourse. It means creating a model with execution code that goes something like this: solve stage A, input some solution value into stage B. Solve stage B, then use some recourse value to alter stage A. Solve stage A again, then input into stage B again, and so on ...

As you can imagine, stochastic programming at this level can be very difficult to model!

So don’t fixate on trying to model a multi-stage stochastic programming problem in its purest sense unless a) you know what you are doing; b) you have the software to enable you to do this; and c) you have a lot of time to work on it. I might also add d) unless you have a very understanding boss who is not going to get mad that you took a lot longer to model it (if even possible) than you said you would in the first place.

Further down, I briefly discuss an alternative approach that works for most business users.

Where are the published Case Studies?

There exists a relatively small group of mostly academics plus a few practitioners called the Stochastic Programming Society who have dedicated their careers to solving stochastic programming problems. They claim membership from a variety of industries or subject areas known to have need for stochastic programming including airlines, agriculture, capacity planning, energy, finance, forestry, military, telecommunications, transportation and water management.

Based on this industry list, you would assume there must be available case studies. But Googling “stochastic programming”, as I have, you will notice that there’s not a lot in the public domain beyond academia. Actual, real-life published examples tend to be quite small. The reason for this is obvious:

Companies that have built stochastic programming models don't want to talk about it — it's become a huge competitive advantage!

The Traditional Modeling Approach

As a product manager, it's my job to know my company’s competition in the optimization platform market. Earlier this year, I spent time analyzing an example of a competitor’s approach to a two-stage stochastic problem. I never could fully understand the reason for every single line of code, but I will say it appeared quite complicated and likely required someone experienced with a Masters or PhD in Operations Research or Computer Science. I just cannot comprehend how the typical early career consultant with an MBA is going to create something like that, even with some help.

Think of it this way … imagine a past experience building an optimization model, maybe using a 3rd- or 4th-generation algebraic modeling language, or even a complex Excel workbook. Then, on top of the basic model, imagine a requirement to write as much (or possibly more) code just to control the following: a) how the stochastic data is defined; b) the interaction between the multiple stages; c) the recourse steps; and d) how the entire model is executed. This is the “traditional” approach.

The limitations of traditional modeling approaches 

There is a reason why there are very few commercial modeling packages on the market intended for stochastic programming — and it’s not due to a lack of need or interest. Rather, stochastic programming using traditional tools is hard, difficult to grasp and takes a long time to implement. Again, this is why there are so few real-life published examples of multi-stage stochastic programming models. Modelers who are somehow successful at this have created real competitive value for their company or their clients. Everyone else is left struggling to figure how to do it.

A Visual, Data-Driven Approach

There is a simpler, better approach. There exists today fifth-generation modeling software that consist of four simple steps:

  1. Models are built by dragging-and-dropping icons from a pallet to a diagram
  2. Icons are linked together to form some process or financial flow logic
  3. Objects are customized as needed to accurately describe the problem
  4. Data is imported into the model from nearly any common data source once the model is built

5GL modeling packages outrank traditional approaches

Importantly, 5GL modeling packages allow the user to incorporate stochastic programming elements with built-in features (primarily Boolean decisions) that control flow “gates”, control higher level attribute constraints, and enable other advanced modeling features. These modeling features allow for decisions in earlier periods to affect, even trigger, decisions in later periods. And, they can be extremely difficult and time-consuming to code from scratch into 3rd- and 4th-generation modeling tools.

Instead of worrying about whether a model is one, two or multi-stage, it makes far more sense to just focus on the business problem at hand. What decisions need to be made? When do they need to be made? What are the implications and downstream effects when they are made? What time horizon do they need to be made over? By focusing on the business issue, and not the mechanics of how the stochastic programming model should be defined, it frees the modeler from having to abide by someone else’s set of rules.

One simple approach is to add binary or integer decisions in the model that can trigger some action in a later period (i.e. stage).  A simple example would be a long-range planning model with an M&A decision.  Based on values of certain stochastic random variables, like sales prices, it might or might not trigger the M&A purchase decision.

Modelers can do more with 5GL modeling packages

In a package like River Logic’s Enterprise Optimizer, the modeler can then run a Monte Carlo simulation and iterate over as many solves as necessary, each time saving the Seed Value and any other important metrics like objective function.  At the end of the batch run, they can then search through the objective function values (or other metrics), select the best result, reset the Seed Value, re-solve the model one last time and then export to some database.  (Or, they could save all the runs and export everything to a database.) This may or may not quite meet the Stochastic Programming Society’s definition of stochastic programming, but it is very easy to implement and places no restrictions on model size or complexity. 

Other process modeling examples include facility open/close decisions, resource buy/sell or deterioration and refurbishment/replacement decisions. Financial modeling examples include considering a bond or stock offering, or buying back bonds, and the long-term financial implications.

Final Thoughts

Stochastic programming can play an important and influential role in a company’s strategic planning process.

Well-defined stochastic models allow for a complex depth of scenario analysis that the human mind cannot comprehend.

The cascading effects of a decision in one time period and how future decisions are made can be captured by using appropriate software and techniques, but technology matters. Basing stochastic models on traditional approaches will allow for complete control over problem definition but will likely result in code that few people will ever understand. A visual modeling approach might not meet the definition of a society’s view of stochastic programming, but it will let the modeler, his customers, and other interested parties see the model and results and run what-if scenarios quickly and effectively.