Wake up, OR Community

It is becoming more and more painful to see how OR is limping behind.

This article is a great example. I hope the author and authors cited will not take my criticism the wrong way. My heart beats for OR, ever since I attended my first linear programming course. And that is precisely why I expect more from my home community. A 6-step plea for action:

1. Yes, ML and OR are a necessary combination; most industrial problems require these disciplines to combine their artefacts into data analysis pipelines that produce actionable plans.

2. If we agree on the above, why on earth is the deterministic optimization problem still what we teach our students (note that I am not the only person being bamboozled by this, see, for example, the posts by Warren Powell)? Let us face it, deterministic optimization is a rare exception and not the norm. Yet we cling to it like scared children to their parents.

Examples of standard OR problems that (almost) no one has:

• TSP: Travel times and processing times at nodes are stochastic in real life.
• Production Planning: Demand and processing times are stochastic.
• Network Design: Future operating and transportation costs and demands are inherently uncertain.

3. If we accept the reality that data feeding into our OR models from ML pipelines is estimated and inherently uncertain/stochastic, then we have two directions we can take (note that they are not excluding each other):

A. We can improve our dual methods to provide tight dual bounds for models with stochastic objectives and side constraints. In this case, our current approach to solving optimization problems by search and dual inference may be viable.

B. We devise highly efficient primal approaches that provide extremely good solutions for stochastic problems.

4. In the article at hand, an example is given of how we can use ML in a dual method by improving branching decisions. Yes, we can, but this avenue has been pursued for over a decade and, frankly, has not led to noteworthy improvements in solving deterministic problems. The also-mentioned portfolios do have a massive effect on solver performance, though, but the ML method to be used is cost-sensitive hierarchical clustering, which performs highly efficient, cost-sensitive classification. However, both methods do nothing to address the elephant in the room, and that is the need to deal with stochasticity. For dual methods, this would mean we need efficient and tight dual bounds facing hundreds of thousands of scenarios. This ought to be the focus of the research agenda for dual methods, not branching or portfolios.

5. As a primal method, RL keeps being pursued and mentioned a lot when it comes to ML/OR hybrids. Look at the following facts from the 2021 IJCAI AI4TSP competition, where the objective was to solve a (prize-collection) TSP with uncertain travel times.

A. In track one of the competition, where one tour had to be found that could not be altered during its execution, a primal approach won.

B. In track two of the competition, the tour could be altered during execution, and an RL approach had to be devised to learn a policy for where to go next. A POMO approach including active learning and rollouts won this track.

C. Clearly, being allowed to alter the tour offers the potential to do much better than to stubbornly cling to the originally suggested tour.

D. The approach that won track 1 outperformed the RL, even though it was so severely limited in what it was allowed to do. Why? Because RL managed to bring itself into situations it had never encountered during training. Plain and simple, RL by itself is too unreliable.

The focus of the research agenda regarding primal methods should be how we can adjust primal heuristics, feasibility pumps, local search, etc, so that they can provide near-optimal solutions for stochastic problems with hundreds of thousands of scenarios.

6. Where do we stand when a current article published by the Informs Society lists better branch-and-bound by means of ML and RL as two showcases of state-of-the-art ML/OR hybrids? We need to rise to the occasion and finally address the real problems of this world. It is crying for efficiency, and OR has a crucial role to play. But we will not get there if we do not dare to think OR completely new, namely as decision science where making robust decisions based on uncertain data is the name of the game.