Graph Pointer Network and Reinforcement Learning for Thinnest Path Problem

The complexity and NP-hard nature make finding optimal solutions challenging for combinatorial optimization problems (COPs) using traditional methods, especially for the large-scale problem. Recently, deep learning-based approaches have shown promise in solving COPs. Pointer Network (PN) has become a popular choice due to its ability to handle variable-length sequences and generate variable-sized outputs. Graph Pointer Network (GPN), which incorporates graph embedding layers in PN, can be well-suited for problems with graph structures. Additionally, Reinforcement Learning (RL) has great potential in enhancing scalability for solving large-scale instances. In this paper, we focus on Thinnest Path Problem (TPP). We propose an approach using RL to train GPN with constraints (GPN-c) to solve TPP. Our approach outperforms traditional solutions by providing faster and more efficient solving strategies. Specifically, we achieved significant improvements in solution quality, runtime, and scalability, and successfully extended our approach to instances with up to 500 nodes. Furthermore, RL and GPN can provide more flexible and adaptive solving strategies, making them highly applicable to real-world scenarios.