Fulin-Yan

CATIE (Centre Aquitain des Technologies de l’Information et Électroniques) is a non-profit organization created in 2014 based in the Région Nouvelle-Aquitaine. As a technology resources center specialized in digital technology, its main mission is to support SMEs and intermediate size companies in their digital transformation and to help them embracing and integrating related technologies.

Our collaboration with CATIE is about machine learning and optimization. We focus on problems related to shortest path problem with side constraints.

[Read more]

Many combinatorial optimization (CO) problems can be formulated as resource-constrained shortest path problems (RCSPPs) on directed acyclic multigraphs, which represent state-transition graphs defined under the dynamic programming (DP) paradigm. The number of vertices, arcs, and resource constraints depends on the size of the original problem instance. This reformulation is NP-hard. Exact methods require high-quality primal bounds to converge efficiently.

In this work, we focus on designing a generic constructive heuristic algorithm that can be applied to any problem once it is formulated as an RCSPP on a directed acyclic multigraph. Recent advances have demonstrated that combining machine learning (ML) with tree-based search strategies can enhance the solution of CO problems. Building on this idea, we propose an ML-enhanced beam search algorithm for RCSPPs. Our ML model leverages graph-based information to score candidate paths for expansion.

[Read more]

Authors: Ayse N. Arslan, Jeremy Omer, Fulin Yan
Abstract: The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant pr [Read more]