Generic machine-learning-augmented beam search for resource-constrained shortest path reformulations of combinatorial optimization problems
Fulin Yan, François Clautiaux, Aurélien Froger, Boris Albar · Computers & Operations Research · 2025
In this work, we propose a generic heuristic for the resource-constrained shortest path problem derived from dynamic programming reformulations of hard combinatorial optimization problems. The approach is a machine-learning (ML)-augmented beam search, where an ML model serves as one of the scoring functions to select candidate paths for expansion, complementing lower and upper bound estimates. Our method offers several key advantages. First, the path features used by our model are generic and only derived from the reformulation, without relying on any additional problem-specific information beyond the graph structure and resource constraints. Second, we manually designed and aggregated features to obtain vectors of fixed length, enabling us to train the model on small to medium-sized instances and apply it to much larger instances. We evaluate our algorithm on two benchmark problems: the Single Machine Total Weighted Tardiness Problem and the Temporal Knapsack Problem, each under two settings: with and without access to optimal Lagrangian multipliers. Our numerical experiments show that integration of ML into an anytime beam search enhances its solution quality in most cases, with at most minor performance degradation in the other cases. They suggest that one should systematically incorporate ML into the approach.