Approcci MIP per il Maximum Weighted Submatrix Coverage Problem

The Maximum Weighted Submatrix Coverage Problem (MWSCP) is a combinatorial optimization problem that has recently attracted attention, positioning itself within the broader field of Operations Research and integer mathematical programming. This thesis addresses the study of the MWSCP through the implementation of three integer programming models, derived from recent developments in the literature. Following an in-depth analysis of the problem, an experimental campaign was carried out on artificially generated instances, in order to evaluate the effectiveness and efficiency of the different models. In particular, the behavior of the models was analyzed by varying specific input parameters, examining the impact on performance in terms of solution quality and computational time. The results obtained provide useful insights for future optimization efforts and contribute to a deeper understanding of the solving dynamics of the MWSCP.

Il Maximum Weighted Submatrix Coverage Problem (MWSCP) rappresenta una problematica di ottimizzazione combinatoria di recente interesse, inserendosi nell’ambito più ampio della Ricerca Operativa e della programmazione matematica intera. In questa tesi si affronta lo studio del MWSCP attraverso l’implementazione di tre modelli di programmazione intera, derivati da recenti sviluppi della letteratura. Dopo un’analisi approfondita del problema, è stata condotta una campagna sperimentale su istanze generate artificialmente, al fine di valutare l’efficacia e l’efficienza dei diversi modelli. In particolare, si è analizzato il comportamento dei modelli al variare di specifici parametri di input, esaminando l’impatto sulle prestazioni in termini di qualità delle soluzioni e tempi di calcolo. I risultati ottenuti offrono spunti utili per future ottimizzazioni e contribuiscono alla comprensione delle dinamiche risolutive del MWSCP.