polito.it
Politecnico di Torino (logo)

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

Matteo Boffa

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

Rel. Michela Meo. Politecnico di Torino, Corso di laurea magistrale in Ict For Smart Societies (Ict Per La Società Del Futuro), 2021

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (6MB) | Preview
Abstract:

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.

Relatori: Michela Meo
Anno accademico: 2021/22
Tipo di pubblicazione: Elettronica
Numero di pagine: 94
Soggetti:
Corso di laurea: Corso di laurea magistrale in Ict For Smart Societies (Ict Per La Società Del Futuro)
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-27 - INGEGNERIA DELLE TELECOMUNICAZIONI
Ente in cotutela: Huawei Technologies Co.,Ltd., France (FRANCIA)
Aziende collaboratrici: Huawei Technologies France S.A.S.U
URI: http://webthesis.biblio.polito.it/id/eprint/20421
Modifica (riservato agli operatori) Modifica (riservato agli operatori)