发表在 Management Science, 2022. DOI: https://doi.org/10.1287/mnsc.2020.3922.
Area of review: optimization.
Key words: prescriptive analytics; data-driven optimization; machine learning; linear regression
This paper proposes a general framework called Smart “Predict, then Optimize” (SPO).
Let $D_x$ be the conditional distribution of the objective $c$, given the feature vector $x \in \mathbb{R}^p$. The classic “Predict, then Optimize” (PO) framework solves $$ \min _{w \in S} \mathbb{E}_{c \sim \mathcal{D}_x}\left[c^{\top} w \mid x\right]=\min _{w \in S} \mathbb{E}_{c \sim \mathcal{D}_x}[c \mid x]^{\top} w $$ where the decision variable $w$ and feasible region $S \in \mathbb{R^d}$ is known with certainty.
$$ \begin{aligned} P(c): \quad z^\ast(c):=& \min _w c^T w \\ & \text { s.t. } w \in S, \end{aligned} $$
Definition (SPO Loss)
Given a cost-vector prediction $\hat{c}$ and a realized cost vector $c$, the true SPO loss $\ell_{\mathrm{SPO}}^{w^\ast}(\hat{c}, c)$ with respect to optimization oracle $w^\ast(\cdot)$ is defined as $$ \ell_{\mathrm{SPO}}^{w^\ast}(\hat{c}, c):=c^T w^\ast(\hat{c})-z^\ast(c) $$
Definition (Unambiguous SPO Loss)
Given a costvector prediction $\hat{c}$ and a realized cost vector $c$, the (unambiguous) true SPO loss $\ell_{\mathrm{SPO}}(\hat{c}, c)$ is defined as $$ \ell_{\mathrm{SPO}}(\hat{c}, c):=\max _{w \in W^{\ast}(\hat{c})}\left\{c^T w\right\}-z^\ast(c) $$