The Interplay between Operations Research and Machine Learning

In recent years, applications of artificial intelligence (AI) have become ubiquitous and part of our everyday lives. From the minute we wake up and check the latest social media feeds on our cell phones to the moment we tell Alexa to set the alarm before going to bed, we are subjected to products and services in which AI plays a key role. In 2021, organizations across the globe invested more than US$90 billion in AI [1].

AI solutions are based on different methods across several subfields, predominantly in the area of machine learning (ML). ML has been of particular interest to a vast number of researchers of various disciplines, and the number of ML publications has grown substantially in the past decade. A large number of operations research (O.R.) scholars have been attempting to explore the interplay between O.R. and ML in distinct forms. In fact, the number of contributions in INFORMS journals/publications containing the string “machine learning” has been increasing exponentially in the past few years, as shown in Figure 1.

Given the above, one might ask: Do O.R. scholars genuinely believe that O.R. and ML make a perfect match, or are they deliberately finding ways to accommodate ML approaches into their papers to make them more appealing? Moreover, is this tendency the result of genuine discovery of new topic areas, or is it the result of funding agencies’ focus on ML topics and an attempt by O.R. folks to fit in? Are we seeing the evolution of our field that is here to stay, or are editors and reviewers of O.R.-related journals more keen to welcome articles that are more trendy and full of buzzwords over those that are closer to the O.R. roots?

Either way, it seems that a considerable portion of the O.R. scientific community has found ways to combine O.R. and ML in their research work. It is thus no surprise that this is a topic of regular discussion on the “Subject to” (s.t.) podcast. In what follows, we highlight examples of where O.R. and ML go hand in hand, supporting the hypothesis that the combination is proving extremely advantageous and makes for valuable contributions of the O.R. community.

Machine Learning and Optimization

Many modern data applications operate under a paradigm that can be characterized as “predict-then-optimize.” The “predict” part comes from an ML model that predicts probabilities or regression outcomes and feeds them into an optimization model, which makes coordinated decisions. Often, the two parts are disconnected, with the ML model handing off parameters to the optimization model. Nevertheless, combining the two can be powerful in practice. For example, Elmachtoub and Grigas show that leveraging the optimization problem structure (i.e., its objective and constraints) can help design better prediction models through the development of new loss functions [2]. Moreover, Donti et al. [3] include the characteristics of stochastic optimization problems directly into neural network loss functions by differentiating the optimization solution. This results in more aligned ML and optimization models, and thus in better decision outcomes. In fact, Dimitris Bertsimas summarizes the natural codependency and interconnectedness of ML and optimization when defining analytics as “the science of using data to build models for better decisions” [4].

ML algorithms can also directly benefit from optimization. In particular, ML methods such as random forests can be made more interpretable using optimization, or support vector machines can be enhanced through column generation, as discussed by Dolores Romero Morales [5]. As Thibaut Vidal mentions, there are a lot of hidden heuristics in ML, for example, in the classification and regression tree algorithm (CART) for decision trees or in k-means clustering [6].

Another promising combination is integrating optimization and causal inference to learn optimal interpretable policies, for example, in resource allocation for the homeless, as Phebe Vayanos points out [7]. On a more general level, Vidal highlights another case for how ML can benefit from the O.R. toolkit: In O.R., we decompose problems into the model and solution technique, whereas in ML, these two are often thought of as one. This lens of decomposition can potentially yield more systematic development of solutions for a wide range of problems. 

Not only can ML benefit from optimization – it also works the other way around: Optimization solvers can take direct advantage from ML methods, and many of the state-of-the-art solvers today employ ML internally. For example, ML can be embedded into mixed-integer quadratic optimization solvers to help decide when to linearize, or embedded into discrete optimization solvers to make promising branching decisions, as highlighted by Andrea Lodi [8]. In some cases, the ML community is trying to replace optimization entirely, for example, to solve the capacitated vehicle routing problem. Here, it is important that ML solutions are compared to state-of-the-art O.R. solutions so that the scientific community does not reinvent the wheel [9, 10]. 

Another example of optimization turning ML to its advantage is the development of surrogate ML models to learn the optimal solution of an optimization model as a function of its parameters. An impactful application is in the security-constrained economic dispatch to clear electricity markets, work that Pascal Van Hentenryck elaborates on in a forthcoming s.t. episode [11]. These models run in electricity markets worldwide with an impact on the order of billions of dollars per year [12], and the requirement to run the dispatch optimization models every five minutes limits the modeling detail. By learning a surrogate model of the optimization model, results can be returned instantly. Because the runtime requirement of the optimization model becomes less stringent, this enables the development of much more powerful optimization models to clear electricity markets.  

These are all great examples of how ML and optimization can be combined. But more broadly, what is the impact of the exponential growth around ML on the interest of students to study mathematical optimization and O.R. [13]? Are they drawn into other fields instead of O.R., or does the hype increase overall interest? Eduardo Uchoa points out that ML has a low barrier of entry compared with O.R. [14]. However, it is likely a balance of push and pull. On one hand, O.R. as an ML-adjacent field receives more exposure than without the recent hype. On the other hand, many bright O.R. scholars may be tempted to leave academia to pursue a career in the ML industry.

Overall, the strong interest in ML is a wonderful opportunity for the O.R. community to bring new attention to our field. O.R. has provided impactful analytics for more than 60 years. However, because in the past decade a vast number of applications of AI and ML have changed the world of analytics, the field of O.R. is also evolving, becoming more data-driven and more intertwined with predictive analytics. We have only scratched the surface, and many new research and application areas in which ML and O.R. go hand in hand have yet to be discovered, with significant opportunities for the O.R. community to bring ways of thinking to the table that no other community can contribute.

References

1. https://www.statista.com/statistics/941137/ai-investment-and-funding-worldwide/
2. Adam N. Elmachtoub and Paul Grigas, 2022, “Smart ‘Predict, then Optimize,’” Management Science, Vol. 68, No. 1, pp. 9-26.
3. Priya L. Donti, Brandon Amos and J. Zico Kolter, 2017, “Task-based end-to-end model learning in stochastic optimization,” Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS’17), https://dl.acm.org/doi/10.5555/3295222.3295300.
4. Dimitris Bertsimas, s.t. episode: https://www.youtube.com/watch?v=cifspW4gLwA&t=1513s
5. Dolores Romero Morales, s.t. episode: https://www.youtube.com/watch?v=rn4zFZCwsrE&t=3080s
6. Thibaut Vidal, s.t. episode: https://www.youtube.com/watch?v=oqWlANvtviU&t=3415s
7. Phebe Vayanos, s.t. episode: https://www.youtube.com/watch?v=9OtCbznTCJA&t=3022s
8. Andrea Lodi, s.t. episode: https://www.youtube.com/watch?v=6JHr3dS1630&t=3202s
9. https://www.amazon.science/academic-engagements/winning-last-mile-challenge-team-addresses-problem-of-combining-mathematical-routes-with-driver-knowledge
10. https://uwaterloo.ca/combinatorics-and-optimization/news/bill-cooks-team-announced-winner-amazon-last-mile-routing
11. Pascal Van Hentenryck, s.t. episode: https://www.youtube.com/watch?v=gZ5Dlu9vnz4&t=4553s
12. https://www.ferc.gov/sites/default/files/2020-04/acopf-1-history-formulation-testing.pdf
13. Jeff Linderoth, s.t. episode: https://www.youtube.com/watch?v=z82R6pI__wg&t=2813s
14. Eduardo Uchoa, s.t. episode: https://www.youtube.com/watch?v=9mNjqkUIZRk&t=3242s