Solver Foundation 2.0 Preview: Simulation and Stochastic Programming

  • Article

I'm back from ISMP and helping to put the finishing touches on Solver Foundation 2.0.  In our first version we introduced: our declarative modeling language OML; Solver Foundation Services, which provides a powerful, consistent .Net API for modeling and solving a wide range of decision problems; a set of solvers for linear, quadratic, mixed integer, constraint, and unconstrained nonlinear programming; third-party solver plug-in support; and an Excel add-in that provides easy access to all of Solver Foundation's functionality through Office 2007.  Our aim in version 2.0 is to make it easier for non-experts to model and solve problems, and to expand the range of problems that can be solved using Solver Foundation.  I will spend the next few posts talking about our plans for 2.0.

Many real-world problems involve uncertainty.  For example, task durations, sales estimates, rate of return, and so on. Simulation and/or stochastic programming techniques are often used to account for randomness, but applying such techniques can often be quite tricky.  In Solver Foundation 2.0 we are adding OML, Solver Foundation Services and solver support for linear stochastic models.  The two new modeling concepts are:

  • Random parameters are used to model randomness.  They can be discrete or continuous.  They can be used where (non-random) parameters or constants would normally be used in constraints.
    • A special type of random parameter is a Scenarios parameter.  In this case a list of scenarios are given where each scenario contains a value and a probability.  For example, to model weather we might have a "rainy" scenario, a "normal" scenario, and a "dry" scenario.
  • Recourse decisions are decisions that are made in response to the realization of a random parameter.  For example, if the weather turns out to be dry, we may not be able to produce enough of a certain crop and may need to purchase it from someone else.  In this case, the purchase amount is a recourse decision.  Recourse decisions are sometimes called "second-stage" decision because such decisions can be made only after the randomness is resolved.    

As you will see in a moment, if you know how to build regular models using OML, building models with random parameters and recourse decisions will be no problem.  Solver Foundation Services will contain new APIs that allow for stochastic modeling using random parameters and recourse decisions.  Indexed random parameters and data binding will be fully supported.  We will support the following distributions in V2:

  • Continuous: Normal (Gaussian), Uniform, Exponential, Log normal, Scenario-based.
  • Discrete: Uniform, Geometric, Binomial

Here is a simple OML example.  It is a simple production planning problem with scalar input (here is a non-stochastic sample in C#).  We introduce recourse decisions that represent the amount of pre-refined product to buy, in case demand cannot be met by production.  The demand for each product is random; the demand for gas is modeled using two scenarios of equal probability, the others are uniformly distributed.  Not very realistic, but I wanted to cram all the new concepts in a short model!  Indexed random parameters are of course possible.  In that case you will be able to use data binding to define the parameters associated with the distributions - keeping a clean separation between data and model, and allowing for easy experimentation. 

Model[
Decisions[Reals[0, Infinity], SaudiArabia, Venezuela],
Decisions[Reals[0, Infinity],
// To define a recourse decision, just wrap Recourse[] around it.
Recourse[GasBuy], Recourse[JetFuelBuy], Recourse[LubricantBuy]
],

Parameters[
// Here is a scenario-based random parameter with two scenarios of equal probability.
Scenarios[Reals[0, Infinity]],
GasDemand = {{0.5, 1900}, {0.5, 2100}}
],

// Here is a continuous random parameter.
Parameters[UniformDistribution[1500, 1600], JetFuelDemand],
Parameters[UniformDistribution[400, 500], LubricantDemand],

Goals[
Minimize[ goal -> 20 * SaudiArabia+ 15 * Venezuela + (38.4 * GasBuy + 35.2 * JetFuelBuy + 28.8 * LubricantBuy) ]
],

Constraints[
0.3 * SaudiArabia + 0.4 * Venezuela + GasBuy >= GasDemand,
0.4 * SaudiArabia + 0.2 * Venezuela + JetFuelBuy >= JetFuelDemand,
0.2 * SaudiArabia + 0.3 * Venezuela+ LubricantBuy >= LubricantDemand,
SaudiArabia <= 9000,
Venezuela <= 6000
]
]

The modeling constructs are simple, but underneath the hood there is a lot going on:

  • Solver Foundation Services supports different sampling methods including Monte Carlo and Latin Hypercube.  Going beyond simple Monte Carlo often leads to better results in less time.  
  • Large problems can be solved efficiently using Benders decomposition. 
  • Solver Foundation Services will have API support for tuning the behavior of the stochastic solver. 
  • Our primary focus is on providing a satisfactory experience “out-of-the-box”, without having to resort to lots of tuning.