Sperimentazione del Package CPLEX per la soluzione di Problemi di Programmazione Lineare Intera

Questa Tesi si inserisce nel settore di applicazione dell'Ottimizzazione Combinatoria, in particolare in quello della Programmazione Lineare Intera, e si dedica ad un aspetto specico della ricerca: la sperimentazione.
Sono state prese in esame due tematiche fondamentali dell'Ottimizzazione Combinatoria:
- il problema dello zaino
- il problema dell'assegnamento
Il problema dello zaino, più noto come problema di Knapsack, dato un insieme di elementi a ciascuno dei quali è stato assegnato un peso ed un profitto, consiste nel determinare un sottoinsieme di elementi che abbia profitto massimo ed il cui peso totale non superi un certo valore pressato. Il nome deriva dal fatto che viene usualmente descritto come il problema di scegliere quali oggetti di un dato insieme mettere in uno zaino in modo da non superare la capacità massima dello stesso e massimizzare il valore complessivo degli oggetti selezionati.
Nel problema dell'assegnamento sono dati due insiemi di elementi, con cardinalità non necessariamente uguale, e si deve associare ogni elemento dell'insieme più piccolo ad uno solo degli elementi dell'altro insieme; viceversa, ad ogni elemento dell'insieme più grande può essere associato al massimo un elemento dell'insieme più piccolo. Dato che ogni associazione ha un proprio costo, il problema consiste nell'individuare gli assegnamenti che minimizzano il costo totale nel pieno rispetto dei vincoli.
Questi due problemi hanno importanti applicazioni in ambito industriale, in particolar modo nella logistica e nella ripartizione dei carichi di lavoro, ma si adattano anche alle molteplici situazioni quotidiane.
La sperimentazione è stata interamente eseguita utilizzando CPLEX, un potente software di ottimizzazione avanzata, specico per la programmazione lineare mista e molto usato sia in ambienti industriali che di ricerca.