Microsoft Solver Foundation

Simulation Programming Primer

This documentation is provided to you for informational purposes only. MICROSOFT MAKES NO WARRANTIES, EXPRESS,
IMPLIED OR STATUTORY, AS TO THE INFORMATION IN THIS DOCUMENT.

Complying with all applicable copyright laws is the responsibility of the user. Without limiting the rights under copyright,
no part of this document may be reproduced, stored in or introduced into a retrieval system, or transmitted in any form
or by any means (electronic, mechanical, photocopying, recording, or otherwise), or for any purpose, without the express
written permission of Microsoft Corporation.

Microsoft may have patents, patent applications, trademarks, copyrights, or other intellectual property rights covering
subject matter in this document. Except as expressly provided in any written license agreement from Microsoft, the
furnishing of this document does not give you any license to these patents, trademarks, copyrights, or other intellectual
property.

© Microsoft Corporation. All rights reserved.

Microsoft and Excel are registered trademarks or trademarks of Microsoft Corporation in the United States and/or other
countries.

© 2006-2011 Microsoft Corporation

Table of contents
Table of contents .......................................................................................................................................... 2
Introduction .................................................................................................................................................. 3
Solution approach ..................................................................................................................................... 3
Creating stochastic models ........................................................................................................................... 4
Creating distribution-based models ......................................................................................................... 5
Creating scenario-based models............................................................................................................... 7
Random parameters, sets, and data binding ............................................................................................ 7
Controlling the sampling engine ............................................................................................................... 8
Stochastic solution measures ................................................................................................................... 9
Customization using StochasticDirective .................................................................................................... 10
Appendices.................................................................................................................................................. 11
Appendix 1: API Overview....................................................................................................................... 11
Appendix 2: API Methods ....................................................................................................................... 12

2 © 2006-2011 Microsoft Corporation

Introduction
Many real-world problems involve uncertainty: sales estimates, project task durations, rates of return,
and so on. Accounting for this uncertainty results in models that more accurately reflect reality, and
their solutions are more likely to be useful over a wider range of situations. Simulation and stochastic
programming techniques are often used to account for randomness, but applying such techniques can
often be tricky and error-prone. Solver Foundation provides modeling, solver, and reporting tools that
support the solution of two-stage linear stochastic models, the most commonly used stochastic model
type. These new extensions complement the existing Solver Foundation platform, making them both
powerful and easy to use. This document describes how to build, solve, and analyze stochastic models
using Solver Foundation Services. For an OML reference, consult the Excel Programming Primer.

Modeling is extended in two important ways. Random parameters are used to model randomness in
input data. Solver Foundation supports a wide range of commonly used random distributions. They can
be discrete or continuous, and 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.

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.

Solution approach
The Solver Foundation Services programming APIs and declarative modeling language OML have been
extended so that random parameters and recourse decisions are easily expressed. Here’s a brief sketch
of how Solver Foundation Services handles the complexities of solving stochastic models.

Solver Foundation can solve linear, two-stage stochastic models. Stochastic simply means that the
model contains random parameters. Linear means that the goals and constraints are linear in the
decisions. Two-stage means that there are two kinds of decisions: first stage decisions that must be
determined without specific knowledge of the random parameter values; and second stage decisions
that are determined after the values of random parameters are known. Solving a two-stage stochastic
model means finding values for first and second stage values that optimize the expected value of the
goal over the range of possible values for random parameters.

If the range of possible values is small then it is possible to consider all of them when solving a model.
However, models that contain continuous distributions (or a large number of scenarios) are best solved
using sampling techniques. Solver Foundation Services uses sampling engines to draw representative
samples from all of the random parameters that appear in a model. The Monte Carlo sampling engine

3 © 2006-2011 Microsoft Corporation

draws completely independent random samples, whereas the Latin Hypercube engine divides the
distributions into pieces and draws random samples from each piece. The number of samples and the
choice of sampling engine can affect the solution time and quality. Large models that require many
samples can lead to very challenging problems. Solver Foundation is able to use advanced
decomposition techniques to solve large-scale models more efficiently and with less memory.

Solver Foundation Services takes care of setting sampling and decomposition options that are
appropriate for the model at hand. However, advanced users may wish to tune these settings to suit
their particular needs. The Customization section describes these options in detail.

Creating stochastic models

