Simulation Programming

Solver Foundation 3.0

You can simulate real-world problems by introducing randomness into a model. Solver Foundation supports two-stage linear stochastic models, also known as stochastic models, which contain first-stage decisions, second-stage decisions, and random parameters. The first-stage decisions must be determined without knowledge of the random parameters, and the second-stage decisions are computed after the values of the random parameters are known. These stochastic models can more accurately solve models such as finance, manufacturing planning, energy planning, sales estimates, project task durations, or rates of return.

To create stochastic models, you can incorporate random parameters, which represent randomness in input data, and recourse decisions or second-stage decisions, which are decisions made in response to the realization of a random parameter. Random parameters are used to model randomness in input data, and you can assign several different distributions. Discrete or continuous distributions can be used wherever non-random parameters or constants would normally be used in constraints. Examples of distributions include uniform, normal, and log normal. A special type of random parameter is a scenario-based parameter, where each scenario consists of a value and a probability. For example, to model weather we may have "rainy", "normal", and "dry" scenarios.

After calculating the possible values of a parameter, the solution to a model can be adjusted with recourse decisions in goals or constraints, which are known as second stage constraints.

Distribution-Based Models

You can fit distributions such as a normal bell-shaped curve to a model by using the RandomParameter class. These distributions are defined by its center (the mean) and its width (the standard deviation). You can define a gas demand random parameter with a mean value of 1900 and a standard deviation of 50 by using the following code.

RandomParameter gasDemand = new NormalDistributionParameter("r", 1900, 50);

If the number of products in the model, you can use indexed decisions and parameters.

Set products = new Set(Domain.Any, "Products");
UniformDistributionParameter demand = new UniformDistributionParameter("demand", products);
RecourseDecision buy = new RecourseDecision(Domain.RealNonnegative, "buy", products);

If you are using indexed parameters, you can also use the SetBinding<T>(IEnumerable<T>, String, String) or SetBinding<T>(IEnumerable<T>, String, String, String[]) methods to bind data to arguments of indexed parameters.

Set products = new Set(Domain.Any, "Products");
UniformDistributionParameter demand = new UniformDistributionParameter("demand", products);
List<UniformInfo> uniformInfo = GetUniformInfo();
demand.SetBinding(uniformInfo.Where(u => u.Enabled), "Lower", "Upper", "Product");

Scenario-Based Models

You can configure scenario-based stochastic problems by using the ScenariosParameter class. Each scenario defines a possible value for the random parameter and the probability of occurrence. You can define a gas demand scenario parameter where it is equally likely that the demand is for 1950 or 2050 barrels.

RandomParameter gasDemand = new ScenariosParameter("GasDemand", new Scenario[] { new Scenario(0.5, 1950), new Scenario(0.5, 2050) });

Use the SetBinding<T>(IEnumerable<T>, String, String) or SetBinding<T>(IEnumerable<T>, String, String, String[]) methods to bind data from an external source to a scenario parameter.

ScenariosParameter gasDemand = new ScenariosParameter("GasDemand");
var scenarios = new Scenario[] {new Scenario(0.5, 1950), new Scenario(0.5, 2050) };
gasDemand.SetBinding(scenarios, "Probability", "Value");

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 crop and may need to purchase it from an external supplier. In this case, the purchase amount is a recourse decision. Recourse decisions are sometimes called "second-stage" because such decisions can be made only after the randomness is resolved. The non-recourse decisions are called "first-stage" decisions, for example the number of acres devoted to each type of crop.

If the range of values for a random parameter is small, a stochastic model can consider all the values when solving a model. However, if the distribution of values is large or there are many scenarios to consider, the solver can use two different sampling techniques.

You can adjust the sampling behavior by configuring the SamplingParameters property.

The number of samples and choice of sampling engine can affect the solution time and quality. Microsoft Solver Foundation uses decomposition techniques to solve large-scale models with many samples efficiently by using less memory. If you are using Solver Foundation Services, the SFS layer has default settings for sampling and decomposition options in different models, but you can also adjust the settings to suit varying needs.

The sample count can be set to a specific value or left at its default value of -1. The default value means that Solver Foundation Services choose the sample count based on the problem. In general, a higher sample count makes sense when there are many random parameters in the model. Also remember that some models do not require sampling at all: for example if a model contains a small number of scenario parameters.

Solver Foundation uses the Mersenne Twister algorithm to generate random numbers.

Monte Carlo

Monte Carlo sampling draws completely independent and random samples throughout the distribution or scenario in the model. You can change the sample count or sampling method as demonstrated in the following code.

  SolverContext context = SolverContext.GetContext();
  context.SamplingParameters.SampleCount = 50;
  context.SamplingParameters.SamplingMethod = SamplingMethod.MonteCarlo;

Latin Hypercube

Latin Hypercube sampling divides the distribution into slices and draws random samples from each slice. The number of slices depends on a sample count. For example, for a uniform distribution with bounds [0, 50] if the sample count is 100 then a Latin Hypercube sampler will draw samples from [0, 0.5), [0.5, 1.0), [1.0, 1.5), etc. For many large models, the Latin Hypercube method leads to better results.

The first part of the report contains information on how the problem was solved. The solution type indicates if sampling was used to solve the model. Some problems, such as scenario-based problems, do not necessarily require sampling. The sampling method is either Monte Carlo or Latin Hypercube (the default). The solution method is either "Deterministic Equivalent", which considers all scenarios at once, or "Decomposition", which computes each scenario separately. The deterministic equivalent solution method involves considering all scenarios at once, whereas decomposition deals with each scenario individually.

The second part of the report contains statistics that provide additional insight about the problem. EV stands for the value of the goal for the expected value model. In the expected value model, all random parameters have been replaced with their expected values (or "averages"). For example, a uniform distribution parameter is replaced by the average of lower and upper bounds, and a normal distribution parameter is replaced by its mean.

The VSS, or Value of Stochastic Solution, is a measure of the worth of using a stochastic (rather than a deterministic) model. The VSS is the difference between the goal value for the stochastic problem, and the average goal value over all scenarios when the non-recourse decisions are fixed to their values in the expected value problem. If this difference is small, then that indicates that using the solution of the expected value problem will likely lead to a "pretty good" solution to the stochastic problem. In other words, the randomness does not play a very significant role. This is not the same as saying that the amount of randomness in the problem is "small".

EVPI is the Expected Value of Perfect Information. Informally, it is a measure of the value of perfect forecasting: the actual values of the random parameters depend on future events. Another way to interpret EVPI is the amount the modeler would be willing to pay for perfect information: in this case the exact demand for gas, jet fuel, and lubricant.

Stochastic Measures:
Stochastic Solution Type: Sampled
Sampling Method: LatinHypercube
Sample Count: 500
Solving Method: Deterministic Equivalent
EV: 90500
VSS: 337.87275173275
EVPI: 778.560392168525
===Solution Details===
goal: 91278.2763528171

The sampling engine is controlled using a SolverContext object, and you can customize the stochastic model by using the StochasticDirective class. The following code creates a stochastic directive and specifies the decomposition solution method.

StochasticDirective directive = new StochasticDirective();
  directive.DecompositionType = DecompositionType.Enabled;

In general, for smaller models with only a few scenarios, the deterministic equivalent method requires less time to solve than the decomposition method. For larger models, the decomposition method consumes less memory. If the DecompositionType property set to its default value of Automatic, the simplex solver can choose whether to use the deterministic equivalent or decomposition method.