Conference Proceedings

An Investigation into Prediction��Optimisation for the Knapsack Problem

E Demirović, PJ Stuckey, J Bailey, J Chan, C Leckie, K Ramamohanarao, T Guns

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Springer | Published : 2019

Abstract

© 2019, Springer Nature Switzerland AG. 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 int..

View full abstract

Citation metrics