Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure
This work addresses the limitation of neural solvers for real-world graph optimization problems, such as wireless network allocation, but is incremental in proposing an enhancement to existing architectures.
The paper tackles the problem of applying neural combinatorial optimization architectures beyond the TSP to practical graph problems like PCAP, finding that existing methods fail to capture graph structure and adapt to dynamic attributes, but shows that Distance Encoding improves structural representation.
Recent years have witnessed the promise that reinforcement learning, coupled with Graph Neural Network (GNN) architectures, could learn to solve hard combinatorial optimization problems: given raw input data and an evaluator to guide the process, the idea is to automatically learn a policy able to return feasible and high-quality outputs. Recent work have shown promising results but the latter were mainly evaluated on the travelling salesman problem (TSP) and similar abstract variants such as Split Delivery Vehicle Routing Problem (SDVRP). In this paper, we analyze how and whether recent neural architectures can be applied to graph problems of practical importance. We thus set out to systematically "transfer" these architectures to the Power and Channel Allocation Problem (PCAP), which has practical relevance for, e.g., radio resource allocation in wireless networks. Our experimental results suggest that existing architectures (i) are still incapable of capturing graph structural features and (ii) are not suitable for problems where the actions on the graph change the graph attributes. On a positive note, we show that augmenting the structural representation of problems with Distance Encoding is a promising step towards the still-ambitious goal of learning multi-purpose autonomous solvers.