# Divide and Learn: A Divide and Conquer Approach for Predict+Optimize

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2020.

## Built on by (most cited first, 2 of 2)

- [Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses](https://mlsanity.com/paper/2203.16067/) (2022)
- [Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach](https://mlsanity.com/paper/2505.11360/) (2025)

## Abstract (arXiv)

The predict+optimize problem combines machine learning ofproblem coefficients with a combinatorial optimization prob-lem that uses the predicted coefficients. While this problemcan be solved in two separate stages, it is better to directlyminimize the optimization loss. However, this requires dif-ferentiating through a discrete, non-differentiable combina-torial function. Most existing approaches use some form ofsurrogate gradient. Demirovicet alshowed how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. How-ever, their approach is restricted to optimization problemswith a dynamic programming formulation. In this work wepropose a novel divide and conquer algorithm to tackle op-timization problems without this restriction and predict itscoefficients using the optimization loss. We also introduce agreedy version of this approach, which achieves similar re-sults with less computation. We compare our approach withother approaches to the predict+optimize problem and showwe can successfully tackle some hard combinatorial problemsbetter than other predict+optimize methods.