Contrastive Losses and Solution Caching for Predict-and-Optimize

Maxime Mulamba, Jayanta Mandi, Michelangelo Diligenti, Michele Lombardi, Victor Bucarey Lopez, Tias Guns

Research output: Chapter in Book/Report/Conference proceedingConference paper

1 Citation (Scopus)

Abstract

Many decision-making processes involve solving a combinatorial optimization problem with uncertain input that can be estimated from historic data. Recently, problems in this class have been successfully addressed via end-to-end learning approaches, which rely on solving one optimization problem for each training instance at every epoch. In this context, we provide two distinct contributions. First, we use a Noise Contrastive approach to motivate a family of surrogate loss functions, based on viewing non-optimal solutions as negative examples. Second, we address a major bottleneck of all predict-and-optimize approaches, i.e. the need to frequently recompute optimal solutions at training time. This is done via a solver-agnostic solution caching scheme, and by replacing optimization calls with a lookup in the solution cache. The method is formally based on an inner approximation of the feasible space and, combined with a cache lookup strategy, provides a controllable trade-off between training time and accuracy of the loss approximation. We empirically show that even a very slow growth rate is enough to match the quality of state-of-the-art methods, at a fraction of the computational cost.

Original languageEnglish
Title of host publicationContrastive Losses and Solution Caching for Predict-and-Optimize
EditorsZhi-Hua Zhou
PublisherInternational Joint Conferences on Artificial Intelligence
Pages2833-2840
Number of pages8
ISBN (Electronic)978-0-9992411-9-6
DOIs
Publication statusPublished - 19 Aug 2021
Event30th International Joint Conference on Artificial Intelligence (IJCAI-21): IJCAI-21 - Canada, Montreal, Canada
Duration: 21 Aug 202126 Aug 2021
https://ijcai-21.org/

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference30th International Joint Conference on Artificial Intelligence (IJCAI-21)
Abbreviated titleIJCAI 2021
CountryCanada
CityMontreal
Period21/08/2126/08/21
Internet address

Keywords

  • Neuro-Symbolic Methods
  • Structured Prediction
  • Constraint Optimization

Fingerprint

Dive into the research topics of 'Contrastive Losses and Solution Caching for Predict-and-Optimize'. Together they form a unique fingerprint.

Cite this