polito.it
Politecnico di Torino (logo)

MATHEURISTICS FOR THE K CLUSTERS WITH FIXED CARDINALITY PROBLEM

Tommaso Boccardo

MATHEURISTICS FOR THE K CLUSTERS WITH FIXED CARDINALITY PROBLEM.

Rel. Marco Ghirardi. Politecnico di Torino, Corso di laurea magistrale in Mechatronic Engineering (Ingegneria Meccatronica), 2021

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

Download (2MB) | Preview
Abstract:

The aim of this thesis work is based on the search for a metaheuristic algorithm able to efficiently solve the K clusters with fixed cardinality problems, which are NP-hard combinatorial optimization problems. To do this, the mixed integer linear programming (MILP) formulations that were presented in the study conducted by Gonclaves & Lourenco, 2019 were used as reference models. Initially, the instances to test were generated randomly using the software MATLAB and the edge graphs present in the CEDRCIC’s library, considering the same characteristics as those present in the study. Subsequently the models of the paper were compared. Then an attempt was made to reduce the metaheuristic CPU execution times without straying too far from the optimal solution obtained by the MILP model and promising results have been achieved. These computational experiments were based on LP based local search metaheuristic algorithms. Finally, larger instances were generated, and it was possible to observe that metaheuristics managed not only to improve execution times, but also to obtain better results than the MILP formulation used as a reference. The codes were developed in C++ language and has been written on Visual Studio 2019 using IBM ILOG CPLEX 12.10 as optimization solver.

Relatori: Marco Ghirardi
Anno accademico: 2021/22
Tipo di pubblicazione: Elettronica
Numero di pagine: 97
Soggetti:
Corso di laurea: Corso di laurea magistrale in Mechatronic Engineering (Ingegneria Meccatronica)
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-25 - INGEGNERIA DELL'AUTOMAZIONE
Aziende collaboratrici: NON SPECIFICATO
URI: http://webthesis.biblio.polito.it/id/eprint/21207
Modifica (riservato agli operatori) Modifica (riservato agli operatori)