Studio computazionale sul Multidimensional Knapsack Problem: analisi prestazionale al variare della dimensionalità

This thesis presents a computational study on the Multidimensional Knapsack Problem (MKP), a classic NP-hard problem in the field of combinatorial optimization. The main objective of this work is to analyze the impact of dimensionality and problem scale on the performance of exact solving algorithms. To this end, an empirical analysis was conducted based on the systematic generation of random instance sets, varying critical parameters such as the number of items (n) and the dimensions/capacities of the knapsack (m). The computational tests were performed by implementing mathematical models using PySCIPOpt, the Python interface for the SCIP solver. During the testing phase, key metrics for performance evaluation were collected, including execution times, the number of explored nodes, and the optimality status. The analysis of the collected data aims to track the solver's performance as complexity varies, providing a quantitative and structured evaluation of the problem's tractability limits across heterogeneous instances.

Il presente lavoro di tesi illustra uno studio computazionale sul Multidimensional Knapsack Problem (MKP), un classico problema NP-hard nell'ambito dell'ottimizzazione combinatoria. L'obiettivo principale dell'elaborato è analizzare l'impatto della dimensionalità e della scala del problema sulle prestazioni degli algoritmi di risoluzione esatta. A tale scopo, è stata impostata un'analisi empirica basata sulla generazione sistematica di set di istanze casuali, facendo variare parametri critici quali il numero di oggetti (n) e le dimensioni/capacità dello zaino (m). I test computazionali sono stati eseguiti implementando modelli matematici tramite PySCIPOpt, l'interfaccia Python per il risolutore SCIP. Durante la fase di testing sono state raccolte metriche fondamentali per la valutazione delle performance, tra cui i tempi di esecuzione, il numero di nodi esplorati e lo stato di ottimalità. L'analisi dei dati raccolti ha lo scopo di tracciare le prestazioni del risolutore al variare della complessità, fornendo una valutazione quantitativa e strutturata dei limiti di trattabilità del problema su istanze eterogenee.