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. CeselliSecondo
;M. TrubianUltimo
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.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.