Predict+optimise with ranking objectives: exhaustively learning linear functions

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

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

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.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
EditorsSarit Kraus
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1078-1085
Number of pages8
ISBN (Electronic)9780999241141
DOIs
Publication statusPublished - 2019
EventInternational Joint Conference on Artificial Intelligence 2019 - Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28th
https://ijcai19.org/

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2019
Abbreviated titleIJCAI-19
CountryChina
CityMacao
Period10/08/1916/08/19
Internet address

Keywords

  • Constraints and SAT
  • Constraints and Data Mining
  • Machine Learning
  • Heuristic Search and Game Playing
  • Combinatorial Search and Optimisation

Cite this

Demirović, E., Stuckey, P. J., Bailey, J., Chan, J., Leckie, C., Ramamohanarao, K., & Guns, T. (2019). Predict+optimise with ranking objectives: exhaustively learning linear functions. In S. Kraus (Ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (pp. 1078-1085). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.24963/ijcai.2019/151