In response to a previous puzzle, we received this comment:
Some time ago, UPS built a model to determine how many planes they would need to handle their overnight network. They had 3 scenarios: "high demand," "medium demand," and "low demand." The OR team solved the problem under each of those scenarios. These decisions cost hundreds of millions of dollars—the problem is how many planes to buy/lease, which are quite expensive.
The OR team then presented a 3 by 3 matrix. On one axis was "the decision" made under each scenario. The other axis was "the outcome" realized under each scenario after the decision was made. In each of the 9 boxes were various KPIs. For example, under a low-demand scenario that you planned for, but the high-demand scenario was realized, you'd be hurting service.
They then presented this matrix to the C-level executives and said, "You decide." The insight of those executives on the tradeoffs of cost vs. service was something the OR team did not want to place into a model.
This week, let us look at a very innocent two-variable LP with three different profit scenarios. The uncertainty is only in the objective. These problems are easy to solve under uncertainty when aiming to maximize expected profit by simply weight-aggregating all scenarios into one.
The situation changes when we are risk-averse and we do not want to maximize the expected profits but the worst-case profits.
Our LP:
Maximize a*x + b*y
s.t.
- x+2y <= 4
- 441x + 504y <= 1030
- 19x + 10y <= 38
- 0 <= x,y <= 2
- (a,b) in {(0.5,1), (1,1), (1,0.5}
Use the methodology suggested by our reader to decide what would be the best solution.
Then think what you would do when you were facing this problem, and each scenario could realistically happen, but you have no probability to work with. Your objective is to set values for x and y that will maximize the worst case.
Assume that the three scenarios really mean that we hope profit for both x and y will be at 100%, but that we foresee some chance that one (but not both of them) might dip, possibly all the way to 50%. What is a rational solution?
We suggest setting x=1.287 and y=0.918.
This solution will likely surprise as
- It is sub-optimal for all three scenarios, and
- It does not maximize the worst case.
However, if we assume that the provisioning of those three scenarios really meant that we hope to see both x and y at 100% profit but foresee a chance that one of the two might dip, potentially all the way to 50%, but possibly less, then the solution provided gives an expected value of 1.93 while keeping the conditional value at risk-10% at 1.63. It thereby represents a rational compromise between our objective to maximize expected profits while keeping the associated risk under control.
Let us compare this solution with the following alternatives:
- Solution 1: x=0, y=2. Maximizes scenario 1.
- Solution 2: x=1.71, y=0.54. Maximizes scenario 2.
- Solution 3: x=2, y=0. Maximizes scenario 3.
- Solution 4. x=1.09, y=1.09. Maximizes the worst possible outcome.
- Solution 5. x=1.12, y=1.07. Maximizes CVAR-10%.
- Solution 6. x=1.29, y=0.92. Our suggested solution.
We can evaluate all solutions on all three scenarios, plus the expected value if all scenarios are equally likely, when the (1,1)-profit scenario is more likely than the dipping scenarios, or when allowing an infinite number of scenarios where we uniformly choose the level of profit loss, from profit 100% down to 50%, whereby we choose which component will dip uniformly at random.
We observe that the three solutions that each optimize one scenario in isolation show significant losses when compared to Solutions 4, 5, and 6. Especially the extreme Solutions 1 and 3 are brittle. Optimizing the CVAR-10% (Sol 5) and maximizing the worst case (Sol 4) yield almost the same result on this problem. By multi-objectively optimizing both expected returns and the CVAR-10% (Sol 6), we reach a rational compromise, maintaining a good upside when compared with Sol 2, while managing the risk of Scenario 1 occurring.
The diagram below shows some interesting facts:
- None of the solutions 4, 5, or 6 is a corner of the feasible polytope.
- As a consequence, none of the solutions 4, 5, or 6 can be found by linearly aggregating the different scenario objectives.
- None of the solutions 4, 5, or 6 is a convex combination (where we assign a percentage to each solution 1, 2, or 3) of the solutions to each individual scenario. This is evident by the fact that solutions 4, 5, and 6 are all outside the convex hull of solutions 1, 2, 3.
- None of the solutions 4, 5, or 6 is optimal for any scenario.
The most important point, though, is this. Even when our estimates of the individual scenario probabilities are somewhat off, the solutions obtained by incorporating all scenarios will still yield good results, as we can see by the robust performance against E(uniform), E(1/4,1/2,1/4), and E(continuous).
We find that this is generally the case: Ignoring the fact that there is uncertainty in the model data is a terrible mistake that can easily cost millions of dollars.
However, the exact distributions of the uncertain data matter far less. As long as the potential futures that we expose to the solver cover the reality that we may face later, and we control for risk, then the solutions we obtain will work robustly in practice. The best part: We can control how much insurance we want to buy.
Here is the Seeker Colab that shows how.