Stochastic Programming

Stochastic Programming for Health Care Planning Under Uncertainty

Stochastic programming chooses a plan by mathematical optimisation when some of the numbers the plan depends on, such as patient demand or treatment effects, are not known at the time of choosing. Each uncertain input enters the model as a probability distribution or a set of weighted scenarios, and the model picks the plan that does best across them, usually on expected cost or expected health gain. In health care the method suits commitments made early and adjusted later, for example contracting winter beds or dividing a budget between programmes. Unlike probabilistic sensitivity analysis, stochastic programming searches every feasible plan, including later adjustments, for the one that does best across the uncertainty, instead of comparing a few fixed options.

Decisions taken before uncertainty resolves

Ordinary constrained optimisation treats every parameter as known. The ISPOR Optimization Methods Emerging Good Practices Task Force (Crown and colleagues) states that in deterministic optimisation the parameters are fixed while in stochastic optimisation uncertainty is incorporated, and gives uncertainty in the costs and benefits of interventions as its example of when the stochastic extension applies.

The central idea is timing. Chen and Wu, modelling influenza vaccine supply, describe first-stage decisions as determined irrespective of the random events and second-stage decisions as taken once the information is disclosed, so vaccine ordering comes first and allocation follows. The later decisions are called recourse, because they let the plan adjust.

The two-stage recourse formulation

The outer problem picks the first-stage decision and pays its cost. The inner problem, solved once the uncertainty is revealed, picks the cheapest recourse given what was already committed.

$$\min_{x \in X} \; c^{\top}x + \mathbb{E}_{\xi}\big[Q(x,\xi)\big]$$

where $x$ is the vector of first-stage decisions (beds contracted, doses ordered, budget shares), $X$ the set of choices that meet known constraints such as a budget, $c$ the first-stage unit costs, $\xi$ the random vector of uncertain inputs, $\mathbb{E}_{\xi}$ the expectation over its distribution and $Q(x,\xi)$ the lowest second-stage cost once $\xi$ is known.

$$Q(x,\xi) = \min_{y \ge 0} \; q(\xi)^{\top}y \quad \text{subject to} \quad W y = h(\xi) - T(\xi)\,x$$

where $y$ is the vector of recourse decisions, $q(\xi)$ their unit costs, $W$ the recourse matrix, $h(\xi)$ the requirements to be met, such as patients to be treated, and $T(\xi)$ the matrix that converts first-stage decisions into contributions towards those requirements.

With a finite set of $S$ scenarios, scenario $s$ having probability $p_s$, the expectation becomes the weighted sum of $p_s Q(x,\xi_s)$, and the problem can be solved as one large deterministic model with a copy of the recourse variables for each scenario. The first-stage $x$ carries no scenario index, which is what forces one plan to serve every possible future. Multi-stage versions repeat the pattern over several periods and are close relatives of dynamic programming.

The distributions behind $\xi$ are the same kind of inputs a health economic model already uses, so the parameter uncertainty characterised for a decision model can feed a stochastic program. Continuous distributions are usually handled by sampling a finite set of scenarios. Chen and Wu use sample average approximation, and their objective settled once the sample exceeded three thousand. Whole beds or staff shifts turn the model into a stochastic form of integer programming.

Four benchmarks and what uncertainty is worth

Four objective values of a minimisation problem measure what modelling uncertainty is worth. The expected value problem (EV) replaces every random input by its mean and solves a deterministic model. The expectation of the expected value solution (EEV) fixes the first-stage decision at the EV answer and lets recourse respond in each scenario. The recourse problem (RP) is the stochastic program itself, and the wait-and-see value (WS) averages the costs achieved if the outcome were observed before the first-stage decision.

$$\mathrm{VSS} = \mathrm{EEV} - \mathrm{RP}, \qquad \mathrm{EVPI} = \mathrm{RP} - \mathrm{WS}$$

where VSS is the value of the stochastic solution, the expected saving from solving the stochastic program instead of planning on mean values, and EVPI is the expected value of perfect information, the most it would be worth paying to learn the outcome before committing. Chen and Wu note that RP never exceeds EEV when minimising, so the VSS is the potential loss from deciding on expected values. For a maximisation problem, such as maximising QALYs, the differences are taken the other way round.

