Esperimenti su reduced cost fixing in Programmazione Lineare Intera

Il metodo di Reduced Cost Fixing, o più in generale Reduced Cost Tightening, rappresenta uno strumento migliorativo basilare impiegato in molti algoritmi risolutivi per problemi di programmazione lineare intera mista. In questo studio, dopo aver opportunamente introdotto alcune nozioni fondamentali della programmazione lineare e il concetto di costo ridotto, sono stati svolti due esperimenti con lo scopo di verificare le performance della strategia in questione. La maggior parte delle definizioni relative alla programmazione lineare derivano dalle dispense fornite dal prof. Domenico Salvagnin [12][13][14]. Gli esperimenti condotti hanno portato alla scrittura di uno script Python [11], tramite l’editor Visual Studio Code [8], attraverso il quale è stato possibile applicare l’algoritmo di fixing and tightening ad un pool di problemi di varie dimensioni e complessità. Sono stati utilizzati due test set, MIPLIB 2017 [9] e setpart che, grazie all’eterogeneità dei problemi in essi contenuti, hanno permesso di ricavare dati sperimentali il più possibile generali. Attraverso il primo esperimento è stato possibile ottenere dei dati sull’efficienza dell’algoritmo in un ambiente ideale, mentre il secondo è stato utile per avere un’idea, sul possibile miglioramento delle performance, in caso di riformulazione della strategia di fixing tramite l’impiego di un gap dimezzato. Attraverso i dati raccolti e i grafici riassuntivi, e comparativi, è stato infine possibile trarre alcune conclusioni ed evidenziare alcuni possibili sviluppi e impieghi futuri.