MATHEURISTICS FOR THE K CLUSTERS WITH FIXED CARDINALITY PROBLEM

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.