In this primer we assume you are familiar with basic SFS programming as described in the Solver
Foundation Services Programming Primer. Stochastic models are made up of the same building blocks as
other Solver Foundation models. Parameters are input values that represent problem data. Decisions
are output values that are determined by the solver. Decisions and parameters can be single valued, or
indexed over sets. All decisions and parameters have domains that determine the range of possible
values. A goal combines parameters, decisions, and constant values to express how the model is to be
optimized. Constraints are expressions that restrict decision values. A stochastic model contains two
special types of constructs: random parameters and recourse decisions.

Let’s start with a simple non-stochastic model, and then add random parameters and recourse
decisions. The following C# code models a production planning problem. A company has refineries in
two locations that refine crude oil into three different products: gas, jet fuel, and lubricant. Each refinery
has a total capacity and different production yields for each product. A few lines of C# code allow us to
create and solve the SFS model for this problem:

private static void Petrochem() {

SolverContext context = [Link]();
[Link]();
Model model = [Link]();

Decision sa = new Decision([Link](0, 9000), "SA");

Decision vz = new Decision([Link](0, 6000), "VZ");
[Link](sa, vz);

[Link]("goal", [Link], 20 * sa + 15 * vz);

[Link]("demand1", 0.3 * sa + 0.4 * vz >= 1900);

[Link]("demand2", 0.4 * sa + 0.2 * vz >= 1500);
[Link]("demand3", 0.2 * sa + 0.3 * vz >= 500);

Solution solution = [Link](new SimplexDirective());

Report report = [Link]();
[Link](report);
}

Here is the output for the program:

4 © 2006-2011 Microsoft Corporation

===Solver Foundation Service Report===
Datetime: 09/03/2009 21:28:00
Model Name: Default
Capabilities Requested: LP
Solve Time (ms): 376
Total Time (ms): 848
Solve Completion Status: Optimal
Solver Selected: [Link]
Directives:
Simplex(TimeLimit = -1, MaximumGoalCount = -1, Arithmetic = Default, Pricing =
Default, IterationLimit = -1, Algorithm = Default, Basis = Default, GetSensitivity =
False)
Algorithm: Primal
Arithmetic: Double
Variables: 2 -> 2 + 4
Rows: 4 -> 4
Nonzeros: 8
Eliminated Slack Variables: 0
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 3
Phase 1 Pivots: 3 + 0
Phase 2 Pivots: 0 + 0
Factorings: 4 + 0
Degenerate Pivots: 0 (0.00 %)
Branches: 0
===Solution Details===
Goals:
goal: 90500

Decisions:
SA: 2200
VZ: 3100

Creating distribution-based models

This problem may be more realistically modeled by considering the fact that the demand is not generally
known in advance. We will replace the right-hand sides of the constraints with random parameters. A
random parameter corresponds to either a probability distribution or to a set of scenarios. In this case,
let us assume that the demand fits a bell-shaped (normal) distribution. The shape of a normal
distribution is defined by its center (the mean), and its width (the standard deviation). These are
provided as arguments to the NormalDistributionParameter constructor, for example:

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

The mean value for the parameter is 1900 and the standard deviation is 50. Random parameters can be
used in goals or constraints in the same way as other parameters.

Injecting uncertainty, while useful from a modeling perspective, may also introduce complications.
Depending on the actual values of the random parameters, we may need to take additional action to
compensate. For example, in a project schedule if a milestone takes longer than expected to complete,
it may be necessary to delay other tasks. To handle such situations it is useful to introduce recourse

5 © 2006-2011 Microsoft Corporation

decisions – decisions whose values are determined after the values of random parameters are known.
Recourse decisions are defined the same way as decisions: provide a domain, a name, and an optional
list of index sets. Recourse decisions can then be used in goals or constraints. Constraints that contain
recourse decisions form so-called second stage constraints. There are multiple copies of the constraint,
one for each scenario induced by the values of random parameters that appear in the constraints. When
a recourse decision appears in a goal, it will evaluate to the expected value of the recourse decision over
all possible scenarios. Now we can build a stochastic model where the demands are normally
distributed, and where there is the option to purchase pre-refined product if the demand cannot be met
by the refineries.

