\chapter{Introduzione}
% \todo[inline]{Spostare come intro anticipazione modello + mettere descrzione + geenica di quello che ci si aspetta come risultati}
% \todo[inline]{Esempi numerati come Figure e Table}

% \todo[inline]{Rimuovi i doppi backslash in giro. Per indicare che devi andare a capo, basta lasciare una riga vuota, il doppio backslash sputtana gli spazi tra paragrafi}


% abstract

% problema: gli orari sono difficili da fare perché

% qualche elenco di vincolo da inserire

% obiettivo : modello che permetta di allocare con vincoli hard e soft

% In questa tesi abbiamo ottenuto: 
% riassunto dei risultati

% analisi dei dati $\to$ ricavato modello UML

% modello di rappresentazion basso livello ai fini di ottimizzazione

% scelto ILP e CPLEX dopo valutazione


% riassunto in poche righe della validazione

La Tesi si pone come obiettivo di risolvere il problema la pianificazione dell’orario dei collegi di ICM (Informatica, Cinema e Meccatronica) ed ETF (Elettronica, Telecomunicazioni e Fisica) del Politecnico di Torino, modellandolo come un problema di ottimizzazione. 

La pianificazione dell’orario è un problema difficile da affrontare poiché coinvolge differenti tipi di vincoli. Esistono limiti strutturali, quali aule e laboratori disponibili in quantità limitata e con capienze note, dipendenze date dai piani di studio, ad esempio l’impossibilità di sovrapporre insegnamenti obbligatori per un dato orientamento, vincoli dettati dalla disponibilità dei docenti che possono essere coinvolti in più insegnamenti, e vincoli dettati dalle necessità degli studenti di seguire troppe ore di lezione consecutive. Si è dovuto considerare anche che i docenti che possono avere impegni istituzionali o tenere lezione in insegnamenti in Master e corsi di laurea di altri collegi che comportano indisponibilità nell’arco della settimana.

Alcuni di questi vincoli sono stati ritenuti forti (\textit{hard constraint}). Ad esempio, non è possibile pianificare un orario che usi più aule di quelle presenti in ateneo, non è possibile che un docente insegni contemporaneamente per più insegnamenti e non è possibile sovrapporre insegnamenti obbligatori all’interno dello stesso orientamento se questi sono allocati per il medesimo anno accademico. 

Altri vincoli sono stati considerati deboli (\textit{soft constraint}), soddisfare o non soddisfare i soft constraint introduce penalità o bonus a seconda del tipo. Ad esempio si pensi agli insegnamenti classificati come crediti liberi all’interno di un orientamento, se questi si sovrapponessero ad altri insegnamenti dello stesso orientamento in un’allocazione questa non dovrebbe essere considerata non valida, ma bisognerebbe preferirne un’altra in cui tale sovrapposizione non è presente. 

L’obiettivo della Tesi è stato sviluppare un software che supporti nella pianificazione dell’orario usando l’ottimizzazione matematica. Il problema è stato modellato richiedendo di soddisfare tutti gli hard constraint e massimizzare una funzione obiettivo costruita a partire da tutte i soft constraint. In altre parole, l’output di tale software è la versione migliore possibile dell’orario che rispetti tutti i vincoli. 


% \todo[inline]{Non è corretto scrivere così l'intro. Devi prima spiegare tutte le cose (l'ho fatto io), poi al fondo dei scrivere l'outline}

Per raggiungere questo obiettivo è stato effettuato uno studio approfondito delle tecnologie e della letteratura informatica fatto per trovare i modelli di ottimizzazione e gli approcci migliori in grado di rappresentare correttamente le due tipologie di vincoli e che consentano di classificare le soluzioni in funzione del soddisfacimento o della violazione dei soft constraint. Sono stati individuati due problemi validi per quello in esame: “\textit{Maximum satisfiability problem}” (MaxSMT) e “\textit{Integer linear programming}” (ILP). In seguito sono stati scelti gli strumenti, i solver, in grado di risolvere tali problemi: Z3 per MaxSMT e IBM CPLEX per ILP.

I dati relativi all'analisi dei requisiti sono stati acquisiti mediante interviste con i responsabili dell’orario volte a chiarificare tutte le variabili in gioco e ad evidenziare eventuali casi limite di interesse.

Tramite l’analisi dei dati acquisiti si è ricavato un modello UML\footnote{Unified Modeling Language.} rappresentante nell’interezza il problema; si è inoltre creato un modello UML specifico dei dati riguardanti gli insegnamenti di cui allocare l’orario, in quanto rappresentano la principale sorgente di dati del software. La progettazione di alto livello si è conclusa con la generazione degli schemi di validazione delle diverse sorgenti di informazioni per uniformare e automatizzare la lettura dei dati da parte del programma.  

