Whenever I discuss with colleagues the topic of stochastic optimization, there always has been an image coming to my mind: that of a sandwich (or more of a burger, for culinary precision).
As odd as it sounds, I had the feeling that this may help illustrate some of the difficult notions with regard to optimality in optimization under uncertainty. In particular the gap that often lies between the optima with and without perfect foresight (perfect knowlegde of futur events, which are otherwise supposed uncertain in stochastic optimization). This gap is known as EVPI (Expected Value of Perfect Information) in the Stochastic Programming literature.
Although I already have a slide deck for my short introductory course on the topic (EVPI comes at p. 52/85), I realized I had never materialized this “sandwich illustration”, except transiently on a white board. Today, as I have so many other things to finish, I finally opened Inkscape to make a first version. I’m not sure it’s that meaningful without an explanation, but I find it decent. It should find its place in next year’s version of the slides.
Some explanations
The illustration encodes two ideas:
- Sandwich: Stochastic Programming theory states that the values of three typical solutions of the stochastic optimization problem are ordered, thus they can be stacked as in a sandwich. Here there are, sorted from the best to the worst (sandwich bottom, middle and top)
- the “best ever solution”, which assumes perfect foresight, which is cheating on the stochastic aspect of the problem
- the genuine best solution, coming from Stochastic Programming, which truly respect the fact that foresight is limited (only a probabilistic knowledge of the future is assumed)
- the “deterministic forecast heuristic” solution, where the problem is solved by replacing each uncertain quantity by its forecasted (expected) value
- Different flavors: theory further states that the performance of these three variants are ranked, but only with non-strict inequalities (≥, not >), so that it may be the case, on a particular problem, that the perfect foresight solution is no better than the imperfect foresight solution (in the domain jargon: EVPI = 0). This implies it is not worth investing resources on finding better forecasts of uncertain quantities. Same, when comparing the deterministic heuristic solution with the stochastic solution: the gap between the two (called VSS, for Value of the Stochastic Solution) can be zero in some cases, so that the application the fancy stochastic programming method brings no benefit. The fact that the EVPI and VSS layers (certainly tasty ingredients, although I have never tasted them...) in the sandwich can disappear makes up for the different flavors.