PLI e MAXSAT: Analisi Comparativa su Problemi di Ottimizzazione Combinatoria

Questa tesi analizza tre problemi classici di ottimizzazione combinatoria: il Problema del Cammino Minimo su grafo pesato, il Problema dello Zaino e il Problema dell’Insieme Indipendente Massimo. Gli obiettivi principali sono stati la formulazione dei problemi utilizzando due approcci distinti, Programmazione Lineare Intera (PLI) e Soddisfacibilità Booleana Massima (MaxSAT), e la valutazione sperimentale delle prestazioni di quattro solutori: glpsol, CBC, RC2 e Open-WBO. I risultati delle sperimentazioni mostrano come non esista un approccio universalmente migliore tra i due ma che i risolutori PLI risultino più efficienti in problemi con vincoli lineari complessi, come nel caso del Problema dello Zaino. I risolutori MaxSAT invece sono migliori in problemi su grafi di grandi dimensioni, come il Cammino Minimo e l’Insieme Indipendente.