Difficulty: Intermediate to Advanced | Prerequisites: Docs 1 and 2 of these study notes (Statistical/ML Models and Classification of Optimisation Models).
Up to this point, all the optimisation models assumed we know the data perfectly. In reality, demand forecasts are uncertain, costs fluctuate and parameters are estimated with error. Stochastic optimisation addresses this by building uncertainty directly into the model. This section also introduces dynamic programming, a fundamentally different model structure where decisions unfold over time through a sequence of states, and closes with the basic mechanics of how optimisation algorithms work under the hood.
When data is uncertain, you can either pad your constraints conservatively, model multiple scenarios explicitly, or optimise the expected cost across scenarios. Dynamic programs model sequential decisions through states and choices, using Bellman's equation to find the optimal path. Most optimisation algorithms work by starting with a solution and iteratively improving it in a chosen direction until it converges.
Stochastic optimisation
Optimisation under uncertainty, where some parameters or data are not known exactly. In simple terms, it is optimisation when you do not have perfect information.
Conservative modelling
Adding a buffer (theta) to constraints to account for uncertainty. For example, requiring the number of workers to exceed expected demand plus theta. Think of it as building in a safety margin.
Scenario modelling
Defining several plausible situations (scenarios) and optimising across all of them simultaneously. In simple terms, instead of planning for one future, you plan for several.
Robust solution
A solution that performs adequately across all modelled scenarios, even if it is not optimal for any single one. Think of it as the plan that does not break no matter what happens.
Expected cost optimisation
Optimising the weighted average cost across scenarios, where each scenario is weighted by its probability. In simple terms, you minimise what you expect to pay on average.
Dynamic program (DP)
A model where the system moves through a sequence of states. At each state, a decision is made, and the next state follows from that decision. The structure is fundamentally different from mathematical programming because it is sequential.
Bellman's equation
The recursive equation that expresses the optimal value at each state in terms of the optimal value at the next state. It is the tool that makes dynamic programming tractable by breaking a multi-stage problem into a sequence of one-stage problems.
Stochastic dynamic program
A dynamic program where the transition to the next state involves probability. The decision includes the likelihood of each possible next state.
Markov decision process (MDP)
A stochastic dynamic program with discrete states and discrete decisions, where the transition probabilities depend only on the current state and the current decision, not on any earlier history. Think of it as a stochastic DP with no memory of the past.
Improving direction
In an optimisation algorithm, the direction t in which the current solution should move to reduce (or increase) the objective function value.
Step size
The distance (theta) the algorithm moves along the improving direction in each iteration. Too large and the algorithm overshoots; too small and convergence is slow.
When parameters are uncertain, three main strategies are available.
Add a buffer to the constraints. If you are scheduling workers to meet demand, instead of constraining workers >= expected demand, constrain workers >= expected demand + theta. The extra theta provides a cushion for days when demand is higher than forecast.
This is the simplest approach. The trade-off is clear: a larger theta means more protection against uncertainty but also higher cost (more workers than strictly needed on an average day).
Define multiple scenarios, each representing a plausible future with its own parameter values and constraints. Then find the solution that works across all of them.
For example, a call centre might model four scenarios: a minor recurring bug, several bugs, major bugs and a catastrophic outage. The robust solution staffs enough workers to handle all four.
The challenge: as the number of scenarios grows, the model grows proportionally. Each scenario adds its own set of constraints. This can become computationally expensive very quickly, and a heuristic may be needed.
Instead of insisting the solution works for every scenario, minimise the expected (probability-weighted average) cost across scenarios. This accepts that some scenarios may have shortfalls, but optimises the average outcome.
This is less conservative than the robust approach but may leave you exposed to worst-case scenarios.
Mathematical programming models (LPs, IPs, etc.) have variables, constraints and an objective function. Dynamic programs have a different structure entirely: states, decisions and transitions.
The system exists in a state that describes the current situation and its value. At each state, the decision-maker chooses an action. That action determines the next state. Bellman's equation provides the recursive relationship that identifies the optimal decision at each state by working backwards from the final state.
The key insight: a complex multi-stage problem is decomposed into a sequence of simpler one-stage problems. Each stage asks: given where I am now, what is the best thing to do?
The same structure as a deterministic dynamic program, but the transition to the next state is probabilistic. After a decision is made, the next state is determined by a probability distribution rather than being known with certainty.
An MDP is a stochastic dynamic program with two additional properties:
States and decisions are discrete
Transition probabilities depend only on the current state and the current decision (the Markov property: no memory of past states)
The Markov property is what makes MDPs tractable. Because the future depends only on where you are now and what you do now, you do not need to track the full history of decisions.
Regardless of the specific method, most optimisation algorithms follow the same general pattern.
Start: create an initial solution. This can be simple, poor, or even infeasible.
Iterate:
Find an improving direction t (the direction in which the objective improves)
Choose a step size theta
Update: new solution = old solution + theta * t
Stop: when the solution changes very little between iterations, or when time runs out.
The quality of the algorithm depends on how it selects the improving direction and the step size. Gradient-based methods use the derivative of the objective function to find the direction of steepest descent (or ascent). The step size balances speed of convergence against the risk of overshooting the optimum.
For convex problems, this iterative process is guaranteed to find the global optimum. For non-convex problems, it may converge to a local optimum instead.
Students often think conservative modelling and scenario modelling are the same thing. Conservative modelling adds a single buffer to constraints. Scenario modelling defines multiple distinct futures and optimises across all of them. They are different strategies with different trade-offs.
Students sometimes believe a robust solution is the same as the optimal solution. A robust solution is optimal in the sense that it performs well across all scenarios, but it is typically not optimal for any individual scenario.
Students confuse dynamic programs with dynamic programming (the algorithmic technique from computer science). In this context, a dynamic program is a specific model structure with states, decisions and transitions. The algorithmic technique is related but broader.
Students often assume the Markov property means the process is memoryless in general. The Markov property means the transition probabilities depend only on the current state and decision, not on the full history. The state itself can encode relevant history.
⚠️ Be able to describe all three stochastic optimisation approaches (conservative, scenario, expected cost) and explain when each is appropriate.
⚠️ Understand the structure of a dynamic program (states, decisions, transitions) and how it differs from a mathematical programming model (variables, constraints, objective).
⚠️ Know what Bellman's equation does conceptually, even if you are not asked to derive it: it breaks a multi-stage problem into one-stage subproblems.
⚠️ Be able to define an MDP and state the Markov property in your own words.
⚠️ Know the three steps of a general optimisation algorithm (initialise, iterate with direction and step size, stop on convergence).
⚠️ Understand why scenario modelling can become computationally expensive and when a heuristic may be needed.
Fill in the blank: Adding a buffer theta to a constraint is an example of ______ modelling. (conservative)
True or false: A robust solution is always the cheapest solution. (False: it is the solution that works across all scenarios, which typically costs more than the cheapest single-scenario solution.)
Fill in the blank: In a dynamic program, the optimal decision at each state is found using ______ equation. (Bellman's)
True or false: In a Markov decision process, transition probabilities can depend on decisions made three states ago. (False: the Markov property means they depend only on the current state and current decision.)
Fill in the blank: In the iterative optimisation algorithm, the update rule is: new solution = old solution + ______ * t. (step size / theta)
Q: Explain the difference between conservative modelling and scenario modelling for handling uncertainty.
A: Conservative modelling adds a single buffer (theta) to constraints to provide a safety margin against uncertainty. Scenario modelling defines multiple distinct possible futures and finds a solution that works across all of them. Conservative modelling is simpler but less nuanced; scenario modelling captures more detail but is computationally heavier.
Q: What is a robust solution and how does it differ from an optimal solution for a single scenario?
A: A robust solution performs adequately across all modelled scenarios. It may not be optimal for any single scenario because it must satisfy every scenario's constraints. A single-scenario optimal solution is the best possible for that one case but may fail under other conditions.
Q: Describe the structure of a dynamic program and explain how Bellman's equation helps solve it.
A: A dynamic program divides the system into states, where each state has a value and available decisions. Each decision leads to a next state. Bellman's equation provides a recursive formula that expresses the optimal value of a state in terms of the optimal value of subsequent states, allowing the problem to be solved by working backwards from the final state.
Q: What distinguishes a Markov decision process from a general stochastic dynamic program?
A: An MDP has discrete states and discrete decisions, and its transition probabilities depend only on the current state and current decision (the Markov property). A general stochastic dynamic program may have continuous states, and transition probabilities may depend on the full history of states and decisions.
Q: Outline the general iterative procedure used by most optimisation algorithms.
A: Step 1: create an initial solution (which may be poor or infeasible). Step 2: repeat: find an improving direction t, choose a step size theta, update the solution as new = old + theta * t. Step 3: stop when the solution converges (changes very little) or when time runs out.
Stochastic optimisation connects to probability and statistics (you need probability distributions to define scenarios and expected costs) and to forecasting (the uncertainty often comes from forecast error, which ties back to the ARIMA and GARCH models in Doc 1).
Dynamic programming and MDPs connect to reinforcement learning, which is essentially an MDP where the transition probabilities are learned through experience rather than known in advance. If you continue into AI or machine learning, MDPs are the foundation.
The iterative algorithm structure connects to gradient descent, the workhorse of neural network training. The same idea of direction plus step size underlies every deep learning optimisation method.
Conservative modelling is used in power grid planning, where demand spikes can be catastrophic. Scenario modelling drives financial stress testing for banks (required by regulators). MDPs are used in robotics for planning sequences of actions, in inventory management for reorder decisions and in healthcare for treatment sequencing. The iterative optimisation algorithm structure is the basis for training every modern machine learning model.
Tags: stochastic optimisation, uncertainty, conservative modelling, scenario modelling, robust solution, expected cost, dynamic programming, dynamic program, Bellman's equation, stochastic dynamic program, Markov decision process, MDP, Markov property, optimisation algorithm, improving direction, step size, gradient descent, convergence, iterative method, prescriptive analytics