Smart "Predict, then Optimize"

By Adam N. Elmachtoub, Paul Grigas. 2017

889 citations recorded by the source corpus.

Many real-world analytics problems involve two significant challenges: prediction and optimization. Because of the typically complex nature of each challenge, the standard paradigm is predict-then-optimize. By and large, machine learning tools are intended to minimize prediction error and do not account for how the predictions will be used in the downstream optimization problem. In contrast, we propose a new and very general framework, called Smart “Predict, then Optimize” (SPO), which directly leverages the optimization problem structure—that is, its objective and constraints—for designing better prediction models. A key component of our framework is the SPO loss function, which measures the decision error induced by a prediction. Training a prediction model with respect to the SPO loss is computationally challenging, and, thus, we derive, using duality theory, a convex surrogate loss function, which we call the SPO+ loss. Most importantly, we prove that the SPO+ loss is statistically consistent with respect to the SPO loss under mild conditions. Our SPO+ loss function can tractably handle any polyhedral, convex, or even mixed-integer optimization problem with a linear objective. Numerical experiments on shortest-path and portfolio-optimization problems show that the SPO framework can lead to significant improvement under the predict-then-optimize paradigm, in particular, when the prediction model being trained is misspecified. We find that linear models trained using SPO+ loss tend to dominate random-forest algorithms, even when the ground truth is highly nonlinear. This paper was accepted by Yinyu Ye, optimization.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Learning When-to-Treat Policies (2019, methodology): “…data to help inform how and to whom interventions should be applied (Manski 2004; Zhang et al. 2012; Zhao et al. 2012; Dudík et al. 2014; Swaminathan and Joachims 2015; Elmachtoub and Grigas 2017; Kallus and Zhou 2018; Kitagawa and Tetenov 2018; Athey and Wager 2020; Bertsimas and Kallus 2020).”
Strong mixed-integer programming formulations for trained neural networks (2018, background): “Broadly, our work fits into a growing body of research in prescriptive analytics and specifically the “predict, then optimize” framework, which considers how to embed trained machine learning models into optimization problems [11,12,17,18,24,28,39].”
Forecasting: theory and practice (2020, background): “…problems, they are usually treated separately (Elmachtoub and Grigas, 2017), though there are now recent works where they are considered together (Elmachtoub and Grigas, 2017; El Balghiti et al., 2019; Demirovic et al., 2019), and this will certainly be an interesting avenue for future research.”
Tackling Climate Change with Machine Learning (2019, neutral): “[59] Adam N Elmachtoub and Paul Grigas.”
Market Segmentation Trees (2019, methodology): “Elmachtoub et al. (2020) trains decision trees for use in the predict-then-optimize framework (Elmachtoub and Grigas 2022), which requires modifying the loss function to an optimization problem (rather than a choice model as in this work).”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, positive): “In this section, we summarize the predict-then-optimize framework and the SPO loss proposed in Elmachtoub and Grigas (2017).”
Differentiation of Blackbox Combinatorial Solvers (2019, positive): “A related mindset of learning inputs to an optimization problem gave rise to the “predict-and-optimize” framework and its variants (Elmachtoub & Grigas, 2017; Demirovic et al., 2019; Mandi et al., 2019).”
Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer (2019, background): “For example, Elmachtoub and Grigas [20] propose the ”Smart Predict-and-Optimize” where the authors present a framework to leverage the optimization problem structure and test on the shortest path problem (5×5 grid) and portfolio selection problem (50 assets).”