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

Divide and Learn: A Divide and Conquer Approach for Predict Optimize Authors Ali Ugur Guler, 1 Emir Demirovic, 2 Jeffrey Chan, 3 James Bailey, 1 Christopher Leckie, 1 Peter J. Stuckey, 4 1 University of Melbourne, 2 Delft University of Technology, 3 RMIT University, 4 Monash University aguler@student.unimelb.edu.au, Abstract The predict optimize problem combines machine learning of problem coefficients with a combinatorial optimization problem that uses the predicted coefficients. While this problem can be solved in two separate stages, it is better to directly minimize the optimization loss. However, this requires differentiating through a discrete, non-differentiable combinatorial function. Most existing approaches use some form of surrogate gradient. Demirovic et al showed how to directly express the loss of the optimization problem in terms of the predicted coefficients as a piece-wise linear function. However, their approach is restricted to optimization problems with a dynamic programming formulation. In this work we propose a novel divide and conquer algorithm to tackle optimization problems without this restriction and predict its coefficients using the optimization loss. We also introduce a greedy version of this approach, which achieves similar results with less computation. We compare our approach with other approaches to the predict optimize problem and show we can successfully tackle some hard combinatorial problems better than other predict optimize methods. Introduction Machine Learning ( ML) has gained substantial attention in the last decade, and has proven to be useful in a wide range of industries. ML models usually focus on making accurate predictions by minimizing errors, such as mean squared error ( MSE). These predictions can then be used as coefficients in other decision making processes, such as a combinatorial optimization problem.