EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2169. PathWyse 1.0: a software library for the Resource Constrained Shortest Path

Invited abstract in session MD-26: Optimization problems on graphs, stream Combinatorial Optimization.

Monday, 14:30-16:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Matteo Salani
IDSIA - USI/SUPSI
2. Saverio Basso
IDSIA - USI/SUPSI

Abstract

In this paper, we introduce PathWyse 1.0, a versatile dual licensed library addressing the Resource Constrained Shortest Path Problem (RCSPP), a fundamental and hard combinatorial problem.

PathWyse is capable of modeling and solving a variety of standard RCSPPs implementing state-of-the-art algorithms. The library interfaces with both C++ and Python, easing the task of modeling customized problems with minimal programming required.

Algorithmically, the latest version presents parallel implementations of both exact and heuristic algorithms. Particularly, heuristic algorithms are integrated into a competitive ensemble framework, boosting their effectiveness. Moreover, this release highlights an enhanced bi-directional dynamic programming technique. The joining procedure, usually a time-intensive aspect of the algorithm, now utilizes binary search and Pareto frontier exploration, resulting in notable performance improvements.

We conducted computational experiments using instances from literature, encompassing scenarios featuring a singular resource constraint across cyclic networks and large acyclic networks. We present findings related to instances with multiple resource constraints within cyclic networks.

The flexible parameterization showcases how users can easily model and efficiently resolve multi-constrained problems. To aid comprehension, we provide a tutorial on a column generation algorithm, utilizing PathWyse as the solver for the pricing problem.

Keywords

Status: accepted

Back to the list of papers