Passa ai contenuti principali

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!

Commenti

Post popolari in questo blog

PuLP – Un valido strumento per la didattica

L'insegnamento dei concetti di base della ricerca operativa, ovvero la programmazione lineare, ha trovato nel corso degli ultimi anni diversi strumenti di supporto. Sono ormai parecchi i software gratuiti e open source che permettono agli studenti e agli insegnanti di toccare con mano le nozioni e i concetti spiegati e studiati sui banchi. Ricordiamo, ad esempio, glpk che con il suoi linguaggio di modellazione MathProg permettete di scrivere e risolvere anche complessi modelli di programmazione lineare intera. Oppure citiamo anche lp_solve che con il suo ambiente impropriamente chiamato lp_solve IDE permette di scrivere e risolvere modelli di programmazione lineare direttamente nella formulazione matematica. A mio avviso però le proposte appena citate sono limitate nella potenza espressiva e nelle capacità di integrarsi con altri software o moduli esterni. Queste limitazioni sono egregiamente risolte da PuLP : un modellatore di problemi di programmazione lineare intera basato

Ci arricchiremo con la ricerca operativa?

A questa domanda forse possiamo rispondere sì :-) , rimandando al lavoro molto fresco ed interessante di Giancarlo Volpe dal titolo " Scommesse sportive: un modello di Ricerca Operativa che descrive la “vincita perfetta” " E' possibile scaricare il documento da scribd.com . Dall'apprezzabile contenuto didattico la parte entrale, dove si illustra passo passo come è possibile usare il risolutore di excel per applicarlo al modello descritto. Buona lettura e giocate con moderazione. Un Modello di Ricerca Operativa per Scommesse Sportive

Dispense di ricerca operativa

Ho trovato sulla home page del prof. Agnetis, delle interessanti dispense di ricerca operativa. I temi trattati sono tutti molto interessanti: Appunti sul duale del problema del massimo flusso Appunti sui problemi di matching Appunti su classi di complessità e problemi NP-completi Appunti sul problema del TSP euclideo Appunti sulla generazione di colonne Appunti sui modelli di lot sizing: Wagner-Whitin, Zangwill, Florian-Klein Appunti sui problemi di scheduling Appunti sui metodi metaeuristici di ricerca Introduzione all'ottimizzazione non vincolata   Introduzione all'ottimizzazione vincolata Esercizi di ottimizzazione non vincolata  Condizioni di KKT e Programmazione Lineare  Esercizi di ottimizzazione vincolata   Raccolta di esercizi di PL svolti  Esercizi di esame di PL svolti Esercizi di PLI svolti Appunti sui metodi basati sul rilassamento Lagrangiano Esercizi d'esame (R.O.) di ottimizzazione non vincolata e vincolata Ottimizzazione nella Gestione