# Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems

arXiv: https://arxiv.org/abs/1911.10092 · HTML: https://mlsanity.com/paper/1911.10092/

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2019.

## Built on by (most cited first, 30 of 89)

- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Decision-Focused Learning: Through the Lens of Learning to Rank](https://mlsanity.com/paper/2112.03609/) (2021)
- [PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming](https://mlsanity.com/paper/2206.14234/) (2022)
- [Learning with Combinatorial Optimization Layers: a Probabilistic Approach](https://mlsanity.com/paper/2207.13513/) (2022)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [Alternating Differentiation for Optimization Layers](https://mlsanity.com/paper/2210.01802/) (2022)
- [Learning Hard Optimization Problems: A Data Generation Perspective](https://mlsanity.com/paper/2106.02601/) (2021)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method](https://mlsanity.com/paper/2110.06365/) (2021)
- [Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspective](https://mlsanity.com/paper/2304.06833/) (2023)
- [Efficient differentiable quadratic programming layers: an ADMM approach](https://mlsanity.com/paper/2112.07464/) (2021)
- [End-to-end Learning for Fair Ranking Systems](https://mlsanity.com/paper/2111.10723/) (2021)
- [Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information](https://mlsanity.com/paper/2307.08964/) (2023)
- [End-to-end Conditional Robust Optimization](https://mlsanity.com/paper/2403.04670/) (2024)
- [Utility-Directed Conformal Prediction: A Decision-Aware Framework for Actionable Uncertainty Quantification](https://mlsanity.com/paper/2410.01767/) (2024)
- [Scalable Decision-Focused Learning in Restless Multi-Armed Bandits with Application to Maternal and Child Health](https://mlsanity.com/paper/2202.00916/) (2022)
- [Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses](https://mlsanity.com/paper/2203.16067/) (2022)
- [Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.04862/) (2022)
- [Neuro-algorithmic Policies enable Fast Combinatorial Generalization](https://mlsanity.com/paper/2102.07456/) (2021)
- [Neuro-Symbolic Constraint Programming for Structured Prediction](https://mlsanity.com/paper/2103.17232/) (2021)
- [Score Function Gradient Estimation to Widen the Applicability of Decision-Focused Learning](https://mlsanity.com/paper/2307.05213/) (2023)
- [TaskMet: Task-Driven Metric Learning for Model Learning](https://mlsanity.com/paper/2312.05250/) (2023)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning](https://mlsanity.com/paper/2411.19285/) (2024)
- [Dissecting the Impact of Model Misspecification in Data-driven Optimization](https://mlsanity.com/paper/2503.00626/) (2025)
- [Decision Focused Causal Learning for Direct Counterfactual Marketing Optimization](https://mlsanity.com/paper/2407.13664/) (2024)
- [Solver-Free Decision-Focused Learning for Linear Optimization Problems](https://mlsanity.com/paper/2505.22224/) (2025)

## Abstract (arXiv)

Combinatorial optimization assumes that all parameters of the optimization problem, e.g. the weights in the objective function is fixed. Often, these weights are mere estimates and increasingly machine learning techniques are used to for their estimation. Recently, Smart Predict and Optimize (SPO) has been proposed for problems with a linear objective function over the predictions, more specifically linear programming problems. It takes the regret of the predictions on the linear problem into account, by repeatedly solving it during learning. We investigate the use of SPO to solve more realistic discrete optimization problems. The main challenge is the repeated solving of the optimization problem. To this end, we investigate ways to relax the problem as well as warmstarting the learning and the solving. Our results show that even for discrete problems it often suffices to train by solving the relaxation in the SPO loss. Furthermore, this approach outperforms, for most instances, the state-of-the-art approach of Wilder, Dilkina, and Tambe. We experiment with weighted knapsack problems as well as complex scheduling problems and show for the first time that a predict-and-optimize approach can successfully be used on large-scale combinatorial optimization problems.