private static void PetrochemStochastic() {

SolverContext context = [Link]();
[Link]();
Model model = [Link]();

Decision sa = new Decision([Link](0, 9000), "SA");

Decision vz = new Decision([Link](0, 6000), "VZ");
RecourseDecision gasBuy = new RecourseDecision([Link],
"GasBuy");
RecourseDecision jetFuelBuy = new
RecourseDecision([Link], "JetFuelBuy");
RecourseDecision lubricantBuy = new
RecourseDecision([Link], "LubricantBuy");
[Link](sa, vz);
[Link](gasBuy, jetFuelBuy, lubricantBuy);

[Link]("goal", [Link], 20 * sa + 15 * vz + (38.4 *

gasBuy + 35.2 * jetFuelBuy + 28.8 * lubricantBuy));

RandomParameter gasDemand = new NormalDistributionParameter("GasDemand",

1900, 50);
RandomParameter jetFuelDemand = new
NormalDistributionParameter("JetFuelDemand", 1500, 25);
RandomParameter lubricantDemand = new
NormalDistributionParameter("LubricantDemand", 500, 5);
[Link](gasDemand, jetFuelDemand, lubricantDemand);
[Link]("demand1", 0.3 * sa + 0.4 * vz + gasBuy >=
gasDemand);
[Link]("demand2", 0.4 * sa + 0.2 * vz + jetFuelBuy >=
jetFuelDemand);
[Link]("demand3", 0.2 * sa + 0.3 * vz + lubricantBuy >=
lubricantDemand);

Solution solution = [Link](new SimplexDirective());

Report report = [Link]();
[Link](report);
}

The solution report contains the values for our decisions SA and VZ, as well as the values of the recourse
decisions. Recourse decisions depend on the realization of the random parameters – so in reality each
recourse decision has one value for each scenario. Therefore the report contains the expected value

6 © 2006-2011 Microsoft Corporation

(average) value, as well as the minimum and maximum value over all scenarios. The minimum and
maximum give a sense for the sensitivity of recourse decisions over random parameter values.

Decisions:
SA: 1946.84420002793
VZ: 3283.42813347508

Second stage decisions (Average [Min, Max]):

GasBuy: 21.2452621622179 [0, 149.380352124129]
JetFuelBuy: 64.6065989517969 [0, 142.14750924475]
LubricantBuy: 0 [0, 0]

Creating scenario-based models

Solver Foundation supports several real and integer distributions. A complete list is given in the API
reference. Additionally, SolverFoundation supports scenario-based stochastic problems using the
ScenariosParameter class. A ScenariosParameter is associated with an underlying set of Scenario
objects. Each Scenario defines a possible value for the random parameter along with the probability of
the scenario actually occurring. In the code snippet below, the demand for gas is either 1950 or 2050
with equal probability:

RandomParameter gasDemand = new ScenariosParameter("GasDemand",

new Scenario[] { new Scenario(0.5, 1950), new Scenario(0.5, 2050) });
RandomParameter jetFuelDemand = new ScenariosParameter("JetFuelDemand",
new Scenario[] { new Scenario(0.7, 1500), new Scenario(0.1, 1400),
new Scenario(0.2, 1550) });
RandomParameter lubricantDemand = new ScenariosParameter("LubricDemand",
new Scenario[] { new Scenario(0.3, 475), new Scenario(0.4, 490),
new Scenario(0.3, 525) });

Random parameters, sets, and data binding

Random parameters can be indexed by Sets. If the number of products grows larger it makes sense to
change our model to use indexed decisions and parameters:

Set products = new Set([Link], "Products");

UniformDistributionParameter demand =
new UniformDistributionParameter("demand", products);
RecourseDecision buy = new RecourseDecision([Link],
"buy", products);

It is often useful to define the arguments of a distribution (or the scenarios of a scenario-based
parameter) using data binding. Each random parameter type has a SetBinding method that can be used
to data bind to an external data source. A simple example using ScenariosParameter is as follows. The
demand for gas will be either 1950 or 2050, with equal probability.

ScenariosParameter gasDemand = new ScenariosParameter("GasDemand");

var scenarios = new Scenario[] {
new Scenario(0.5, 1950), new Scenario(0.5, 2050) };
[Link](scenarios, "Probability", "Value");

7 © 2006-2011 Microsoft Corporation

If we have defined a UniformInfo class with Product, Enabled, Lower, and Upper properties, we can bind
the arguments of an indexed random parameter as follows:

