Dynamic Programming for Predict+Optimise

We study the predict+optimise problem, where machine learning and combinatorial optimisation must interact to achieve a common goal. These problems are important when optimisation needs to be performed on input parameters that are not fully observed but must instead be estimated using machine learning. We provide a novel learning technique for predict+optimise to directly reason about the underlying combinatorial optimisation problem, offering a meaningful integration of machine learning and optimisation. This is done by representing the combinatorial problem as a piecewise linear function parameterised by the coefficients of the learning model and then iteratively performing coordinate descent on the learning coefficients. Our approach is applicable to linear learning functions and any optimisation problem solvable by dynamic programming. We illustrate the effectiveness of our approach on benchmarks from the literature.

Authors

• Emir Demirovi?
• Peter J. Stuckey Monash University
• Tias Guns KU Leuven
• James Bailey
• Christopher Leckie The University of Melbourne
• Kotagiri Ramamohanarao
• Jeffrey Chan RMIT University, Australia

Keywords

No keywords are indexed for this paper.