Successivamente, sulla modellazione si è passati dai requisiti di alto livello alle variabili e alle equazioni definite prima in un ambiente matematico e successivamente a livello di codice compatibilmente con le API messe a disposizione dai software utilizzati. 
Sono stati implementati due differenti modelli:  
\begin{itemize}
    \item Modello a matrice: enfatizza il concetto di unità di lezione allocata ad un dato insegnamento e ad un dato docente in una data aula modellandolo tramite una matrice multidimensionale
    \item Modello a slot: viene posta l’enfasi sullo slot di lezione e sul giorno e la fascia oraria in cui questo viene allocato. 
\end{itemize}
In entrambi i modelli i soft constraint vengono associati ad una funzione obiettivo da minimizzare associando ai singoli termini di essa un valore superiore a 0 in caso di penalità, 0 in caso di vincolo rispettato o suggerimento non rispettato e un valore inferiore a 0 in caso di suggerimento rispettato.


La modellazione in ambiente matematico ha evidenziato i limiti del modello a matrice in quanto, sebbene la definizione dei vincoli elementari fosse semplice, la descrizione di quelli più complessi era impraticabile; ad esempio un vincolo indicante l’allocazione parallela di due lezioni appartenenti ad insegnamenti differenti produce un elevato numero di equazioni con il modello matriciale mentre immediata con il modello a slot. 
D’altro canto il secondo modello rende più complessa la gestione dei vincoli intesi a porre un limite superiore al numero di lezioni allocabili parallelamente in funzione del numero di aule di un certo tipo disponibili in un certo giorno o ad una certa fascia oraria.


L'implementazione del modello matematico in Python ha evidenziato ulteriormente la bontà del secondo modello in termini di risorse computazionali necessarie e di performance. Non è stato infatti possibile modellare la disponibilità di aule con il primo modello poiché la richiesta di risorse era troppo elevata; inoltre il software CPLEX, a differenza di Z3, permette un’esecuzione multi-thread del solver. 
%
La scelta è quindi ricaduta sulla modellizzazione come un problema di programmazione lineare con l’ausilio di CPLEX. 

Durante la fase successiva della Tesi è stato scritto il codice in grado di raccogliere i dati dalle diverse fonti di input, di istanziare le variabili del modello e di modellare i vincoli e la funzione obiettivo. È stato implementato un ulteriore modulo del software che ha il compito di interfacciarsi con il solver CPLEX e reagire ogni qualvolta viene trovata una soluzione e salvarla in un database di appoggio per una futura analisi ed esportazione. % Vengono inoltre mostrate nel Capitolo \ref{chapModiUtilizzo} le modalità di utilizzo del software scritto.

Questa tesi ha anche  affrontato il problema della validazione dei dati sorgente e delle soluzioni. Ad una prima fase di acquisizione dei dati da varie fonti tramite interazioni con i relativi uffici, nonché tramite questionari somministrati ai docenti ed all’estrazione semi automatizzata dei dati autonomamente da fonti pubblicamente consultabili quali il sito del Politecnico, è iniziata la fase di validazione dei dati in input. 

Le prime esecuzioni del software hanno permesso di verificare la correttezza dei dati inseriti andando a verificare l’esistenza di soluzioni che soddisfacessero i soli hard constraint. Successivamente si è considerato il problema di ottimizzazione nella sua interezza a ricercare la soluzione ottima considerando anche i soft constraint. 

L’esportazione delle soluzioni e una prima validazione di massima sono avvenute tramite un modulo dedicato all’export e una piccola applicazione web che tramite interfaccia grafica mostra il piano di allocazione settimanale per orientamento o per singolo docente. 



Nel Capitolo \ref{chapBackground} sono introdotte le tecnologie e i software utilizzati nella Tesi, partendo da un'analisi della letteratura informatica e procedendo con l'introduzione di due differenti classi di problemi in grado di modellare il problema dell'allocazione dell'orario.

Nel Capitolo \ref{chapDefinizioneProblema} vengono definiti tutti i requisiti del problema per poi essere suddivisi nelle due categorie di vincoli forti e deboli.

Nel Capitolo \ref{chapProgettazione} è introdotta la progettazione di alto livello tramite un modello UML. Viene inoltre introdotto un secondo modello UML per uniformare le sorgenti di dato del software e vengono definiti 

Nel Capitolo \ref{chapModellazione} vengono implementati a basso livello due modelli differenti per il problema in esame, sia in ambiente matematico che in ambiente di sviluppo andando a valutare pregi e difetti di entrambi.

Nel Capitolo \ref{chapModiUtilizzo} sono mostrate le modalità di utilizzo del software, sia in validazione che in ottimizzazione.

Infine nel Capitolo \ref{chapTesting} viene descritto il reperimento dei dati di test e dei dati ufficiali per l'Anno Accedemtico 2022-2023, l'utilizzo del tool per la risoluzione del problema, l'esportazione dei risultati e la loro validazione.

Nelle conclusioni di Capitolo~\ref{chapConclusioni} compaiono alcuni spunti per una futura espansione del modello e di miglioramento del software oltre ai manuali d’uso del software che mostrano tutte le opzioni che è possibile configurare ed i vincoli che è possibile aggiungere oltre ad indicare come espandere lo strumento con nuove funzioni. 