Set products = new Set([Link], "Products");

UniformDistributionParameter demand =
new UniformDistributionParameter("demand", products);
List<UniformInfo> uniformInfo = GetUniformInfo();
[Link]([Link](u => [Link]),
"Lower", "Upper", "Product");

Controlling the sampling engine

Solver Foundation Services provides sampling engines to draw representative samples from all of the
random parameters that appear in a model. Sampling behavior is changed by setting properties on
[Link]. The sampling behavior is defined by the choice of sampling method,
and number of samples. Solver Foundation currently supports two sampling methods: Monte Carlo and
Latin Hypercube. Monte Carlo sampling repeatedly draws completely independent samples from each
distribution or scenario that appears in the model. Latin Hypercube engine divides the distributions 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), and so on. For many models,
the Latin Hypercube method leads to better results when solving large models. No matter the sampling
method or distributions used, Solver Foundation uses a random number generator based on the
Mersenne Twister algorithm.

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 will 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 only ScenarioParameters
with a small number of scenarios.

The following sample code changes the number of samples and the sampling engine:

SolverContext context = [Link]();

[Link] = 50;
[Link] = [Link];

These settings apply for all models that require sampling.

8 © 2006-2011 Microsoft Corporation

Stochastic solution measures
The solution report contains additional information particular to stochastic models. The stochastic
measures section appears at the bottom of the report. Here is the report for our example:

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===
Goals:
goal: 91278.2763528171

The first part of the report contains information on how the problem was solved. The solution type
indicates whether sampling was used. 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” or “Decomposition”. The
deterministic equivalent solution method involves considering all scenarios at once, whereas
decomposition deals with each scenario individually. Solver Foundation determines the solution method
automatically by default; see the Customization section to learn how to change it.

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.

9 © 2006-2011 Microsoft Corporation

Customization using StochasticDirective
While the sampling engine is controlled using SolverContext, the means used to solve a stochastic model
can be customized using StochasticDirective class. In general, stochastic problems can be solved in two
ways: either by forming a problem that considers all possible scenarios at once (the “deterministic
equivalent”), or by iteratively considering subsets of possible scenarios (“decomposition”). The following
code creates a StochasticDirective and specifies the decomposition solution method:

StochasticDirective directive = new StochasticDirective();

[Link] = [Link];
[Link](directive);

Solver Foundation 2.0 and 3.0 supported both the deterministic equivalent and decomposition. In Solver
Foundation 3.1 although the DecompositionType can be set, the deterministic equivalent will always be
used to solve the stochastic model. In a future release decomposition may be reintroduced. Recall that if
the model requires sampling, the number of scenarios depends on the number of samples. Determining
the best choice for a given model can be difficult, so leaving the DecompositionType set to its default
value of Automatic is often a good idea.

Whether the deterministic equivalent or decomposition model is employed, the underlying linear
programming problems are solved using the Solver Foundation Simplex solver. Plug-in solvers are not
supported at this time.

10 © 2006-2011 Microsoft Corporation

Appendices

Appendix 1: API Overview

11 © 2006-2011 Microsoft Corporation

Appendix 2: API Methods
The Solver Foundation Services APIs related to stochastic models are described below.
// A group of terms that take stochastic values.
public abstract class RandomParameter : Term, IDataBindable, IIndexable {

// The name of the parameter.

public string Name { get; }

// A description.
public string Description { get; }
}

The RandomParameter base class is used to model randomness in input data. Random parameters can
be discrete or continuous, and can be used where (non-random) Parameters or constants would
normally be used in Constraints. RandomParameter is the base class for a number of commonly used
distributions including uniform, normal, and log normal. A special type of random parameter is a
ScenariosParameter, where each scenario contains a value and a probability.

// A parameter representing a fixed, finite number of discrete scenarios.

public sealed class ScenariosParameter : RandomParameter

A ScenariosParameter is associated with an underlying set of Scenario objects. Each Scenario defines a
possible value for the random parameter along with the probability of the scenario actually occurring.
The sum of probabilities over all scenarios equals 1.0.

// A normal (Gaussian) distribution parameter.

public sealed class NormalDistributionParameter : RandomParameter

