KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems
This work addresses a gap in neural algorithmic reasoning benchmarks for combinatorial optimization, but it is incremental as it applies known methods to a new problem.
The paper tackled the problem of extending neural algorithmic reasoning to solve the Knapsack problem, a pseudo-polynomial problem not covered in standard benchmarks, and achieved better generalization to larger instances compared to a direct-prediction baseline.
Neural algorithmic reasoning (NAR) is a growing field that aims to embed algorithmic logic into neural networks by imitating classical algorithms. In this extended abstract, we detail our attempt to build a neural algorithmic reasoner that can solve Knapsack, a pseudo-polynomial problem bridging classical algorithms and combinatorial optimisation, but omitted in standard NAR benchmarks. Our neural algorithmic reasoner is designed to closely follow the two-phase pipeline for the Knapsack problem, which involves first constructing the dynamic programming table and then reconstructing the solution from it. The approach, which models intermediate states through dynamic programming supervision, achieves better generalization to larger problem instances than a direct-prediction baseline that attempts to select the optimal subset only from the problem inputs.