次の方法で共有

Solver Foundation 2.0 Preview: Simulation and Stochastic Programming

  • [アーティクル]

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.

Comments

  • Anonymous
    September 07, 2009
    Hello Nathan, That's very exciting! Could you recommend an introduction book on stochastic programming, with emphasis on applications ? Thanks a lot.

  • Anonymous
    September 22, 2009
    Yes this is very exciting ! A good book on Stochastic programming is: Introduction to Stochastic Programming (Springer Series in Operations Research and Financial Engineering) (Hardcover) by John R. Birge  and John R. Birge (Author). Hardcover: 448 pages Publisher: Springer; Corrected edition (February 2, 2000) Language: English ISBN-10: 0387982175 Cheers

  • Anonymous
    October 07, 2009
    Hi Nathan! Could you advise, does/will the Solver Foundation API provide a possibility to solve the minimization problem of a 'user-defined' function ? 'User-defined' means a smooth function, which is defined inside my C# code as a simple C# routine like: public static double f(double x, double y, ...) {   return result of some complex formula here; Smooth, of course! } I read up the Solver Foundation Constraint Programming (CSP) API v1.2 documentation and cann't find out how to make such a 'user' function definition. Only via the 'Function Terms'...but it seems they give not enough flexibility to describe an arbitrary complex smooth function. Or could you advise, where I can find information about this ? Thanks in advance

  • Anonymous
    October 07, 2009
    Hi Anton, Yes, Solver Foundation does support minimization of a 'user defined' function so long as there are no constraints.  Solver Foundation has a Compact Quasi Newton (CQN) solver - it is not exposed through Solver Foundation Services, but you can write code against the solver directly.  You will also need to provide the gradient values in addition to 'f'.  More info, including a link to a sample here: http://code.msdn.microsoft.com/solverfoundation/Thread/View.aspx?ThreadId=2309 Nathan

  • Anonymous
    February 12, 2010
    Hi Nathan, How can I use the error function in OML/MSF? Something as the errorf funtion in GAMS. Thank you!

  • Anonymous
    February 14, 2010
    Sorry to say that OML does not currently support the errorf/erf function.  It's something we're considering for a future release - but it probably won't happen in the next few months.

  • Anonymous
    April 27, 2010
    The comment has been removed

  • Anonymous
    April 27, 2010
    Hi Nathan, I found the solution myself:            StochasticDirective d = new StochasticDirective();            d.DecompositionType = DecompositionType.Enabled;            Solution solution = context.Solve(d); Only the criterias which influence the decision on the DecompositionType when set to "Auto" I could not find in any documentation. Maybe you can help me out with that, thank you! Lars