Module 10: Stochastic Optimization

So far in this course, we have focused on “conventional optimization,” in which all the parameters are assumed to be numbers known with certainty.  In almost all business problems, this is a simplification of the actual real world situation: typically there is at least some uncertainty in the values of the parameters in an optimization model. In other words, as opposed to a certain parameter which has a single, known value, we can think of an uncertain parameter as having many possible values.  We call each such value a realization of the uncertainty.

In some models, the uncertainty or variation in the parameters may be small enough to be ignored, or it may be sufficient to address it using the sensitivity reports or parametric analysis covered earlier in this course.  However, in some business cases the uncertainty is so large that it is a major feature of the problem, and thus it is important to incorporate the uncertainty directly into the model.

In many real-world problems, the uncertainties being modeled are independent of the decision variables.  For example, in a crop planning model where the acres to plant of different crops are decision variables, and the rainfall in a future period is an uncertainty, the uncertainty is independent of the decisions (i.e. the rainfall is not dependent on how much of each crop is planted).  Stochastic optimization is the perfect tool for these problems.

In other real-world problems, the uncertain parameters being modeled are dependent on the decision variables – they change if the decisions change.  For example, in a market response model that includes competitor actions in a future period, where your product prices are decision variables, and your competitors’ product prices are uncertainties, it is quite likely that the uncertainties will depend on the decisions.  As described in the next section, stochastic optimization cannot be used in the presence of decision-dependent uncertainties.  Instead, another feature of Analytic Solver Platform, called simulation optimization, must be used.

In some real-world problems, we are uncertain about the value of a parameter today, and we will remain uncertain about its value in the future; we have to make decisions in the presence of this uncertainty.  In other real-world problems, we are uncertain about the value of a parameter today, but we will know its value with certainty at some point in the future.  In such cases, we might be able to make some decisions ‘here and now,’ before the uncertainty becomes known, while other decisions can be made on a ‘wait and see’ basis, after the uncertainty is known.  Such models require the use of recourse decisions, which are included with Analytic Solver Platform but are outside the scope of this course.

We’ll now describe all the elements of a Solver model with uncertainty.  Again, our goal is to find a solution – values for the decision variables in our model – that satisfies the constraints and that maxi­mizes or minimizes the objective.  In computing the objective and constraints, we may use many parameters – some of which are computed from uncertain variables.

Uncertain Variables

A certain parameter is easy to model, in a worksheet cell containing a number.  To model an uncertain parameter, we must have a way to specify the range and ‘shape’ of the values it can assume.  In Analytic Solver Platform, we model uncertain variables in worksheet cells that contain special ‘Psi’ functions, which can be added to the model using ASP’s ‘Distributions’ menu.  For example:

=PsiUniform(0,1) – a uniform distribution ranging from 0 to 1

=PsiNormal(2,1.5) – a Normal distribution with mean 2, standard deviation 1.5

=PsiBeta(A1,B1) – a Beta distribution with shape parameters given in worksheet cells A1 and B1

You can think of the cell for an uncertain variable as holding an array of sample values, with each value being one possible realization of the uncertainty.  Analytic Solver Platform can generate such an array of sample values automatically.  For example, the cell D5 might contain the formula =PsiUniform(0,1).  If your objective or constraint depends on D5 (e.g. C8 = 100+80*D5), it must also compute an array of sample values.  Each value corresponds to one possible realization of all the uncertainties on which the formula depends.

In the example function PsiBeta(A1,B1), it is important to know whether A1 or B1 is dependent on the decision variables.  A model that includes such a decision-dependent uncertainty is much harder to solve, and will require the methods of simulation optimization, which is included with Analytic Solver Platform but is outside the scope of this course.  Analytic Solver Platform can automatically diagnose your model and determine whether any uncertain variables depend – possibly through a chain of formula cells – on the decision variables.

The Objective Function

If the objective function of a model depends on uncertainties, we must specify how we want to ‘optimize’ this function.  The most common practice is to maximize or minimize the expected value of the objective, over all realizations of the uncertainties.  In Analytic Solver Platform, you do this by selecting Expected instead of Normal when specifying the objective function.

Constraints:  Normal and Chance

When your model includes uncertainty, we must examine how each constraint depends on the uncertainties and the decision variables:

• If a constraint depends only on certain parameters and normal decision variables, it is ‘deterministic’ and is handled in the usual way by the Solver.  We call this a normal constraint.
• If a constraint depends on uncertain variables and normal decision variables, we must specify what it means for the constraint to be satisfied.  There are many possible realizations for the uncertain variables, but only single values for the decision variables.  The Solver must find values for the decision variables that cause the constraint to be satisfied for all, or perhaps most but not all, realiza­tions of the uncertainties.  We call this a chance constraint.  For example, we might specify that the constraint must be satisfied 95% or 99% of the time, i.e. it can be violated 5% or 1% of the time. This can be done by choosing the ‘Chance Constraint’ option as opposed to the ‘Normal Constraint’ option when specifying the model constraints. Note: the relation of the constraint must be either <= or >=.  A chance constraint cannot be an equality.

In the above example, the criterion that it must be satisfied for all realizations of the uncertainties up to a given percentile (say 95%) makes it a VaR (Value at Risk) constraint. Analytic Solver Platform supports two other criteria besides VaR – Conditional Value at Risk (CVaR), and Uncertainty Set (USet).  These are available as options when you add a chance constraint, and in certain cases they might be a better choice for your model – you can find more details on each in the ASP User Guide.  In particular, CVaR is often preferred since it is more conservative than VaR, and unlike VaR it will not compromise model convexity.

Optimal Solution: Stochastic vs. Conventional Models

The optimal solution to a stochastic model will often be (quite) different from the optimal solution to a problem where all uncertain variables are replaced with their nominal or average values.  The latter optimization will exploit the ‘point values’ of the parameters, with no consideration for their variability; this will often yield a better objective value for the nominal problem, but the solution may not be feasible, let alone optimal, for many different realizations of the uncertain variables.  Compared to the ‘nominal’ solution, the stochastic solution is more robust or ‘well-hedged’ against possible variations in the uncertain variables.