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. Our contributions are two-fold: 1)
we provide theoretical insight into the properties
and computational complexity of predict+optimise
problems in general, and 2) develop a novel framework that, in contrast to related work, guarantees to
compute the optimal parameters for a linear learning function given any ranking optimisation problem. We illustrate the applicability of our framework for the particular case of the unit-weighted
knapsack predict+optimise problem and evaluate
on benchmarks from the literature