2020/12/04 by Ali Ugur Guler, Emir Demirović, Guler, Ali Ugur +9 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2012.02342
openalex publication_date 2020/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.