A normal distribution is a bell-shaped continuous random distribution. The distribution is defined by its
mean value and its standard distribution. The distribution is symmetric about the mean value. Normal
distributions are sometimes defined using the variance rather than standard deviation - the variance is
the square of the standard deviation.

// A continuous uniformly distributed random parameter.

public class UniformDistributionParameter : RandomParameter

A uniform distribution is a continuous random distribution defined by an upper and lower bound. The
values within the (closed) interval occur with equal probability. The upper and lower bounds must be
finite.

// A discrete uniformly distributed random parameter.

public sealed class DiscreteUniformDistributionParameter :
UniformDistributionParameter

A discrete uniform distribution is defined by an upper and lower bound. The integer values within the
(closed) interval occur with equal probability. The upper and lower bounds must be finite.

// A random parameter with exponential distribution.

public sealed class ExponentialDistributionParameter : RandomParameter

12 © 2006-2011 Microsoft Corporation

An exponential distribution is a continuous random distribution defined by a rate parameter. The
distribution describes a Poisson process where independent events occur continuously at that rate.

// A random parameter with geometric distribution.

public sealed class GeometricDistributionParameter : RandomParameter

A geometric distribution is a discrete random distribution defined by a success probability parameter.

The distribution describes a process where independent Bernoulli trials are taken with the given success
probability.

// A binomial distribution parameter.

public sealed class BinomialDistributionParameter : RandomParameter

A binomial distribution is a discrete random distribution defined by a success probability parameter. The
distribution represents the number of successes in a sequence of trials with the given success rate.

// A log normal distribution parameter.

public sealed class LogNormalDistributionParameter : RandomParameter

A log normal random parameter is a continuous random parameter where the log of the parameter is
normally distributed. The distribution is defined by the natural log of its mean value and standard
distribution.

// RecourseDecisions are Decisions that are made in response to the

// realization of a RandomParameter.
public sealed class RecourseDecision : Term, IIndexable, IDataBindable {
// Create a new non-indexed recourse decision.
public RecourseDecision(Domain domain, String name);

// Create a new indexed recourse decision. The recourse decision may be

// single-valued (scalar), or multi-valued (a table). To create a
// single-valued decision, pass in a zero-length indexSets array.
// If indexSets has nonzero length, each element of it represents a set
// of values which this decision is indexed by. For example, if there
// are two index sets, then this decision takes two indexes, one from
// the first set and one from the second set.
// The total number of decisions is the product of the sizes of all the
// index sets.
// <param name="domain">The set of values each element of the decision
// can take, such as [Link]</param>
// <param name="name">A name for the decision. The name must be unique.
// If the value is null, a unique name will be generated.</param>
// <param name="indexSets">The index sets to use. Omit to create a
// scalar decision.</param>
public RecourseDecision(Domain domain, String name,
params Set[] indexSets);
}

13 © 2006-2011 Microsoft Corporation

RecourseDecisions are Decisions that are made in response to the realization of a RandomParameter.
Recourse decisions are sometimes called "second-stage" because such decisions can be made only after
the randomness is resolved. Each RecourseDecision has an underlying Decision for each second stage
problem. For example: the weather may be modeled as a ScenariosParameter. 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.

// Random sampling parameters for the SolverContext.

public sealed class SamplingParameters {
// How many samples should be taken. Use 0 for automatic mode (Default).
public int SampleCount { get; set; }

// Sampling method: Monte Carlo or Latin Hypercube.

public SamplingMethod SamplingMethod { get; set; }

// Initial seed for the random number generator.

public int RandomSeed { get; set; }
}

Sampling parameters are controlled using the SamplingParameters property on the SolverContext .
Sampling parameters apply to all models created using the SolverContext. Stochastic options are set
using the StochasticDirective class (see below).

// Controls stochastic solution settings.

public class StochasticDirective : Directive {
// Whether to use decomposition or the deterministic equivalent.
public DecompositionType DecompositionType { get; set; }
}

// Decomposition type. Whether to use decomposition.

public enum DecompositionType {
// Let the solver decide whether to use decomposition.
Automatic,

// Do not use decomposition. Form the deterministic equivalent instead.

Disabled,

// Use decomposition.
Enabled
}

The behavior of the stochastic solver is modified by passing in a StochasticDirective to

[Link](). The DecompositionType property is described in more detail in the Customization
section.

14 © 2006-2011 Microsoft Corporation