Resource Constrained Shortest Path Problems (RCSPP) have wide applicability, representing a flexible model for network applications. Furthermore, they frequently arise as subproblems in decomposition-based methods, as occurs in column generation for Vehicle Routing Problems. In all these settings, being able to perform early detection of infeasibility helps to strongly reduce computing times. For instance, dynamic programming is often used to design RCSPP algorithms: labels representing partial solutions are iteratively created and extended, and these can be dropped if they are found to have no feasible (and profitable) completion. Many fathoming heuristics have been proposed in the literature. We experiment a data-driven approach in this context, using supervised learning models to deal with the problem of detecting infeasibility. We design features which are not dependent on instance size, having different computing cost. We compare the tradeoff between computational effort and performance which can be achieved, when a binary classifier is employed. Our results indicate such an attempt to be effective.

Data-Driven Feasibility for the Resource Constrained Shortest Path Problem / C. Ondei, A. Ceselli, M. Trubian (AIRO SPRINGER SERIES). - In: Graphs and Combinatorial Optimization: from Theory to Applications. CTW 2023 / [a cura di] A. Brieden, S. Pickl, M. Siegle. - Cham : Springer Nature, 2024. - ISBN 9783031468254. - pp. 135-146 (( Intervento presentato al 19. convegno Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW) tenutosi a Garmisch-Partenkirchen nel 2023 [10.1007/978-3-031-46826-1_11].

Data-Driven Feasibility for the Resource Constrained Shortest Path Problem

C. Ondei
Primo
;
A. Ceselli
Secondo
;
M. Trubian
Ultimo
2024

Abstract

Resource Constrained Shortest Path Problems (RCSPP) have wide applicability, representing a flexible model for network applications. Furthermore, they frequently arise as subproblems in decomposition-based methods, as occurs in column generation for Vehicle Routing Problems. In all these settings, being able to perform early detection of infeasibility helps to strongly reduce computing times. For instance, dynamic programming is often used to design RCSPP algorithms: labels representing partial solutions are iteratively created and extended, and these can be dropped if they are found to have no feasible (and profitable) completion. Many fathoming heuristics have been proposed in the literature. We experiment a data-driven approach in this context, using supervised learning models to deal with the problem of detecting infeasibility. We design features which are not dependent on instance size, having different computing cost. We compare the tradeoff between computational effort and performance which can be achieved, when a binary classifier is employed. Our results indicate such an attempt to be effective.
Settore INFO-01/A - Informatica
Settore MATH-06/A - Ricerca operativa
2024
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
DataDriven_Feas_RCSPP_CTW_2023_Ondei_Ceselli_Trubian.pdf

accesso riservato

Descrizione: Intervento a convego
Tipologia: Publisher's version/PDF
Dimensione 158.81 kB
Formato Adobe PDF
158.81 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/1124459
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact