Studio e implementazione di un algoritmo euristico per risolvere problemi MIP generali

Risolvere problemi di programmazione lineare intera (MIP) può risultare particolarmente complesso, sia per il tempo necessario a trovare una soluzione ottimale, sia per la difficoltà stessa di garantire che tale soluzione venga individuata. Per tali ragioni, l’idea alla base della progettazione di algoritmi euristici è quella di utilizzare una tecnica algoritmica che non sempre viene fondata su evenienze o principi matematici rigorosi. Con tali assunzioni si auspica all’individuazione di una soluzione ragionevolmente buona, che non sia per forza ottimale, in tempi altrettanto ragionevoli. In particolare, in questa tesi mi occuperò di fornire delle analisi sperimentali in merito a dei test effettuati su dei testbased di istanze di problemi MIP tramite un algoritmo euristico chiamato ACS (Alternating Criteria Search).