CRIS Current Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishMany 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.
| Titolo: | Contrastive Losses and Solution Caching for Predict-and-Optimize | |
| Autore/i: | Maxime Mulamba; Jayanta Mandi; Michelangelo Diligenti; Michele Lombardi; Victor Bucarey; Tias Guns | |
| Autore/i Unibo: | ||
| Anno: | 2021 | |
| Titolo del libro: | Proceedings of the Thirtieth International Joint Conference on ArtificialIntelligence, {IJCAI} 2021, Virtual Event / Montreal, Canada, 19-27August 2021 | |
| Pagina iniziale: | 2833 | |
| Pagina finale: | 2840 | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.24963/ijcai.2021/390 | |
| 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. | |
| Data stato definitivo: | 18-feb-2022 | |
| Appare nelle tipologie: | 4.01 Contributo in Atti di convegno |
File in questo prodotto:
Copyright © 2022