Beyond the TSP: On the transfer of existing deep learning architectures to other combinatorial problems

Solving combinatorial problems represents an everyday challenge for vital problems such as logistics, resource allocation and optimization. In those contexts, machine learning, with its Reinforcement Learning and Graph Neural Networks branches, promises automation: give the machine input data and an evaluator to guide its learning process and, and the end of training, it will return feasible and high-quality outputs. Unfortunately, exploiting this potential is not an easy matter: in practice, the research so far has only focused on tailored solutions, small environments or, with changing fortunes, on specific sub-classes of combinatorial problems such as the TSP and its variants. The aim of this research is therefore assessing how and whether the latest deep learning findings in those fields also transfer to other practical problems. To this end, we set out to systematically transfer these architectures from the TSP problem to that of radio resource allocation in wireless networks. Our results suggest that existing architectures are still incapable of capturing the structural aspects of combinatorial problems, which represent a sever setback for generalization purposes. We will also demonstrate that reinforcing the structural representation of problems with a novel technique named Distance Encoding is a promising direction for obtaining multi-purpose autonomous solvers. The introduction of encoded distances as novel features in fact improves the solutions when no other structural information is provided.