Esperimenti computazionali su approcci MIP per problemi di facility location

This thesis addresses Facility Location Problems (FLP) by investigating the computational differences among four variants: Uncapacitated Facility Location Problem (UFLP), Capacitated Facility Location Problem (CFLP), p-Dispersion, and Maxisum Dispersion. The research focuses on two main comparisons: the first, between UFLP and CFLP, studies the impact of capacity constraints on computational complexity, while the second, between p-Dispersion and Maxisum, analyzes the differences in complexity and structure of the two dispersion models. The thesis aims to highlight the computational, structural, and qualitative differences among these optimization models, using the SCIP solver through the Python PySCIPOpt interface. In the comparison between UFLP and CFLP, experimental results demonstrate that the CFLP model requires significantly higher solution times (up to 2 or 3 orders of magnitude) compared to the UFLP model, with the number of nodes explored in the Branch & Cut algorithm reaching thousands versus the few nodes required by UFLP. Furthermore, CFLP necessitates opening a greater number of facilities to satisfy capacity constraints, resulting in higher objective function values. In the comparison between p-Dispersion and Maxisum, the analysis reveals substantial differences in computational complexity: while p-Dispersion exhibits linear growth in computation times, Maxisum exhibits approximately quadratic growth which compromises scalability for large instances. From a qualitative perspective, p-Dispersion generates more balanced spatial distributions with superior minimum distances between facilities, while Maxisum produces configurations that maximize global dispersion even at the cost of having relatively close facilities. The experiments were conducted on randomly generated instances belonging to three dimensional categories (small, medium, large), with facilities and customers generated within the unit square [0,1] × [0,1]. The analyses considered computational parameters (runtime, nodes explored, memory usage) and qualitative indicators of facility spatial distribution. The results provide guidelines for selecting the most appropriate model based on specific application requirements, highlighting the trade-off between modeling realism and problem-solving complexity. The work also includes an overview of the main practical applications of the studied models in sectors such as logistics, healthcare, telecommunications, and management of hazardous facilities.

La tesi affronta i problemi di tipo Facility Location (FLP) investigando le differenze computazionali tra quattro varianti: Uncapacitated Facility Location Problem (UFLP), Capacitated Facility Location Problem (CFLP), p-Dispersion e Maxisum Dispersion. La ricerca si concentra su due principali confronti: il primo, tra UFLP e CFLP, studia l'impatto dei vincoli di capacità sulla complessità computazionale mentre il secondo, tra p-Dispersion e Maxisum, analizza le differenze nella complessità e nella struttura dei due modelli di dispersione. La tesi si propone di evidenziare le differenze computazionali, strutturali e qualitative tra questi modelli di ottimizzazione, utilizzando il solutore SCIP attraverso l'interfaccia Python PySCIPOpt. Nel confronto tra UFLP e CFLP, i risultati sperimentali dimostrano che il modello CFLP richiede tempi di risoluzione significativamente superiori (fino a 2 o 3 ordini di grandezza) rispetto al modello UFLP, con un numero di nodi esplorati nell'algoritmo Branch & Cut che può raggiungere le migliaia contro i pochi nodi richiesti dall'UFLP. Inoltre, il CFLP necessita dell'apertura di un numero maggiore di facilities per soddisfare i vincoli di capacità, comportando valori più elevati della funzione obiettivo. Nella comparazione tra p-Dispersion e Maxisum , l'analisi rivela differenze sostanziali nella complessità computazionale: mentre il p-Dispersion presenta una crescita lineare dei tempi di calcolo, il Maxisum evidenzia una crescita approssimativamente quadratica che compromette la scalabilità per istanze di grandi dimensioni. Dal punto di vista qualitativo, il p-Dispersion genera distribuzioni spaziali più equilibrate con distanze minime superiori tra facilities, mentre il Maxisum produce configurazioni che massimizzano la dispersione globale anche a costo di avere facilities relativamente vicine. Gli esperimenti sono stati condotti su istanze generate casualmente appartenenti a tre categorie dimensionali (piccole, medie, grandi) mentre le facilities e i clienti sono generati nell'unit square [0,1] × [0,1]. Le analisi hanno considerato parametri computazionali (runtime, nodi esplorati, utilizzo memoria) e indicatori qualitativi della distribuzione spaziale delle facilities. I risultati forniscono delle indicazioni per la selezione del modello più appropriato in base alle specifiche esigenze applicative, evidenziando il trade-off tra realismo della modellazione e complessità di risoluzione del problema. Il lavoro include inoltre una panoramica delle principali applicazioni pratiche dei modelli studiati in settori quali logistica, sanità, telecomunicazioni e gestione di facilities pericolose.