YT YouTube2Text

YouTube2Text → Transcripts → Why predict-then-optimize and end-to-end learning won't fix your optimization under uncertainty.

Why predict-then-optimize and end-to-end learning won't fix your optimization under uncertainty. — Transcript

by InsideOpt Tutorials · 7,184 words · 1,183 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01Today we want to talk about two
0:04approaches that people typically take
0:07when dealing with uncertain forecasts in
0:09operational research.
0:11The first one is predict and optimize
0:13and the other one is end-to-end
0:15learning, sometimes also known as
0:18predict and optimize.
0:21And today we're going to look at a
0:22couple of examples, very simple
0:24examples, that will show
0:27that both of them
0:28are not good approaches and that in fact
0:31the whole idea of end-to-end learning is
0:33a misguided research agenda.
0:37We need to talk. Welcome to Inside Opt.
0:50Let's start by looking at the typical
0:52setup as we find it in many many
0:55businesses that use optimization.
0:58The data that goes into our optimization
1:01approach, which we
1:03illustrate here by the beautiful rocket,
1:07needs to come from somewhere.
1:09And it usually comes from estimates.
1:12Think about prices, think about demand,
1:16think about traffic times, think about
1:18lead times when you order something,
1:20when it will arrive.
1:21All of these are typically estimates.
1:25And in more sophisticated departments,
1:28you will find that those estimates are
1:30not taken from thin air or simple
1:32statistics over historical data, but
1:34they actually come from a machine
1:36learning model. So, you have the
1:38historical data,
1:40then you build a machine learning model
1:41that that comes up with
1:44a
1:45scenario, a prediction of what might
1:48happen,
1:49and then you take this predicted data
1:51and hand it over to the OR department
1:53and then you get your plan.
1:55Very very common machine learning to
1:58optimization flow as you will find it in
2:01many many organizations.
2:06Now, there is of course that disconnect
2:09that you have here. On the left-hand
2:12side, you have a machine learning
2:14department. On the right-hand side, you
2:15have the OR department. And it's not
2:18just that we're handing over the
2:20predicted data that marks the
2:22delineation between the two departments.
2:25There's also something profoundly
2:26different going on on both sides of this
2:28wall.
2:30The machine learners,
2:31their task is to handle outliers, to
2:34handle errors, to handle bias, missing
2:37values. In one word,
2:39most of what they're concerned with is
2:41uncertainty.
2:43Then they make a prediction and somehow
2:46on the other side of the wall,
2:48everything is beautiful. We have binary
2:51constraints, meaning on the OR side we
2:53can say exactly whether a constraint is
2:56violated or whether it is fine.
2:59We have measurable objectives. We can
3:01look at two different plans and say
3:03exactly and minutely whether one is
3:06better than the other by evaluating the
3:08objective function.
3:10We have fixed coefficients
3:12in the matrix on the right-hand side for
3:14the objective function and in the end
3:17maybe even provable
3:20optimality.
3:22If you look at this picture, you get a
3:24feeling that there must be something
3:26magical happening
3:28when you hand over that data via that
3:31wall cuz somehow all the uncertainty has
3:34vanished.
3:37And that is exactly what those two
3:39approaches, predict and optimize and
3:41predict and optimize, are trying to
3:43reconcile.
3:45So, what's what's the issue? If we look
3:47at our optimization approach here, the
3:50legacy solvers, they want one scenario,
3:53they want one input
3:56of data
3:57and then they're going to produce a plan
4:00and they're going to tell you what the
4:01objective function value for that plan
4:03is. This case here, 1150.098.
4:07Beautiful.
4:09Cuz if you ask the machine learners on
4:13how reasonable it is to do that, they
4:15will say, "Well,
4:17we gave you one example. We gave you the
4:20scenario that you wanted,
4:23right? Like an expected case, for
4:25example. But we know that there are many
4:28different potential futures that could
4:31happen.
4:32So, what we would actually prefer to do
4:35is to give you a distribution of
4:37scenarios. So, each you know, number of
4:40scenarios and each one associated with a
4:42certain probability so that you, when
4:44you make the decision, can come up with
4:46something that's reasonable
4:48for that entire cloud of potential
4:51futures rather than just one of them.
4:54Now,
4:55no matter what you do in order to handle
4:57this because legacy solvers can't just
4:59take in, you know, 10,000 scenarios.
5:02It's not something you can do. You can't
5:03give them a posterior distribution or
5:05samples thereof and then say, "Please
5:07optimize for this."
5:09But no matter what you do in order to
5:12arrive there, and we will discuss
5:13certain ways on how you could handle
5:15this,
5:16or how you might try to handle this, I
5:19should say.
5:20Um no matter what you do, the solution
5:22you're going to get,
5:24yes, the optimizer is going to say,
5:27"Well, this is um for the expected
5:29scenario or whatever we used as input
5:31for our optimizer now is 1150.098,
5:35but in reality, even for that one plan
5:38that you're producing,
5:40the outcomes will vary.
5:43Because
5:44the future that's going to hit you later
5:46is going to vary. And that means you're
5:49going to get with a certain probability,
5:51you're going to get something much less
5:53than 1150 and then with some
5:55probability, you're going to get
5:56something that's maybe closer to 3,000.
5:59And there is a certain
6:01likelihood associated with these
6:03particular outcomes.
6:05We summarize them all by saying, "Well,
6:08we're expecting this to be 1150, but in
6:11reality,
6:12the results for that one plan that you
6:15generated are going to vary."
6:21So, what can we do?
6:24Given the fact that the machine learners
6:26have a whole cloud of potential
6:29scenarios, but our legacy optimizer only
6:32wants one input.
6:34Well, first idea is, how about we take
6:38some scenarios and for each one of those
6:40scenarios, we use our optimizer to
6:43create an optimal plan for that
6:45scenario.
6:47And then we're going to worry about what
6:48plan we're going to to use later.
6:53So, this is what it would look like,
6:55right? So, for every scenario that you
6:57can imagine,
6:58um you know, typically these are macro
7:01scenarios, so take anywhere between 5
7:03and 20. You use your optimizer, you
7:05generate a plan for that respective
7:07scenario, and now you have the problem
7:10that you somehow need to go into this
7:12set of optimal solutions that you found,
7:16optimal for the respective scenario, of
7:18course,
7:19and
7:21generate one that will work
7:23overall.
7:26So, this can be a daunting task. And if
7:28you've ever said in executive meetings
7:31where scenario planning happened, so you
7:34have optimal plans for each one of them,
7:36you know what political discussions can
7:39can unfold um where people start
7:43reasoning about the likelihood of
7:44individual scenarios happening based on
7:46the features that they like or dislike
7:49about the plans that would be optimal
7:50for that respective scenario.
7:53So, it's like an after-the-fact
7:56discussion of, "Well, I like this
7:58solution. Now I'm going to argue why
8:00it's the right one." Um that can be very
8:03very frustrating um if you're sitting in
8:06in one of those political meetings.
8:10So, let's look at a particular example
8:12on why the whole idea is rather strange.
8:16Um this is of course a contrived
8:18example, but it perfectly illustrates
8:20the point.
8:21So, let's say here,
8:23um we have a stochastic linear program.
8:26And it's a very simple linear program
8:27with just two variables. We have two
8:30constraints, 10x + y is lower equal to
8:321,000, x + 1,000y is lower equal to
8:351,000, x and y are greater or equal to
8:380. The feasible region here is basically
8:40everything between 0 and 1, except that
8:43this point here isn't 1 1, but 0.999 and
8:470.999 and then some.
8:50Right?
8:52Now, what makes this LP stochastic?
8:55Well, we don't know
8:57what we are supposed to optimize for.
9:00Um with probability 1/2, we might have
9:03to optimize for y and with probability
9:051/2, we might have to optimize for x.
9:09So, we have two scenarios, not more, two
9:11scenarios, two variables, very simple,
9:14right?
9:15Uh everything is symmetric uh in in this
9:18example.
9:19It's really not very complicated.
9:22But we don't know whether we're going to
9:23optimize for x or for y. Now, imagine
9:25that you had created optimal solutions
9:28for the two scenarios that might hit
9:30you.
9:31Well, if you're optimizing for x, well,
9:33a good idea is to set x to 1, right?
9:36Uh and y to 0. And that's doable. You
9:39can do that.
9:41And similarly, if you're supposed to
9:42maximize for y, you're going to set x to
9:450 and y to 1.
9:47Beautiful.
9:49But take any one of those two solutions,
9:52which were optimal for the two scenarios
9:54that can actually happen, any one of
9:56them. And suddenly the expected case
10:00is or the expected result is .5.
10:03And the distribution of outcomes looks
10:05very daunting cuz with 50% you're going
10:08to get one and with 50% you're going to
10:09get nada. Zits, zilch, nothing.
10:13Okay? So, take either one of those two
10:16solutions
10:18and you're going to end up with a very
10:20poor expected value
10:22and at the same time also um a a very
10:26brittle result, right? So, you might be
10:28lucky and you were in the right
10:29scenario, there's 50% chance of that,
10:32but with 50% chance you you're suddenly
10:34ending up with with nothing, right?
10:37Where you were expecting one.
10:40And that even though a compromise
10:42candidate is perfectly available to you.
10:46You could have taken .999 and .999 as a
10:49solution
10:51and it's feasible with respect to both
10:53constraints.
10:54And no matter which scenario later
10:56happens, you're going to get .999.
11:00The only reason why you're not seeing
11:01that is because it's not optimal for
11:04either of the two scenarios. You could
11:07have gone to one instead of .999. And
11:11since you were so greedy
11:13and created the provably optimal
11:15solution for each scenario,
11:17you lack any form of robustness with
11:21respect to the other scenarios that are
11:23there.
11:24Right? So, the the very reason that you
11:26wouldn't forego that 1/1000 that is in
11:29there
11:31made it made it so that you didn't see
11:34that compromise candidate. The optimal
11:36solutions that you're seeing here for
11:38each scenario do not contain that
11:40solution and no matter which one of
11:42those two you're choosing,
11:43you're not really doing well.
11:45Right? This solution here is much much
11:48better, especially if you're in a
11:49business environment.
11:52Now, this is of course a contrived
11:54mathematical example to illustrate the
11:56point that the very fact that you're
11:59optimizing, maybe even to the to the
12:02last bit provable optimality for each
12:04scenario, makes the set of solutions
12:07that you're going to get as a whole very
12:09very brittle.
12:11So, let's have a look at a real example.
12:14So, this this is a network design
12:17problem. Our client here has four
12:19distribution centers already in New
12:21Jersey, in Ohio, in Georgia, and in
12:24California and is thinking of opening
12:27two new ones.
12:29Now, we're running a thousand scenarios.
12:31For the first 500 scenarios, it's a good
12:33idea to open um the two new facilities,
12:37one in Oregon, the other one in
12:38Pennsylvania.
12:41Then we go to the next 500 scenarios and
12:44we find, ah, it would be a better idea
12:46for you went to Pennsylvania and Texas.
12:49So, what we have is
12:51Pennsylvania and Texas or Pennsylvania
12:53and Oregon.
12:55And now, you know, if we if we take
12:57those two solutions, I mean, there were
12:59a thousand scenarios, but we only get
13:00two solutions,
13:02we somehow have to find, well, which one
13:04of them is better.
13:06Well, as it turns out for this data that
13:10we ran here, the optimal solution would
13:12have been to open in Oregon and in
13:16Texas.
13:18So, even though you found that both
13:20optimal solutions wanted to open a
13:22distribution center in Pennsylvania,
13:25for the for the totality of the thousand
13:28scenarios, it's actually a good idea not
13:29to do that at all
13:31and instead to go to the to the other
13:34two options that were on the table,
13:36which were Oregon and Texas.
13:39Okay? So, you get 500 times this
13:42solution A, 500 times solution B, and
13:46somehow the one thing that seemed to be
13:48clear that you're going to open in
13:50Pennsylvania is actually not a good
13:53thing to do. You should just open here
13:55or here. Now, the kicker is, well, if
13:57the data had been slightly different,
14:00you would have still gotten this
14:02solution for the first 500
14:04for the first 500 scenarios and this
14:06solution for the next 500 scenarios, but
14:09now the optimal solution would have been
14:11to open in Pennsylvania and in Colorado.
14:16So,
14:19even though you find common structure
14:21among all feasible solutions, all all
14:23optimal solutions that you have run,
14:26doesn't mean that you should do that,
14:27right? So, as the Pennsylvania example
14:29show you, nor does it mean that
14:32something that was never opened before
14:35wouldn't be a good idea to open
14:38in the compromise as you're building a
14:40compromise scenario for all of the
14:42thousand scenarios.
14:44And that's what we're talking about,
14:45right? You need a compromise candidate
14:48that works against the whole set of
14:50scenarios, not something that was
14:52optimized for one of them.
14:55So, this idea of aggregating multiple
14:57solutions for multiple scenarios is
15:00bonkers.
15:01You should not do that.
15:04Okay. Now, that leaves us with the
15:07obvious other choice, which is, well, I
15:09have all of my different scenarios, but
15:12my solver only wants one.
15:15Fine. I'll somehow aggregate the input
15:18data.
15:19And I can do that, of course, by asking
15:22my machine learning department to please
15:24give me the expected values
15:27for each of the data points that I'm
15:29going to need.
15:30Okay? So,
15:32that is called predict then optimize and
15:36it is fundamentally flawed.
15:39Um so, I mean, what what you're doing
15:41here is this, right? So, you have this
15:43plethora of scenarios, you aggregate
15:45them to one, hand it to the solver, get
15:47one solution, and you're a happy
15:49trooper.
15:50Um this is called predict then optimize,
15:53right? As I was mentioning.
15:55Um and but, you know, it it's it's going
15:57to work and it's in fact the thing that
15:59most companies do.
16:01It's a fundamentally flawed approach.
16:04Why?
16:05Well, before I'm going to run through
16:07another actual example with you
16:09with numbers and everything,
16:11um here's a mental picture that I want
16:13to to open. Think penalty shots in
16:16soccer. If you've never done this, it
16:18means that, you know, somebody gets to
16:20kick the ball against this very big goal
16:23and you put a goalie in there and if
16:25it's in, it's a goal and if if not, then
16:27it's not a goal, right? So, that's a
16:29penalty shot. You're alone against the
16:32goalie and you have a very very good
16:33chance of actually scoring a goal, which
16:36is a big deal in soccer.
16:38Now, we have data. The Economist
16:41actually analyzed 434 individual
16:44penalties
16:45that were shot in 44 World Cups and
16:47European Championships games. Okay? And
16:51you see here that some of them were
16:52misses, right? Where it didn't even hit
16:54the goal. Uh some of them were saves,
16:57right? Where the goalie got them and all
16:59of the other ones are actually in.
17:01Okay? So, now from there, of course, we
17:04can compute
17:06where the average penalty shot will be
17:08sent. And that's what you're asking the
17:11machine learning department to do. They
17:13see this wealth of different outcomes,
17:16but you asked them, would you please
17:19compress this to one scenario?
17:23Well, they have little other choice than
17:25to take the average. So, lo and behold,
17:29here is the average
17:31penalty shot
17:33uh in one of the 44 World Cups and
17:36European Championships um between '76
17:40and 2016. Okay? This is what it looks
17:43like.
17:48Very very boring shot.
17:50Slightly up and into the middle.
17:54Now, if you base your optimal strategy
17:58on that prediction, on that one scenario
18:02that you forced your machine learners to
18:03give you, well, the optimal strategy for
18:06your goalie would be just stay put.
18:08The ball will come straight to you. All
18:10you have to do is take it and you're
18:12going to do this.
18:14We know what the reality of that
18:16strategy looks like. It looks like this.
18:20You're not going to catch a single ball.
18:24Now, you
18:25you know, again, this is in to create a
18:27mental picture in in your head, but this
18:30happens in businesses all the time and
18:33it costs businesses millions of dollars.
18:36So, here's an example. We do inventory
18:38relocation. We have a big warehouse here
18:41somewhere in the port where most of our
18:43inventory is and we can send a truck to,
18:47you know, a warehouse somewhere
18:50somewhere um in the middle of the
18:52country,
18:53which is smaller and we you know,
18:55there's only 110 units. I think these
18:57were air conditionings that we can put
18:59onto the truck.
19:01Costs us $350 to run the truck, but, you
19:04know,
19:08and then it's much much cheaper to
19:11service clients that are in the vicinity
19:13of that smaller warehouse.
19:16Okay? So, if I do this, if I actually
19:19send a unit of product one to this
19:23remote warehouse here
19:24in red, then I'm saving on shipping
19:27costs, I'm saving $10
19:29for each of those products. And for
19:31product two, it's still $5. On the other
19:33hand, if I send it and then it doesn't
19:36get sold within a certain period of
19:37time, then I have to pay overstock
19:40costs, right? So, it costs me money to
19:42actually um put the inventory here into
19:45this remote location. It costs me three
19:47bucks more than it would have cost me at
19:49the at the port to have it there.
19:52And similarly for product two, um I pay
19:55a $2 penalty. Running the trucks cost
19:57350, by the way.
19:59So, now the question is
20:02do we send a truck? And if we do send a
20:04truck, how many of each product are we
20:06going to put in there?
20:08Now, this is obviously a question that
20:09you cannot answer unless you estimate
20:12how many of each product are going to be
20:14sold.
20:16So, let's go to the machine learning
20:18department. And because we don't want
20:21multiple futures, we're going to do
20:23predict and optimize. We're going to ask
20:25them to give us the expected number, the
20:27expected demand for each product
20:31at this remote location.
20:35Now, these guys are awesome. They give
20:37you numbers that are 100%
20:40accurate.
20:41This is correct. For product one, our
20:44expected demand is 19 units. And for
20:47product two, the expected demand is 91
20:51units.
20:53100% correct.
20:55Telling you this right now. There's no
20:57There's no ambiguity here. The expected
21:00demand for product one is 19. The
21:01expected demand for product two is 91.
21:05Beautiful. Let's hand this over to the
21:07OR department.
21:09So, what the OR department is going to
21:11do is going to set up a simple MIP.
21:13Right? So, you have one zero one
21:15variable T, which tells us whether we're
21:17going to run the truck. If we do that,
21:18costs us $350.
21:20And then we have variables P1 and P2,
21:23which tells us well, how much of product
21:24one and how much of product two are we
21:26going to relocate.
21:27Right? If we relocate it and it gets
21:30sold, then we save 10 bucks for product
21:32one, five bucks for product two.
21:33Beautiful. On the other hand, if we have
21:35overage, so we're going to compute
21:38whether something is going to be stuck
21:40in that warehouse, then we have to
21:42subtract the 10 bucks that I just gave
21:44you optimistically. Um
21:47and then pay the three bucks extra for
21:51for the additional storage cost in that
21:53remote warehouse. And similarly for OR
21:55two, we have to subtract the five again
21:57and then the two for the for the
22:00storing.
22:01>> [snorts]
22:01>> And here
22:02you And And of course, you know, the the
22:04total number of units that we can
22:06relocate is bounded by 110.
22:09And we do have our demand estimate here.
22:13Right? So, we're going to get overage if
22:15we're going to send more than 19 units
22:18for product one. And for product two, if
22:21we're sending more than 91 units.
22:24Unsurprisingly, the optimal solution
22:27here is, well, send 19 units of product
22:29one and 91 units of product two. You
22:32expect absolutely no overage, right?
22:35Because this is exactly the exact the
22:37the
22:38expected demand. And you're going to
22:41send the truck. And overall, you're
22:42going to save $295.
22:47Beautiful. Now, we do that.
22:50And
22:51we observe over time how much money
22:53we're actually saving. And it turns out,
22:56well, actually, we're not saving $295
22:59over just serving everything from the
23:01port.
23:03In reality, we're only saving $131.
23:07And to add insult to injury, the local
23:10planner the the manual planner that we
23:11used to have used to send 10 units of
23:14product one and 100 units of product
23:16two.
23:18And this person would get $187 in
23:22savings.
23:24So, what's going on? We had a perfect
23:26forecast. This is the expected number of
23:29units that will be sold as 19 and 91.
23:33And then we we we used those exact
23:36numbers, those correct numbers, and gave
23:38them to the OR department. And they came
23:41back with a provably optimal solution.
23:44There's no discussion about it. This is
23:46the correct solution for that MIP.
23:50And nevertheless, you're getting
23:53you know, the the the the hand planner
23:55makes 40% savings more
23:58than the MIP.
23:59What What's going on here? Well, what's
24:02going on is that nobody bothered to look
24:05at the demand distribution.
24:07Right? You compressed this distribution
24:11and made it one number.
24:1419 units of product one.
24:1791 units of product two.
24:20This is the same thing as taking that
24:21economist data on the penalty shots and
24:24saying, well, the expected penalty shot
24:26will go directly in the middle. It's the
24:27exact same thing.
24:29So, what you see here is that, well,
24:31actually, you know, there is a 90%
24:33chance that you're around 10 and 100
24:37for the demand, right? Product one, 10
24:39units. Product two, 100 units. And but
24:42there's a 10% chance that it flips
24:43because some influencer put out a video
24:46and says, well, I really like product
24:47one, and then suddenly it flips. Right?
24:50So, here we go.
24:51This is the individual
24:53probability density for the two
24:55products. It makes more sense to look at
24:58them
24:59in the joint forecast. So, you can see
25:01here that you're somewhere here around
25:03the diagonal, which is always 110 units
25:06that that you're going to to to sell. Um
25:10but you see that this 10% outlier over
25:12here skews the whole average.
25:16And I told you that those are the
25:17correct averages. It's 19 and 91. But it
25:20skews it
25:22towards this point over here, away from
25:24where 90% of the cases are actually
25:26happening, which are always 10 and 100.
25:30In fact, 19 and 91 never happens.
25:34Right? This is This is not something
25:35that has actually in the cards. This has
25:37never happened before. It's just that
25:39you you kind of skewed this because
25:41sometimes it could be instead of 10 100,
25:43it could be 110.
25:45Okay?
25:46So, if you look at that distribution,
25:49you understand why the discrepancy is.
25:52So,
25:54the curious thing is that the folks who
25:56have these
25:58legacy solvers who say, well, give me
26:00one input and I give you one provably
26:02optimal output, are going to sneer at
26:04you if you're telling them, well, you're
26:06going to use something that doesn't come
26:07with a proof of optimality cuz they will
26:09say, "Ha, what if you're 3% suboptimal?
26:12What if you're 5% suboptimal? You're
26:14losing so much money." Well, turns out
26:17that they just lost you 30%.
26:21Not because the optimization was wrong,
26:24but because it forced that you're
26:27compressing
26:29the the the wealth of futures that could
26:31fit you
26:33into that one scenario forecast.
26:38So, you should definitely
26:40prefer a heuristic solution such as, you
26:43know, for example, 5% suboptimal here
26:45for the actual real model,
26:48you'd still make $177 instead of 131.
26:52You should always prefer heuristic
26:54solution to a realistic model,
26:56particularly a model that can handle the
26:58stochasticity of your problem, over an
27:00exact solution to the approximated
27:03model, which forces you to put one
27:05compressed scenario inside.
27:07Very important to remember that.
27:11So, forget predict and optimize. It is a
27:13destroyer of businesses. It costs you
27:16millions to follow this approach.
27:19Now, people know this. People in OR have
27:21known this for a long time that this is
27:23a terrible idea, even though legacy
27:26optimizer representatives will still
27:28tell you to do exactly that.
27:30I can guess why because they can only
27:33handle one scenario inputs.
27:36So, the idea came up,
27:39what if we kind of skew the input?
27:41So, maybe we can aggregate the whole
27:43thing,
27:44but in such a way that the solver the
27:47the the optimizer is somehow nudged in
27:50the right direction to give you a
27:51solution which would actually do well
27:55against the whole cloud of potential
27:57futures. That is the idea
28:02of end-to-end learning or predict and
28:04optimize. Why is it called end-to-end
28:06learning? Well, you see that before
28:07you're actually doing the real thing.
28:09But it basically means that you know, as
28:12you're looking at the at the history,
28:14right? So, if if you're looking at the
28:15data
28:16and you build a model that makes the
28:18forecast, which you're going to shove
28:19into the optimization model.
28:22As you're doing this, you're going to
28:23modify this model
28:25um here um
28:27taking into account what the regret is
28:31with respect to some of these scenarios
28:33that could have also happened um
28:36when you look at the plan that comes out
28:38if you gave it a certain input.
28:42Right? So, so you do this offline
28:44because I'm making this online makes no
28:46sense at all because it means that you
28:48would actually solve the whole thing.
28:49But you do this offline to somehow bias
28:52the forecasting model in such a way that
28:54it's going to nudge the solver
28:57to give you something that's actually
28:59way more robust than you would get
29:01otherwise. And hopefully get better
29:03performance that way. It's called
29:04predict and optimize. And this process
29:07here of modifying the forecasting method
29:10is called end-to-end learning.
29:14So, we can use the exact same
29:17same example that I just gave you
29:21to show you that this is bonkers. The
29:24whole idea is bonkers to do it this way.
29:26Why?
29:27Look at this example.
29:29Well, naturally, as long as your
29:32forecast is a total demand of 110 units,
29:35which is, you know, historically, that's
29:38always what happened. It's always around
29:39110 units.
29:41No matter what you put there as your
29:43forecasted demand for product one and
29:46product two,
29:47you're going to get as an optimum
29:51that same number.
29:54Let me say that again. Yes, you can
29:56nudge the solver to give you the correct
29:58answer, which is 10 and 100,
30:01by essentially telling the solver, "Hey,
30:04the correct answer would be 10 and 100."
30:08So, what's the point of optimizing if
30:10the machine learning itself has to know
30:13the optimal solution to nudge the solver
30:16properly to give you the right answer?
30:20Forecast would need to predict the
30:22optimal solution if this end-to-end
30:24learning was supposed to be working.
30:27Nuts. It's It's just nuts. I I can't say
30:30it any differently. Now, there's there's
30:33one
30:34case
30:35where you might think, "Hey, you know,
30:37aggregating is actually not a bad idea."
30:39And that is if the uncertainty in your
30:43optimization problem lies purely in the
30:46objective function. Right? So, in this
30:48case here, I use capital C and D in
30:50order to
30:52make clear that these are random
30:54variables, so we don't know exactly
30:57what the profit coefficients for X and
31:00for Y are, and there's no uncertainty in
31:03the constraint structure at all.
31:05Right? Note that before we had
31:06uncertainty in the constraint structure,
31:08right? This the example that we had.
31:10Imagine that that wasn't the case. The
31:11uncertainty lies purely in there. Well,
31:13then mathematically, you can show very
31:15easily that you can move that
31:16expectation directly into the
31:18coefficients of each variable.
31:20Right? So, everything is linear over
31:22here. So, you can put the expectation of
31:25C and the expectation of D in there, and
31:27now if you solve this problem,
31:30by the way, no end-to-end learning
31:31required, right? You You just take the
31:33expectation, you're done with it.
31:35Um
31:36if you if you do that, you're going to
31:38get you're going to get a solution that
31:40maximizes the expected profit. Right?
31:44So, this is for maximizing profit.
31:48But there's one caveat.
31:50And that is
31:52that in business, you
31:53rarely care about just expectations. You
31:57also care about the variability of your
32:00solutions. Remember when I said, well,
32:02whatever solution you're going to get,
32:03you're going to get a distribution of
32:05outcomes, matters a great deal for
32:08businesses. So, in this perfect world,
32:12where everything is linear and our our
32:16uncertainty lies purely in the objective
32:18function, let's look at this example
32:20over here.
32:22So, what what are we supposed to do
32:23here? Essentially, we're supposed to
32:24maximize all the Z eyes. And the Z eyes
32:28basically have to be lower equal one,
32:29but we can make some additional room
32:32here. So, for example, if we set the Y
32:35eyes to minus one, so the Y eyes can
32:38live anywhere between minus one and one,
32:40then Z I could go uh for every I in I1,
32:44Z I could go to two. And similarly, if
32:46we're setting a Y I to one, plus one,
32:51for every I in the other set, um I2, uh
32:55then again, we can set the corresponding
32:57Z eyes to two.
32:59So, we can make additional room by
33:02setting the Y eyes accordingly. Okay? Um
33:06thing is,
33:08we don't know how much it costs us. This
33:10could be a good thing
33:12um if if we're actually um
33:15setting Y I to one or minus one, but we
33:17don't know beforehand because this part
33:20of the objective function gets
33:21multiplied with a
33:23with random coefficients that are drawn
33:27uh from Gaussian distributions with
33:29expected value zero. So, on
33:31expectations, we're expecting the Y eyes
33:33to cost nothing,
33:34but they do have a standard deviation of
33:36one.
33:37Okay?
33:38So, this is the problem. Now, I just
33:41showed it to you mathematically, it is
33:43correct to just take the expected value
33:45for these X's, so just make it zero.
33:48Now, you don't even have any uncertainty
33:50here anymore.
33:52It means you can just maximize the Z
33:54eyes. So, what you're going to do is set
33:56the Y eyes to the corresponding values
33:58all the Z eyes are being set to, and now
34:01you're going to get n twos divided by n,
34:03that gives you two. Right? 2n divided by
34:06n gives two.
34:07And you get an expected value of two.
34:11Okay? That's the optimum for the
34:13expectation that you're going to get.
34:16But look at the variance of your
34:18solution. The variance of this is going
34:20to be n.
34:24So, if you have n variables over here,
34:28you're going to get a a a massive spread
34:32of outcomes
34:34of for your
34:37for your final result. And if this is
34:39somehow profit, right? So, let's say
34:41this is $2 million,
34:43you don't suddenly want to end up with
34:45minus $18 million.
34:48Right? For a business, this is this is
34:50breaking your neck. You can't have that.
34:53So, what you would actually want to do,
34:56depending on how sensitive to risk you
34:58are over here, um what you would
35:00actually like to do is to set the whole
35:03set every Z I to one and set all the Y's
35:07to zero in order to take the risk out of
35:10the equation.
35:12Now, you see this this image that I give
35:15you over here. What is that? Well, we
35:16have n Gaussian variables. And And I
35:19want to challenge your intuition a
35:21little bit.
35:23Yes, these n Gaussian distributed
35:26variables all have an expected value of
35:28zero.
35:29So, now you might think, well, most of
35:31the time I'm going to get something that
35:33is kind of like really close to zero,
35:35and then as I move out here um further
35:39away from the expected case, by the way,
35:42this is really bad terminology, as
35:44you'll see in a moment, um the more
35:46unlikely it gets that I'm going to see
35:48that. The reality is completely
35:51different. What you're going to have is
35:53that you will you will have a an X
35:56vector that has length square root of n.
35:59So, if the if there are 100 Z eyes and
36:01100 Y eyes, you're going to get a length
36:0410 vector
36:06for the X's that will be there, right?
36:08So, square root of 100 is 10.
36:10Um and
36:12most of the probability density is going
36:14to lie on this very, very small shell
36:19out here. Right? So, you kind of you
36:21know what the radius is going to be with
36:23very high probability, and you have
36:25basically no chance, not in your
36:28lifetime, that you're going to ever see
36:31the expected case, quote unquote, where
36:34all the X's would be zero.
36:37Just never happens.
36:39And but But this is the the case that
36:42you were preparing for.
36:45And the shell here,
36:47where those where those vectors actually
36:49are lying, right? So, this is like an
36:51n-dimensional sphere, of course,
36:53that shell is what you should have
36:55prepared for.
36:57Now, think back to the goalie, right?
37:00You have the chance that the ball will
37:01go left, that the ball will go right.
37:03You stayed right in the middle. And this
37:04is exactly what you keep doing when you
37:07use predict and optimize,
37:10um or predict then optimize, because you
37:13you kind of you're nudging the whole
37:15thing in the middle. There's There's
37:17really no other way to nudge this
37:19because you you just don't know where
37:21the X's are going to fall, right?
37:23So,
37:24there you go. You You just cannot
37:26control
37:28for losses
37:30if you whenever you compress the input
37:32data to one scenario, you have no
37:36ability to control the outcome, to
37:38control the risk that is associated with
37:41it.
37:42So, here's another example that
37:44illustrates this very simple two
37:46variables. Essentially, we're supposed
37:48to maximize Y2. So, Y2 is is vertical
37:51and Y1 is horizontal. Um and the
37:54feasible thing here is is a very thin
37:56strip here that goes from minus 60 to
37:58250,
38:00um and then that, you know,
38:02small little tilt here that's taken
38:04away, and the maximum you can do for Y2
38:07is five. Right? So, it's a very thin
38:09strip.
38:10No matter where you're going to go
38:12for any feasible Y1,
38:15you're always going to get an expected
38:17value of five
38:20for this optimization problem.
38:22Right? This
38:23You can't do better than five for this
38:25one here.
38:26You could hope that the Y1 contributes
38:29something, but again, its coefficient is
38:32drawn sample drawn randomly from a
38:35Gaussian with expected value zero. So,
38:38on expectation, you're not going to get
38:39anything else for Y1.
38:43So, where would you going to go?
38:45Where would you go? I mean, if you take
38:46a simplex algorithm to solve this thing,
38:49no matter how you nudge it, you can set
38:51this to zero, you can set this to minus
38:52one, you can set this to plus one. It
38:54doesn't matter where you nudge it,
38:55you're going to end up with one of those
38:57two solutions. Either you're going to be
39:00plus five for Y2 and then whatever that
39:03is here, minus 47 or whatever. Um I'm
39:07sorry, my minus minus 57 or something
39:10like this. Um or
39:12plus
39:14241 or something like this. Um
39:20you're going to get one of those two
39:21corners.
39:23And the right thing to do here, the
39:25right way to control the risk that is
39:27associated with the whole thing, is of
39:30course to put it right here where Y1 is
39:34zero.
39:35Just take out the risk all together. It
39:37doesn't hurt you one bit to do so, and
39:41predict and optimize, even in this super
39:43simplified case where all the
39:45uncertainties in the objective function
39:47and the whole problem is linear
39:49cannot give that solution to you.
39:52Which is why you should forget about the
39:54whole idea of predict and optimize right
39:56now.
39:59So, I mentioned before that in order to
40:02make predict and optimize work in
40:04general, you would have to be able to
40:06predict the solution directly.
40:10Now, in most cases this is not doable,
40:12of course, because you have usually
40:15complex constraint structures and
40:17whatever the machine learning is going
40:18to suggest will likely be infeasible.
40:22So, this is not something that works.
40:23But, the question is, well, what if you
40:25have a problem where the constraint
40:27structure isn't totally crazy?
40:29Couldn't I directly forecast what I
40:33ought to be doing?
40:34Well, let's look at an example of this.
40:37In fact, the example that spawned the
40:39idea of
40:40of starting InsideOut in the first
40:42place. We were participating in a
40:45competition, the H Guy 21 competition
40:48on a price collection TSP.
40:51Um, so, we are supposed to collect the
40:53rewards. We can say which clients we're
40:55going to visit. We have to do that in a
40:57certain time window.
40:59Um, and um, then we have to meet a
41:02cutoff time at the end of the day when
41:04we have to be back. Problem is, we don't
41:06actually know how long it's going to
41:08take us to go from A to B. We were given
41:11a distribution that would tell us how
41:13long that would take.
41:15And then there were two tracks. In track
41:17one, we were supposed to find one tour
41:20that you had to stick to.
41:23You couldn't modify it once you started
41:25it, no matter how the travel times were
41:27evolving during the day. You had to
41:29stick to it. And you were supposed to
41:31come up with a tour that has great
41:33expected value. And then in track two,
41:36we were supposed to learn a policy. We
41:39were supposed to use reinforcement
41:41learning in order to say, "Hey, if
41:43you're in this state, maybe this is the
41:45right client to go to next in order to
41:47pick up a reward." And then, of course,
41:50make sure that you will be back at the
41:51depot at the end of the
41:54of the day.
41:56So, um,
41:57if you use the track one solution where
42:00you're stuck
42:01using the same solution every single
42:03time, no matter how the day unfolds, um,
42:07we could get a solution that is like
42:1010.81, right? So, this is price
42:11collection. So, you wanted to maximize
42:13this whole thing. Um, and this was the
42:16value that you would have. Now, if you
42:18had had perfect clairvoyance for each
42:20instance,
42:21um, where you know beforehand these will
42:24be the travel times that are going to
42:25hit you, well, then you could have
42:28computed a the best tour for every
42:31single day for every scenario that was
42:33there, right? So, there's a theoretical
42:35maximum what you can achieve.
42:37Now, you would expect that the track two
42:39solution, reinforcement learning, which
42:41can adapt its solution with more
42:44information how long it did actually
42:46take to get so far, right? That that
42:49solution would be able to, you know, lie
42:52somewhere here between the Uncle Otto
42:55solution, which stubbornly always takes
42:57the same tour no matter how late it
42:59gets,
43:00um, and the perfect clairvoyant
43:03solution.
43:04Right? Somewhere in between here you
43:05would expect the reinforcement learning
43:07to lie.
43:08And we submitted the the solution to
43:10this, um,
43:13uh, which won the competition. So, we
43:15did something that was very close to the
43:16state of the art. A deep learning base,
43:18we used an instance graph encoding. Um,
43:21we did active learning. We wouldn't
43:22just, you know, just take the whole
43:24thing. We did rollout, so there was
43:26dynamic search involved. And
43:28nevertheless,
43:29the reinforcement learning that we
43:31submitted
43:32would only get us to 10.7734.
43:36Now, we knew that before we submitted
43:38it, which is why we asked the, uh,
43:41competition organizers whether we could
43:43also just, you know, do a very simple
43:46policy, which is like, well, stick to
43:47Uncle Otto.
43:49Um, they I wasn't allowed. So, they
43:51said, "No, it has to be reinforcement
43:53learning. You have to submit the code
43:55and everything." So, we had to do that,
43:57even though we knew that just sticking
43:59to a stupid default was better than
44:02reinforcement learning. So, now the
44:03question is, why is that? I mean, this
44:05is the perfect application scenario for
44:07reinforcement learning. There are no
44:09crazy side constraints that would
44:11suddenly say, "Oh, your solution isn't
44:12isn't isn't good." Nothing.
44:15Well, it is because the reinforcement
44:17learning is sometimes amazingly good. It
44:20it it just, you know, for many of those
44:22instances, it just found a perfect tour
44:25for them.
44:27But, every now and then it screwed up so
44:29tremendously
44:31that it was just too brittle to work
44:33robustly. And that is what ruined the
44:36the average performance in the
44:38reinforcement learning.
44:39Right? So, for the time being at least,
44:43even if you're in a in a scenario where
44:45you don't have complex side constraints
44:48to deal with and things that just
44:49require you to do to use optimization,
44:52trying to forecast the optimal action
44:54directly with machine learning
44:57is a very bad idea
44:59due to the brittleness of, uh,
45:01reinforcement learning.
45:03So, forget about predicting the solution
45:06directly. Either you need optimization,
45:09you need to use search in order to find
45:11good plans.
45:13So, what's left?
45:14What what can we possibly do? Well, we
45:17have to break out of the confines of
45:19legacy solvers, which would only take
45:21one input.
45:23What you actually want to do is this.
45:25You want to maximize in the feasible
45:28space some non-linear function and then
45:31some aggregation thereof, right? So,
45:33remember that this function here under
45:35the,
45:36uh, under the different scenarios that
45:38can hit you will have a variability to
45:41it. No matter which plan you're going to
45:43choose,
45:45even if you use a legacy optimizer, even
45:47if you do predict and optimize, you are
45:49going to be hit with a variable outcome,
45:52right? So, okay, now you get to decide
45:56which outcome you want to optimize for.
45:58Is it the expected value?
46:01Is it the expected plus one standard
46:03deviation? Is it the CVaR 5%? Right? It
46:07is up to you to do that, which is why
46:08sometimes we actually write it like
46:10this, right? So, use some aggregator
46:12over your objective function, which can
46:14be non-linear and whatever you want.
46:17Right? This is what you want to be
46:18doing. You want your solver to be able
46:22to look at all of these scenarios as
46:24input and evaluate each course of action
46:28each course of action internally
46:31when weighing the different options that
46:33are available to then spit out one good
46:37compromise candidate that is going to
46:39work well against this cloud of
46:40solutions.
46:42And that is what InsideOut Seeker is
46:45going to give you.

About this transcript

This page contains the full transcript of Why predict-then-optimize and end-to-end learning won't fix your optimization under uncertainty. by InsideOpt Tutorials, generated from the public captions YouTube serves with the video. The transcript has 7,184 words across 1,183 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.