Three Topics in Mixed Integer Programming

Credo che possa interessare a molti la tesi di dottorato di Arrigo Zanette, disponibile presso il sito dell'Università di Padova, dal titolo "Three Topics in Mixed Integer Programming".

Per comodità riporto l'abstract in italiano:

Nel presente lavoro di tesi descriviamo i nostri contributi su tre argomenti di Mixed Integer Programming (MIP).
Nel capitolo intitolato "Lexicography and degeneracy: Can a pure cutting plane algorithm work?" discutiamo una implementazione della versione lessicografica del metodo dei piani di taglio di Gomory per problemi di Integer Linear Programming (ILP) e due euristiche. Nei test computazionali su una batteria di istanze della libreria MIPLIB confrontiamo la performance dei metodi implementati col l'algoritmo standard di Gomory, sia nella versione a singolo taglio che nella versione multi taglio (round di tagli), e mostriamo che le nostre implementazioni producono un miglioramento radicale sulla procedura standard. In particolare riportiamo la soluzione esatta di istanze ILP come stein15, stein27 e bm23, per le quali l'algoritmo standard di Gomory non è in grado di chiudere se non una piccola frazione del gap di integralità. Inoltre forniamo un'interpretazione di questo sorprendente fenomeno.
Nel capitolo intitolato "Minimal Infeasible Subsystems and Benders cuts", prendendo ispirazione dai metodi cutting plane generalmente usati in MIP, proponiamo nuovi criteri di selezione per i tagli di Benders, e li analizziamo computazionalmente. Il nostro approccio si basa sulla corrispondenza tra sistemi minimamente infeasible di un problema lineare infeasible, e i vertici del così detto poliedro delle alternative. La scelta del taglio di Benders violato "più efficace" corrisponde quindi alla selezione di un vertice opportuno nel poliedro delle alternative, da cui segue che è cruciale una scelta intelligente della funzione obiettivo duale--mentre l'approccio di Benders textbook usa una politica di scelta completamente casuale. Nei test computazionali mostriamo che il metodo proposto consente uno speedup da 1 a 2 ordini di grandezza rispetto all'implementazione textbook.
Nel capitolo intitolato "Fast Approaches to Improve the Robustness of a Railway Timetable", ci occupiamo del problema di trovare una tabella oraria robusta in ambito ferroviario. Il Train Timetabling Problem (TTP) consiste nel trovare uno schedule dei treni di una rete ferroviaria che soddisfi dei vincoli operativi e massimizzi una funzione di profitto che stimi l'efficienza dell'uso dell'infrastruttura. Tuttavia la massimizzazione della funzione obiettivo può non essere sufficiente e si può voler trovare una soluzione robusta, ovvero capace di assorbire il più possibile i ritardi/disturbi sulla rete. A tal fine, proponiamo e analizziamo computazionalmente quattro diversi metodi per migliorare la robustezza di una data soluzione di TTP. Gli approcci combinano Programmazione Lineare e tecniche ad-hoc di Stochastic Programming/Robust Optimization. I risultati computazionali su istanze reali mostrano che due delle tecniche proposte sono molto veloci e forniscono soluzioni robuste di qualità comparabile con un approccio di Stochastic Programming standard ma computazionalmente molto più oneroso.

Buona lettura a tutti!