Modelli MIP per problemi basati sul numero di Alcuin di un grafo

This thesis work aims to study a generalization of the river crossing problem with the aim to analyzing the necessary time to determine the problem solution and to evaluate the link between the Alcuin number of a graph and its density. This work is divided in four chapters: initially some fundamental theoretical notions are presented, necessary to understand the study, subsequently the methods used to deal with the experimental tests are presented and the results obtainded are analyzed. Finally the conclusions of the work carried out are drawn up. To tackle this study several Python[1] script were written which perform all the necessary functions starting from the graphs random generation done using Python package Networkx[2], up to the processing of the obtained results. All of the code can be freely consulted online via the repository used for project version control[14]. To solve mathematical models was used Cplex22.1.1[9] software and its Python[1] interface via the Pyomo[3] package. The following Python[1] packages were used to present the results graphically and to process the .csv result file: Matplotlib[4], Seaborn[5], Numpy[6], Pandas[7]. The calculation times presented in this paper refer to the cluster of Department of Information Engineering of the University of Padova. To be able to use the cluster it was necessary to use the generic scheduler SLURM[8]. Most of the definition presented in this paper are inspired by the lecture notes of Models and Software for Discrete Optimization course, held by professor Domenico Salvagnin[11][12][13] at University of Padua.

Il presente lavoro di tesi si prefigge lo studio di una generalizzazione dell’Alcuin river crossing problem, noto anche come il problema dell’attraversamento del fiume di Alcuin, con l’obiettivo di analizzare i tempi necessari per determinare la soluzione del problema e di valutare il legame tra il numero di Alcuin di un grafo e la sua densita`. Questo elaborato e` stato articolato in 4 capitoli: inizialmente si presentano al- cune nozioni teoriche fondamentali, necessarie per la comprensione dello studio, successivamente si presentano le modalita` usate per affrontare le prove sperimen- tali e si analizzano i risultati ottenuti. Infine si elaborano le conclusioni del lavoro svolto. Per affrontare questo studio sono stati scritti diversi script Python[1] che svolgo- no le varie funzioni necessarie partendo dalla generazione casuale di grafi fatta usando il pacchetto python Netwokx[2], fino all’elaborazione dei risultati ottenu- ti. Tutto il codice e` consultabile liberamente online tramite la repository usata per il controllo versione del progetto[14]. Per la risoluzione dei modelli matematici e` stato usato il software CPLEX 22.1.1[9] e la sua interfaccia su Python[1] trami- te il pacchetto Pyomo[3]. Per la presentazione dei risultati in maniera grafica e per l’elaborazione del file .csv sono stati utilizzati i seguenti pacchetti Python[1]: Matplotlib[4], Seaborn[5], Numpy[6], Pandas[7]. I tempi di calcolo presenti nei risultati di questo elaborato fanno riferimento al cluster del Dipartmento di Ingegneria dell’Informazione dell’Universita` degli Stu- di di Padova. Per poter usare il cluster e` stato necessario l’utilizzo dello scheduler generico SLURM[8]. Molte delle definizioni presenti in questo elaborato sono ispirate alle dispense del corso di Modelli e Software per l’Ottimizzazione Discreta, tenuto dal professore Domenico Salvagnin[11][12][13] presso l’Universita` degli Studi di Padova.