Dynamic Programming for Predict+Optimise

  • Emir Demirovi? University of Melbourne
  • Peter J. Stuckey Monash University
  • Tias Guns Vrije Universiteit Brussel
  • James Bailey University of Melbourne
  • Christopher Leckie University of Melbourne
  • Kotagiri Ramamohanarao University of Melbourne
  • Jeffrey Chan RMIT University

Abstract

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.

Published
2020-04-03
Section
AAAI Technical Track: Constraint Satisfaction and Optimization