Esperimenti di programmazione lineare intera per il timetabling accademico

In this thesis, we address the problem of academic timetabling using integer linear programming. We propose a mathematical model that formalizes the hard constraints required to ensure timetable accuracy (absence of overlaps, resource availability, capacity constraints, etc.) and integrates soft constraints to model preferences such as the distribution of classes throughout the week or the assignment of specific classrooms. The model was implemented using the Python language and the PySCIPOpt library, interfaced with a MIP solver. Finally, we present experimental results on several test instances, analyzing the model's performance in terms of solution quality, computation time, and solver tree size.

In questa tesi affrontiamo il problema del timetabling accademico tramite l’uso della programmazione lineare intera. Viene proposto un modello matematico che formalizza i vincoli rigidi necessari per garantire la correttezza dell’orario (assenza di sovrapposizioni, disponibilità delle risorse, vincoli di capienza, ecc.) e integra vincoli flessibili (soft constraints) per modellare preferenze come la distribuzione delle lezioni nel corso della settimana o l’assegnazione di aule specifiche. Il modello è stato implementato utilizzando il linguaggio Python e la libreria PySCIPOpt, interfacciata con un risolutore MIP. Vengono infine presentati i risultati sperimentali su diverse istanze di test, analizzando le prestazioni del modello in termini di qualità delle soluzioni, tempi di calcolo e dimensione dell'albero di risoluzione.