Machine Learning Alongside Beam Search for Resource Constrained Shortest Path Problems on State Transition Graphs

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.

The proposed method offers several advantages: (1) it is generic, (2) the ML model is independent of problem size, and (3) it requires no additional problem-specific information beyond the graph structure. We evaluate our approach on the single machine total tardiness problem and the temporal knapsack problem (TKP), yielding improved results compared to standard beam search without ML integration.