Dynamic Programming for Predict+Optimise

Authors

  • 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

DOI:

https://doi.org/10.1609/aaai.v34i02.5502

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.

Downloads

Published

2020-04-03

How to Cite

Demirovi?, E., Stuckey, P. J., Guns, T., Bailey, J., Leckie, C., Ramamohanarao, K., & Chan, J. (2020). Dynamic Programming for Predict+Optimise. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1444-1451. https://doi.org/10.1609/aaai.v34i02.5502

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization