Optimization models and methods for clustering problems

This work addresses a clustering problem from a geometrical point of view, where the goal is to divide a set of data points in a given number of groups while minimizing the total Euclidean distance (Weber problem) or the total squared Euclidean distance (Minimum Sum of Squares Clustering problem (MSSC)). It builds upon an existing work, where new mixed integer non linear models were introduced, in a convex quadratic framework, with linear and second order cone constraints. Our approach was to start from these models and enhance the performance and the solution by making some adjustments. The big-M constraint defined in the mixed integer non linear models was modified in order to tighten bounds, reducing the computational time. A symmetry breaking constraint was added to reduce the exploration by the solver of redundant solution, accelerating the convergence to the optimal solution. The main modification made to the original models was the introduction of so-called callback functions, that are user-defined procedures activated during the execution of a process, in our case during the branch and bound algorithm. They allow the solver to dynamically intervene on the solution or the model at specific points in the process. These modifications were made to improve the original models in terms of efficiency and precision of the solution, and to reach a faster convergence to the global optimum. The numerical results will show the effects these changes have had on some elements of the solution, and which were the ones with the greatest impact.

Questo lavoro analizza un problema di clustering da un punto di vista geometrico, dove l’obiettivo è suddividere un insieme di punti in più gruppi minimizzando la distanza euclidea totale (problema di Weber) oppure la distanza euclidea totale al quadrato (Minimum Sum of Squares Clustering problem (MSSC)). Questo studio si basa su un lavoro già esistente, dove sono stati introdotti nuovi modelli MINLP (mixed-integer non linear programming) convessi in forma quadratica, con vincoli lineari e vincoli conici del secondo ordine. Il nostro approccio è stato quello di partire da questi modelli e cercare di migliorarne le prestazioni e la soluzione finale, applicando delle modifiche. Il vincolo di big-M definito nei modelli MINLP è stato modificato per restringere i limiti superiore e inferiore, cercando di ridurre il tempo computazionale. Un vincolo di symmetry breaking è stato aggiunto per ridurre l’esplorazione di soluzioni ridondanti da parte del solutore, accelerando la convergenza verso la soluzione ottima. La modifica principale fatta ai modelli originali è stata l’introduzione delle funzioni di callback, che sono procedure definite dall’utente che vengono attivate durante l’esecuzione di un processo, nel nostro caso durante l’algoritmo di branch and bound. Queste funzioni permettono al solutore di intervenire dinamicamente sulla soluzione o sul modello in punti specifici del processo. Queste modifiche sono state fatte per migliorare i modelli di partenza in termini di efficienza e accuratezza della soluzione, e per raggiungere una convergenza più rapida all’ottimo globale. I risultati numerici mostreranno gli effetti che queste modifiche hanno avuto su alcuni elementi della soluzione, e quali sono state quelle con maggiore impatto.