An investigation into prediction + optimisation for the knapsack problem

Emir Demirović, Peter J. Stuckey, James Bailey, Jeffrey Chan, Chris Leckie, Kotagiri Ramamohanarao, Tias Guns

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings
EditorsLouis-Martin Rousseau, Kostas Stergiou
Place of PublicationCham Switzerland
PublisherSpringer
Pages241-257
Number of pages17
ISBN (Electronic)9783030192129
ISBN (Print)9783030192112
DOIs
Publication statusPublished - 2019
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
- Thessaloniki, Greece
Duration: 4 Jun 20197 Jun 2019
Conference number: 16th
https://cpaior2019.uowm.gr/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11494
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
Abbreviated titleCPAIOR 2019
CountryGreece
CityThessaloniki
Period4/06/197/06/19
Internet address

Cite this

Demirović, E., Stuckey, P. J., Bailey, J., Chan, J., Leckie, C., Ramamohanarao, K., & Guns, T. (2019). An investigation into prediction + optimisation for the knapsack problem. In L-M. Rousseau, & K. Stergiou (Eds.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings (pp. 241-257). (Lecture Notes in Computer Science; Vol. 11494 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-030-19212-9_16
Demirović, Emir ; Stuckey, Peter J. ; Bailey, James ; Chan, Jeffrey ; Leckie, Chris ; Ramamohanarao, Kotagiri ; Guns, Tias. / An investigation into prediction + optimisation for the knapsack problem. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. editor / Louis-Martin Rousseau ; Kostas Stergiou. Cham Switzerland : Springer, 2019. pp. 241-257 (Lecture Notes in Computer Science).
@inproceedings{16b9bfb37b22486d90eaf9cce250d6ef,
title = "An investigation into prediction + optimisation for the knapsack problem",
abstract = "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.",
author = "Emir Demirović and Stuckey, {Peter J.} and James Bailey and Jeffrey Chan and Chris Leckie and Kotagiri Ramamohanarao and Tias Guns",
year = "2019",
doi = "10.1007/978-3-030-19212-9_16",
language = "English",
isbn = "9783030192112",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "241--257",
editor = "Louis-Martin Rousseau and Kostas Stergiou",
booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research",

}

Demirović, E, Stuckey, PJ, Bailey, J, Chan, J, Leckie, C, Ramamohanarao, K & Guns, T 2019, An investigation into prediction + optimisation for the knapsack problem. in L-M Rousseau & K Stergiou (eds), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. Lecture Notes in Computer Science, vol. 11494 , Springer, Cham Switzerland, pp. 241-257, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
, Thessaloniki, Greece, 4/06/19. https://doi.org/10.1007/978-3-030-19212-9_16

An investigation into prediction + optimisation for the knapsack problem. / Demirović, Emir; Stuckey, Peter J.; Bailey, James; Chan, Jeffrey; Leckie, Chris; Ramamohanarao, Kotagiri; Guns, Tias.

Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. ed. / Louis-Martin Rousseau; Kostas Stergiou. Cham Switzerland : Springer, 2019. p. 241-257 (Lecture Notes in Computer Science; Vol. 11494 ).

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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

Y1 - 2019

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

SN - 9783030192112

T3 - Lecture Notes in Computer Science

SP - 241

EP - 257

BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research

A2 - Rousseau, Louis-Martin

A2 - Stergiou, Kostas

PB - Springer

CY - Cham Switzerland

ER -

Demirović E, Stuckey PJ, Bailey J, Chan J, Leckie C, Ramamohanarao K et al. An investigation into prediction + optimisation for the knapsack problem. In Rousseau L-M, Stergiou K, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. Cham Switzerland: Springer. 2019. p. 241-257. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-030-19212-9_16