In my first TDS submit, I wrote about how one can translate a real-world drawback into an integer linear program. In my second, I wrote about how one can make that program strong in opposition to uncertainty. Each had been variations on the identical thought: take a fuzzy real-world query, squeeze it into an LP, and let a solver do the remaining.
There’s a second in each optimizer’s life, although, when the LP begins to really feel a bit too neat. Demand is a quantity. Journey time is a quantity. Wind velocity is a quantity. The mannequin accepts the enter, returns an optimum answer, and goes on its method. The truth these numbers had been supposed to explain (messy, jittery, and infrequently shocking) doesn’t actually present up wherever.
Stochastic programming is the sphere that takes that discomfort critically. As a substitute of pretending the information is precise, it builds the uncertainty straight into the mannequin. The value you pay is a little more notation; the payoff is choices that maintain up when the world doesn’t cooperate.
This submit is a mild tour of the fundamentals. We’ll see why the apparent strategy doesn’t work, stroll via the 4 normal methods to deal with uncertainty in a linear program, and end with a fast sanity examine on whether or not any of that is definitely worth the effort. There’s some math, but it surely’s the identical math you already know from LP, with one further image hooked up.
Place to begin: a style firm with a foul crystal ball
To make this concrete, we’ll use the working instance from dr. Ruben van Beesten’s lectures (extra on that within the credit under). It goes like this.
You run a style firm that sells winter clothes in Germany. Manufacturing occurs in Bangladesh, which is reasonable however gradual: the products take a number of weeks to reach. So within the fall, it’s important to resolve how a lot to provide for the upcoming winter season.
Two methods this may go improper: produce too little, and also you lose gross sales; produce an excessive amount of, and also you’re caught with inventory you’ll be able to’t promote. The entire query is how a lot to provide now, and the reply is determined by one thing you don’t really know but: winter demand.
In the event you ignored the uncertainty for a second and pretended demand was a hard and fast quantity, you can write down a vanilla LP:
Right here x is how a lot you produce, c is the unit manufacturing price, h is demand, and T is simply the id matrix (one unit produced satisfies one unit of demand). The constraint says: produce at the least as a lot as is demanded.
That is effective if h is definitely recognized. The difficulty is that demand isn’t a quantity, it’s a random variable. Let’s name it ξ. The sincere model of the mannequin would appear like this:
And right here we hit a wall. What does it imply for x to fulfill a constraint that is determined by a random variable? Is x = 100possible if demand would possibly be 80, would possibly be 120, and is likely to be wherever in between? The issue isn’t exhausting to unravel: it’s ill-defined. The solver doesn’t even know which drawback you’re asking it to unravel.
Stochastic programming is, in essence, a group of principled solutions to that query. We’ll take a look at the 4 most typical ones.
4 methods to deal with the uncertainty
Every of the 4 approaches takes the ill-defined LP above and turns it right into a well-defined optimization drawback. They differ in what they assume you recognize concerning the uncertainty, and in how cautious they’re about dangerous outcomes.
1. Strong optimization: put together for the worst
Probably the most cautious strategy. You don’t must know the total likelihood distribution of ξ, however solely its assist, i.e., the set of values it might presumably take. We name this set the uncertainty set, written U. Then you definately ask: what’s the greatest determination that stays possible regardless of which ξ ∈ U really exhibits up?
The constraint now has to carry for each ξ within the uncertainty set. In our style instance with U = [0, 10], you’d be planning for demand of 10, the worst case, each time.
That’s the power and the weak spot of strong optimization in a single sentence. The answer is bulletproof, but it surely’s additionally conservative: you’ll typically be sitting on stock you didn’t want, since you deliberate as if the unlikely worst case had been assured. In the event you’ve learn my earlier submit on robustifying linear applications, that is precisely the framework that sits behind these 4 steps.
2. Likelihood constraints: loosen up the worst case
Strong optimization plans for any doable end result. Likelihood constraints loosen up that to: plan for most of them. You choose a likelihood degree α, say 95%, and require the constraint to carry with at the least that likelihood:
That is known as a joint probability constraint: all of the entries of the constraint vector need to be glad concurrently, with joint likelihood ≥ α. A weaker variant treats every row individually:
These are particular person probability constraints: every constraint i should maintain with likelihood at the least αᵢ, however you don’t care concerning the joint occasion. Fast train: for those who set each αᵢ equal to the joint α, which formulation is extra conservative?
Reply: the joint model. Satisfying all constraints concurrently is a stricter requirement than satisfying each in isolation, so the joint formulation has a smaller possible area and a worse (larger) optimum price. Both method, probability constraints provide you with a knob, α, to dial how cautious you need to be. Crank it to 1, and also you’re again to (nearly) strong. Drop it to 0.5, and also you’re principally flipping a coin on feasibility. Most actual purposes dwell someplace within the 0.9–0.99 vary.
There’s a catch value flagging: probability constraints are exhausting typically. The likelihood time period contained in the constraint is a non-linear, typically non-convex operate of x, so that you often can’t hand the formulation on to a normal LP solver. There are tractable particular instances (Gaussian noise, sure mixtures of distributions, sample-based approximations), however the basic drawback is tougher than it appears to be like at first look.
3. Two-stage recourse fashions: resolve, observe, appropriate
The primary two approaches deal with constraint violation as one thing to keep away from, both all the time (strong) or with excessive likelihood (probability). Typically that’s the improper body. In our style instance, falling in need of demand isn’t catastrophic. It’s annoying. You’ll be able to often repair it: produce a small emergency batch in Germany at the next price, or ship by air, or simply settle for the misplaced gross sales and transfer on.
This concept, that violating a constraint isn’t the top of the world, you’ll be able to take a corrective motion later, is the center of recourse fashions. Within the two-stage model, the timeline appears to be like like this:
- Stage 1 (now): you make a first-stage determination x whereas ξ continues to be unsure.
- Then: ξ is realized, i.e., the random variable turns into a recognized quantity.
- Stage 2 (later): you make a second-stage determination y, figuring out ξ.
Mathematically, the primary stage appears to be like nearly like a vanilla LP, besides the target now accommodates an anticipated future price:
The operate v(ξ, x) is the optimum worth of the second-stage drawback, given that you just selected x within the first stage and that ξ turned out to be the realized worth:
Learn this rigorously. The fitting-hand facet, h(ξ) − T(ξ) x, is the shortfall, how a lot your first-stage determination did not cowl, after ξ was revealed. The recourse determination y then closes that hole, at a price q(ξ)ᵀ y. So the construction is: pay the up-front price cᵀ x, and on high of it pay the anticipated price of cleansing up after the random variable does its factor.
That’s the entire thought. Two-stage recourse fashions are by far the commonest formulation in follow, partly as a result of they seize the precise chronology of choices in lots of actual issues (manufacturing planning, stock, vitality dispatch, scheduling), and partly as a result of they’re comparatively well-behaved mathematically.
A few items of vocabulary you’ll journey over for those who learn additional:
- A mannequin has mounted recourse if the recourse matrix W doesn’t depend upon ξ. Many algorithms solely work on this case.
- A mannequin has (comparatively) full recourse if there’s all the time a possible recourse determination y, it doesn’t matter what ξ seems to be and it doesn’t matter what x you selected. If full recourse fails, the second-stage drawback could be infeasible, which turns into an implicit constraint on the primary stage. (That is precisely the place Benders’ feasibility cuts come from, however that’s a narrative for an additional submit.)
4. Multi-stage recourse fashions: hold going
Typically life isn’t two levels. You don’t simply decide-observe-correct as soon as and go dwelling; you resolve, observe, resolve, observe, resolve, … time and again. Multi-stage recourse fashions are the pure extension.
In our style instance, suppose we’re now not selecting as soon as within the fall, however 3 times: within the fall (low cost, in Bangladesh), in early winter (dearer, in Romania), and in late winter (costliest, in Germany). Demand is regularly revealed over the season, and at every stage we resolve based mostly on what we’ve noticed up to now.
The notation will get heavier, you find yourself writing recursive worth capabilities Qₜ, with histories ξ[t] = (ξ₁, …, ξₜ) hanging off them, however conceptually nothing new is occurring. Every stage is a recourse drawback nested contained in the earlier one. The pure strategy to image that is as a situation tree: every node is a state of the world, every department is a doable realization of the subsequent random variable, and a situation is an entire root-to-leaf path.
One subtlety. A situation is the whole trajectory of ξ, not only one realization. Realizing that ξ₂ = 10 doesn’t let you know which situation you’re in, as a result of ξ₃ hasn’t occurred but. This issues if you begin writing the deterministic equal (subsequent part), as a result of it’s important to watch out that your choices solely depend upon data that has really been noticed by the point the choice is made. That property known as non-anticipativity: you’ll be able to’t anticipate the long run. The mannequin would fortunately cheat for those who didn’t implement it explicitly.
How will we really remedy a recourse mannequin?
Thus far we’ve been writing fashions. To resolve them, we usually rework them into one thing a normal LP solver can chew on. The trick is the deterministic equal formulation.
Suppose the random variable ξ has a discrete distribution: it takes finitely many values ξ¹, ξ², …, ξˢ (known as eventualities), every with likelihood pₛ. Then the anticipated second-stage price is only a finite sum, and we will write the whole two-stage drawback as one massive LP by introducing one copy of y per situation:
That’s a daily LP. Large, presumably very massive, in case you have S eventualities, you’ve primarily copied the second stage S instances, but it surely’s an LP. You’ll be able to hand it straight to HiGHS, Gurobi, CPLEX, or no matter solver you want, and it’ll remedy it.
Two pure questions observe.
First: what if the distribution of ξ is not discrete? In that case the deterministic equal has infinitely many eventualities and isn’t finite-dimensional. The usual repair is pattern common approximation: draw a pattern of measurement S from the true distribution, remedy the sampled deterministic equal, and let S develop till your answer stabilizes statistically. There’s a complete literature on how massive S must be and what ensures you get.
Second: what if the deterministic equal is simply too massive to unravel straight? That is the place decomposition strategies are available in. Benders’ decomposition splits the issue right into a grasp drawback within the first-stage variables and a subproblem per situation, then iteratively passes data between them. For multi-stage fashions with many levels, the analogous trick is stochastic twin dynamic programming (SDDP), which makes use of sampling and approximate worth capabilities to keep away from constructing the total situation tree. Each are superior sufficient to deserve their very own posts, so I’ll come again to them later.
Is any of this really definitely worth the bother?
Trustworthy query. Stochastic applications are messier to formulate, tougher to unravel, and slower to run than their deterministic cousins. In case your real-world drawback isn’t very delicate to uncertainty, you is likely to be higher off simply plugging the anticipated demand into a daily LP and calling it a day.
The excellent news is, you’ll be able to quantify precisely how a lot the stochastic formulation buys you. There are two classical metrics, and each are value figuring out.
Outline 4 numbers:
In phrases: SP is the optimum worth of the particular stochastic program. EV is what you get for those who substitute ξ with its anticipated worth and remedy the ensuing deterministic drawback; name its answer x̄. EEV is the anticipated price of implementing that deterministic answer x̄ within the precise stochastic world. And WS (“wait-and-see”) is the anticipated price for those who bought to peek on the realized ξ earlier than deciding x, the cheating-but-best case.
From these 4 numbers you’ll be able to construct two extremely informative portions:
VSS is the Worth of the Stochastic Resolution: how a lot worse off you’d be for those who simply solved the deterministic drawback with common values and carried out its answer. If VSS is small, the stochastic program isn’t shopping for you a lot; the deterministic shortcut is okay.
EVPI is the Anticipated Worth of Good Info: how a lot you’d acquire if a benevolent oracle handed you the realized ξ earlier than you needed to resolve. If EVPI is small, your forecasts already comprise many of the data you want; investing in higher predictions most likely received’t transfer the needle. If EVPI is massive, higher knowledge has actual worth.
The 2 metrics trip alongside on a tidy chain of inequalities (assuming uncertainty solely on the right-hand facet):
Learn it left to proper: cheating-with-the-mean (EV) is at most as dangerous as cheating-with-the-realization (WS), which is at most as dangerous because the sincere stochastic reply (SP), which is at most as dangerous as plugging within the deterministic-solution-and-living-with-it (EEV). The chain implies a free higher sure on VSS that you could compute earlier than you ever remedy the SP: VSS ≤ EEV − EV. If that hole is tiny, the deterministic shortcut is sweet sufficient and it can save you your self the headache.
The place to go from right here
This submit caught to the fundamentals: how one can write a stochastic program down. The following pure step is how one can remedy massive ones effectively. The 2 massive workhorses are:
- Benders’ decomposition — for two-stage fashions, decomposes the deterministic equal right into a grasp drawback (in x) plus one subproblem per situation, and reconciles them with cuts. Notably elegant when you’ve got plenty of eventualities however a comparatively small first stage.
- Stochastic Twin Dynamic Programming (SDDP) — for multi-stage fashions, makes use of sampling and piecewise-linear approximations of the long run worth capabilities. Famously utilized in hydropower scheduling, the place the situation tree is so massive that specific enumeration is hopeless.
Each deserve their very own posts. If there’s curiosity, I’ll write them up.
Takeaway
In the event you’re utilizing LPs in any context the place the enter knowledge is genuinely unsure as a result of forecasted demand, climate, costs, journey instances, or the rest, then your mannequin is making an implicit selection about how one can deal with that uncertainty. “Simply use the imply” is a selection. So is “plan for the worst.” Stochastic programming offers you the vocabulary to make that selection specific, and the instruments to judge whether or not your selection was one (hiya, VSS).
To summarize the 4 primary methods to mannequin uncertainty in an LP:
- Strong optimization — plan for the worst case in a given uncertainty set.
- Likelihood constraints — require feasibility with at the least likelihood α.
- Two-stage recourse — resolve, observe, appropriate; pay an anticipated recourse price.
- Multi-stage recourse — the identical thought, repeated over time on a situation tree.
And two metrics value holding in your again pocket: VSS (does the stochastic mannequin assist?) and EVPI (would higher forecasts assist?).
Most actual issues aren’t deterministic. The excellent news is your modeling toolkit doesn’t need to be both.
Credit and references
This submit is predicated on lectures by dr. Ruben van Beesten (Norwegian College of Science and Know-how) from his course on Stochastic Programming given in October 2023, which I had the pleasure of attending in Trondheim, Norway. The style-company instance, the four-way taxonomy of formulations, and the VSS/EVPI framing all come straight from his slides; any clumsiness within the retelling is mine.
The unique modeling train that motivates a lot of the recourse-model instinct is from
- Higle, J. L. (2005). Stochastic Programming: Optimization When Uncertainty Issues. In INFORMS TutORials in Operations Analysis, pp. 30–53.
A few additional pointers value figuring out about:
- Kleywegt, A. J., Shapiro, A., and Homem-de-Mello, T. (2002). The pattern common approximation technique for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479–502. The usual reference for SAA.
- Higle, J. L., and Sen, S. (1991). Stochastic decomposition: an algorithm for two-stage linear applications with recourse. Arithmetic of Operations Analysis, 16(3), 650–669. One of many few strategies that handles non-discrete distributions straight.
And naturally, the 2 earlier posts on this sequence: 5 questions that may allow you to mannequin integer linear applications higher and 4 steps to robustify your linear program.
