TY - GEN
T1 - An Investigation into Prediction + Optimisation for the Knapsack Problem
AU - Demirović, Emir
AU - Stuckey, Peter J.
AU - Bailey, James
AU - Chan, Jeffrey
AU - Leckie, Chris
AU - Ramamohanarao, Kotagiri
AU - Guns, Tias
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We study a prediction�+�optimisation formulation of the knapsack problem. The goal is to predict the profits of knapsack items based on historical data, and afterwards use these predictions to solve the knapsack. The key is that the item profits are not known beforehand and thus must be estimated, but the quality of the solution is evaluated with respect to the true profits. We formalise the problem, the goal of minimising expected regret and the learning problem, and investigate different machine learning approaches that are suitable for the optimisation problem. Recent methods for linear programs have incorporated the linear relaxation directly into the loss function. In contrast, we consider less intrusive techniques of changing the loss function, such as standard and multi-output regression, and learning-to-rank methods. We empirically compare the approaches on real-life energy price data and synthetic benchmarks, and investigate the merits of the different approaches.
AB - We study a prediction�+�optimisation formulation of the knapsack problem. The goal is to predict the profits of knapsack items based on historical data, and afterwards use these predictions to solve the knapsack. The key is that the item profits are not known beforehand and thus must be estimated, but the quality of the solution is evaluated with respect to the true profits. We formalise the problem, the goal of minimising expected regret and the learning problem, and investigate different machine learning approaches that are suitable for the optimisation problem. Recent methods for linear programs have incorporated the linear relaxation directly into the loss function. In contrast, we consider less intrusive techniques of changing the loss function, such as standard and multi-output regression, and learning-to-rank methods. We empirically compare the approaches on real-life energy price data and synthetic benchmarks, and investigate the merits of the different approaches.
UR - http://www.scopus.com/inward/record.url?scp=85066871016&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19212-9_16
DO - 10.1007/978-3-030-19212-9_16
M3 - Conference paper
AN - SCOPUS:85066871016
SN - 9783030192112
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 241
EP - 257
BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Proceedings
A2 - Rousseau, Louis-Martin
A2 - Stergiou, Kostas
PB - Springer Verlag
T2 - 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2019
Y2 - 4 June 2019 through 7 June 2019
ER -