In my first TDS submit, I wrote about easy methods to translate a real-world drawback into an integer linear program. In my second, I wrote about easy methods to make that program strong towards uncertainty. Each have been variations on the identical concept: take a fuzzy real-world query, squeeze it into an LP, and let a solver do the remainder.
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 fact these numbers have been supposed to explain (messy, jittery, and infrequently shocking) doesn’t actually present up wherever.
Stochastic programming is the sector that takes that discomfort significantly. As a substitute of pretending the info is actual, it builds the uncertainty immediately into the mannequin. The value you pay is a little more notation; the payoff is selections that maintain up when the world doesn’t cooperate.
This submit is a delicate tour of the fundamentals. We’ll see why the apparent strategy doesn’t work, stroll by means of the 4 normal methods to deal with uncertainty in a linear program, and end with a fast sanity verify on whether or not any of that is definitely worth the effort. There’s some math, however it’s the identical math you already know from LP, with one additional image connected.
Place to begin: a vogue firm with a foul crystal ball
To make this concrete, we’ll use the operating instance from dr. Ruben van Beesten’s lectures (extra on that within the credit beneath). It goes like this.
You run a vogue firm that sells winter clothes in Germany. Manufacturing occurs in Bangladesh, which is reasonable however gradual: the products take a couple of weeks to reach. So within the fall, it’s a must to resolve how a lot to provide for the upcoming winter season.
Two methods this will go unsuitable: produce too little, and also you lose gross sales; produce an excessive amount of, and also you’re caught with inventory you may’t promote. The entire query is how a lot to provide now, and the reply relies on one thing you don’t truly know but: winter demand.
Should 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 very least as a lot as is demanded.
That is high-quality if h is definitely identified. 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 seem like this:
And right here we hit a wall. What does it imply for x to fulfill a constraint that relies on a random variable? Is x = 100possible if demand may be 80, may be 120, and is perhaps wherever in between? The issue isn’t onerous 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 set of principled solutions to that query. We’ll have a look at the 4 commonest 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 understand in regards to the uncertainty, and in how cautious they’re about unhealthy outcomes.
1. Strong optimization: put together for the worst
Probably the most cautious strategy. You don’t have to know the complete chance 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 finest determination that stays possible regardless of which ξ ∈ U truly reveals up?
The constraint now has to carry for each ξ within the uncertainty set. In our vogue instance with U = [0, 10], you’d be planning for demand of 10, the worst case, each time.
That’s the energy and the weak spot of sturdy optimization in a single sentence. The answer is bulletproof, however it’s additionally conservative: you’ll typically be sitting on stock you didn’t want, since you deliberate as if the unlikely worst case have been assured. Should you’ve learn my earlier submit on robustifying linear packages, that is precisely the framework that sits behind these 4 steps.
2. Probability constraints: chill out the worst case
Strong optimization plans for any potential end result. Probability constraints chill out that to: plan for most of them. You decide a chance stage α, say 95%, and require the constraint to carry with at the very least that chance:
That is known as a joint probability constraint: all of the entries of the constraint vector must be glad concurrently, with joint chance ≥ α. A weaker variant treats every row individually:
These are particular person probability constraints: every constraint i should maintain with chance at the very least αᵢ, however you don’t care in regards to the joint occasion. Fast train: in the event you 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 every one in isolation, so the joint formulation has a smaller possible area and a worse (increased) 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 (virtually) strong. Drop it to 0.5, and also you’re mainly flipping a coin on feasibility. Most actual purposes dwell someplace within the 0.9–0.99 vary.
There’s a catch price flagging: probability constraints are onerous generally. The chance time period contained in the constraint is a non-linear, typically non-convex operate of x, so that you normally can’t hand the formulation on to a normal LP solver. There are tractable particular circumstances (Gaussian noise, sure mixtures of distributions, sample-based approximations), however the common drawback is more durable than it appears 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 at all times (strong) or with excessive chance (probability). Generally that’s the unsuitable body. In our vogue instance, falling in need of demand isn’t catastrophic. It’s annoying. You may normally 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 tip of the world, you may take a corrective motion later, is the guts of recourse fashions. Within the two-stage model, the timeline appears 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 identified quantity.
- Stage 2 (later): you make a second-stage determination y, understanding ξ.
Mathematically, the primary stage appears virtually 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 simply selected x within the first stage and that ξ turned out to be the realized worth:
Learn this fastidiously. The best-hand aspect, h(ξ) − T(ξ) x, is the shortfall, how a lot your first-stage determination didn’t 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 prime of it pay the anticipated price of cleansing up after the random variable does its factor.
That’s the entire concept. Two-stage recourse fashions are by far the commonest formulation in apply, partly as a result of they seize the precise chronology of selections 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 in the event you learn additional:
- A mannequin has mounted recourse if the recourse matrix W doesn’t rely on ξ. Many algorithms solely work on this case.
- A mannequin has (comparatively) full recourse if there’s at all times 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 might 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: preserve going
Generally life isn’t two levels. You don’t simply decide-observe-correct as soon as and go house; you resolve, observe, resolve, observe, resolve, … time and again. Multi-stage recourse fashions are the pure extension.
In our vogue instance, suppose we’re now not selecting as soon as within the fall, however thrice: within the fall (low-cost, in Bangladesh), in early winter (costlier, in Romania), and in late winter (costliest, in Germany). Demand is progressively revealed over the season, and at every stage we resolve primarily based on what we’ve noticed thus far.
The notation will get heavier, you find yourself writing recursive worth capabilities Qₜ, with histories ξ[t] = (ξ₁, …, ξₜ) hanging off them, however conceptually nothing new is happening. Every stage is a recourse drawback nested contained in the earlier one. The pure strategy to image that is as a state of affairs tree: every node is a state of the world, every department is a potential realization of the following random variable, and a state of affairs is an entire root-to-leaf path.
One subtlety. A state of affairs is the whole trajectory of ξ, not only one realization. Realizing that ξ₂ = 10 doesn’t inform you which state of affairs 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 a must to watch out that your selections solely rely on data that has truly been noticed by the point the choice is made. That property is known as non-anticipativity: you may’t anticipate the longer term. The mannequin would fortunately cheat in the event you didn’t implement it explicitly.
How will we truly resolve a recourse mannequin?
To this point we’ve been writing fashions. To resolve them, we sometimes remodel 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 chance pₛ. Then the anticipated second-stage price is only a finite sum, and we will write the whole two-stage drawback as one large LP by introducing one copy of y per state of affairs:
That’s a daily LP. Large, presumably very large, when you have S eventualities, you’ve basically copied the second stage S instances, however it’s an LP. You may hand it straight to HiGHS, Gurobi, CPLEX, or no matter solver you want, and it’ll resolve it.
Two pure questions comply with.
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, resolve the sampled deterministic equal, and let S develop till your answer stabilizes statistically. There’s a complete literature on how large S must be and what ensures you get.
Second: what if the deterministic equal is simply too large to unravel immediately? 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 state of affairs, 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 complete state of affairs tree. Each are superior sufficient to deserve their very own posts, so I’ll come again to them later.
Is any of this truly definitely worth the bother?
Trustworthy query. Stochastic packages are messier to formulate, more durable to unravel, and slower to run than their deterministic cousins. In case your real-world drawback isn’t very delicate to uncertainty, you is perhaps higher off simply plugging the anticipated demand into a daily LP and calling it a day.
The excellent news is, you may quantify precisely how a lot the stochastic formulation buys you. There are two classical metrics, and each are price understanding.
Outline 4 numbers:
In phrases: SP is the optimum worth of the particular stochastic program. EV is what you get in the event you substitute ξ with its anticipated worth and resolve 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 in the event you acquired to peek on the realized ξ earlier than deciding x, the cheating-but-best case.
From these 4 numbers you may construct two extremely informative portions:
VSS is the Worth of the Stochastic Resolution: how a lot worse off you’d be in the event you simply solved the deterministic drawback with common values and applied its answer. If VSS is small, the stochastic program isn’t shopping for you a lot; the deterministic shortcut is ok.
EVPI is the Anticipated Worth of Excellent Data: how a lot you’d achieve if a benevolent oracle handed you the realized ξ earlier than you needed to resolve. If EVPI is small, your forecasts already include 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 aspect):
Learn it left to proper: cheating-with-the-mean (EV) is at most as unhealthy as cheating-with-the-realization (WS), which is at most as unhealthy because the sincere stochastic reply (SP), which is at most as unhealthy as plugging within the deterministic-solution-and-living-with-it (EEV). The chain implies a free higher sure on VSS that you would be able to compute earlier than you ever resolve 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: easy methods to write a stochastic program down. The subsequent pure step is easy methods to resolve massive ones effectively. The 2 large workhorses are:
- Benders’ decomposition — for two-stage fashions, decomposes the deterministic equal right into a grasp drawback (in x) plus one subproblem per state of affairs, and reconciles them with cuts. Significantly elegant when you’ve gotten a number 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 longer term worth capabilities. Famously utilized in hydropower scheduling, the place the state of affairs tree is so large that express enumeration is hopeless.
Each deserve their very own posts. If there’s curiosity, I’ll write them up.
Takeaway
Should you’re utilizing LPs in any context the place the enter knowledge is genuinely unsure resulting from forecasted demand, climate, costs, journey instances, or the rest, then your mannequin is making an implicit selection about easy methods to deal with that uncertainty. “Simply use the imply” is a selection. So is “plan for the worst.” Stochastic programming provides you the vocabulary to make that selection express, and the instruments to judge whether or not your selection was a very good one (hey, 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.
- Probability constraints — require feasibility with at the very least chance α.
- Two-stage recourse — resolve, observe, appropriate; pay an anticipated recourse price.
- Multi-stage recourse — the identical concept, repeated over time on a state of affairs tree.
And two metrics price 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 must 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 price understanding about:
- Kleywegt, A. J., Shapiro, A., and Homem-de-Mello, T. (2002). The pattern common approximation methodology 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 packages with recourse. Arithmetic of Operations Analysis, 16(3), 650–669. One of many few strategies that handles non-discrete distributions immediately.
And naturally, the 2 earlier posts on this sequence: 5 questions that can make it easier to mannequin integer linear packages higher and 4 steps to robustify your linear program.