This EVPI is the quantity health economists know as EVPI, applied to a plan with recourse rather than a choice among fixed strategies. Chalabi and colleagues built a two-stage stochastic formulation that allocates resources within and between health care programmes under an exogenous budget and calculates the expected value of acquiring information to resolve the uncertainties within the allocation. A small VSS is informative too. In Chen and Wu's influenza model the EEV was 8,899,142 and the RP 8,884,969, a VSS of 14,173, which the authors put down to minor variation in the uncertain parameters.

Worked example with winter escalation beds and spot purchasing

All numbers in this example are illustrative. A commissioner must decide in autumn how many winter beds to contract at GBP 5,000 per bed for the season. Any shortfall is bought from other providers at GBP 10,000 per bed, and unused contracted beds are still paid for. A mild season needs 30 beds (probability 0.6) and a severe season needs 100 beds (probability 0.4). Costs are in GBP thousand.

$$C(x,d) = 5x + 10\max(d - x,\,0)$$

where $x$ is the number of beds contracted, $d$ the number needed in the season, and the two terms are the first-stage contract cost and the recourse cost of spot purchases.

1. Expected value problem. Expected demand is 0.6 × 30 + 0.4 × 100 = 58 beds. A contracted bed is cheaper than a spot bed, so the EV plan contracts 58 beds and forecasts a cost of 5 × 58 = 290.

2. Expected cost of the EV plan. With 58 beds a mild season costs 290 and a severe season costs 290 + 10 × 42 = 710. The EEV is 0.6 × 290 + 0.4 × 710 = 458.

3. Recourse problem. Below 30 beds every extra bed saves a spot purchase in both seasons, so expected cost falls. Between 30 and 100 beds the expected cost is 5x + 4 × (100 − x), which is 400 + x, so each extra bed adds 1, because it costs 5 and saves 10 only with probability 0.4. The best plan contracts 30 beds, costing 150 in a mild season and 150 + 10 × 70 = 850 in a severe one, so RP is 0.6 × 150 + 0.4 × 850 = 430.

4. Wait and see. Knowing the season in advance, the commissioner would contract 30 beds at 150 or 100 beds at 500, so WS is 0.6 × 150 + 0.4 × 500 = 290.

5. VSS and EVPI. VSS is 458 − 430 = 28, or GBP 28,000. EVPI is 430 − 290 = 140, or GBP 140,000.

6. Interpretation. The stochastic solution contracts fewer beds than average demand because the 0.4 chance of saving 10 is worth 4, less than the 5 a contracted bed costs. The EVPI of GBP 140,000 caps what a perfect forecast of the season would be worth for this decision. The spot price stands in for every consequence of a shortfall, and if delayed admission harms patients those health losses belong in the objective or a constraint, where they could push the answer towards more contracted beds.

Stochastic programming in health resource allocation

Health economic interest in the method comes mostly from the budget allocation problem. The ISPOR task force notes that traditional health economic models rely on repeatedly applying a cost-effectiveness threshold to individual HTA decisions to optimise the allocation of resources, and that capacity constraints are usually neglected in such models.

McKenna and colleagues state that earlier attempts to bring uncertainty about costs and effects into mathematical programming had important limitations, and develop a two-stage stochastic version. They find that the value of further research depends on the budgetary policy in place, the realisations revealed during the budget period, the remedial actions available and the variability in parameter values. A standard value of information calculation values a single choice among strategies, so this result shows that recourse within the budget period changes what research is worth.

Tanner and colleagues formulate the choice of a vaccination policy under parameter uncertainty as a stochastic program. Their numerical example shows that including the uncertainty makes the optimal strategy less exposed to error in the parameters, at the cost of vaccinating more of the population. Burdett and colleagues apply the method to capacity planning for a whole hospital.

Choices that change the answer

Most stochastic programs minimise expected cost or maximise expected health gain, which treats the decision maker as risk neutral and matches the expected net benefit rule of cost-effectiveness analysis. Al and colleagues bring uncertainty about costs and effects into a health care allocation model through expected utility and argue that approaches without an explicit utility function still carry implicit notions about risk attitude.

A chance constraint requires a condition to hold with at least a stated probability. Tanner and colleagues seek the lowest-cost vaccination policy for which the probability that the post-vaccination reproduction number is at most one exceeds a chosen level, and Burdett and colleagues set a risk threshold for temporary exceedances of hospital capacity.

The ISPOR task force calls it good practice to run an optimisation model with different parameter values and to examine how the decision variables and optimum value react, and alternative scenario sets belong in a scenario analysis. Which decisions count as recourse should match what managers can really change once the season is under way.

Stochastic programming beside robust optimisation and probabilistic analysis

Robust optimisation needs no probabilities and chooses the plan whose worst outcome within a stated uncertainty set is best. In the bed example that plan contracts 100 beds and costs 500 whatever happens. Chalabi and colleagues argue that for the health care allocation problem the two-stage stochastic formulation has several advantages over chance constrained and robust mathematical programming methods.

The ISPOR task force contrasts modelling methods that evaluate a few scenarios and pick a good one with optimisation methods that aim to identify the best solution overall. A probabilistic sensitivity analysis belongs to the first group. Monte Carlo simulation can generate the scenarios a stochastic program uses, and deterministic linear programming is the special case with a single scenario.

Limitations and common misreadings

A common misreading treats the objective value of a mean-value model as a forecast. In Chen and Wu's model the EV objective was about 8.4 million against 8.9 million for the recourse problem, and in the bed example the EV plan promised 290 but would cost 458 on average. A second error reads the stochastic solution as safe in every scenario, when it minimises the average and costs 850 in the severe season.

The answer is only as good as the probabilities behind it, and the chance of a rare surge is among the hardest inputs to estimate. Large models are hard to solve, and Burdett and colleagues needed a new two-stage hierarchical solution approach because of the size and complexity of their hospital capacity model. The ISPOR task force notes that total costs and QALYs typically have a non-linear relationship with model parameters, so a linear stochastic program built from a health economic model is an approximation. A plan that assumes remedial actions which budget rules or contracts do not allow overstates the value of flexibility, the point McKenna and colleagues make about budgetary policies.

Sources

• Al MJ, Feenstra TL, van Hout BA. Optimal allocation of resources over health care programmes: dealing with decreasing marginal utility and uncertainty. Health Economics. 2005;14(7):655-667. https://doi.org/10.1002/hec.973
• Burdett RL, Corry P, Spratt B, Cook D, Yarlagadda P. A stochastic programming approach to perform hospital capacity assessments. PLoS One. 2023;18(11):e0287980. https://doi.org/10.1371/journal.pone.0287980
• Chalabi Z, Epstein D, McKenna C, Claxton K. Uncertainty and value of information when allocating resources within and between healthcare programmes. European Journal of Operational Research. 2008;191(2):530-539. https://doi.org/10.1016/j.ejor.2007.07.026
• Chen SI, Wu CY. A stochastic programming model of vaccine preparation and administration for seasonal influenza interventions. Mathematical Biosciences and Engineering. 2020;17(4):2984-2997. https://doi.org/10.3934/mbe.2020169
• Crown W, Buyukkaramikli N, Thokala P, Morton A, Sir MY, Marshall DA, et al. Constrained optimization methods in health services research, an introduction: report 1 of the ISPOR Optimization Methods Emerging Good Practices Task Force. Value in Health. 2017;20(3):310-319. https://doi.org/10.1016/j.jval.2017.01.013
• McKenna C, Chalabi Z, Epstein D, Claxton K. Budgetary policies and available actions: a generalisation of decision rules for allocation and research decisions. Journal of Health Economics. 2010;29(1):170-181. https://doi.org/10.1016/j.jhealeco.2009.11.005
• Tanner MW, Sattenspiel L, Ntaimo L. Finding optimal vaccination strategies under parameter uncertainty using stochastic programming. Mathematical Biosciences. 2008;215(2):144-151. https://doi.org/10.1016/j.mbs.2008.07.006
• Vatn J. Stochastic programming. Lecture slides, TPK4191, Norwegian University of Science and Technology; September 2025. https://jvatn.folk.ntnu.no/eLearning/TPK4191/slides/StochasticProgramming.pdf