Three Topics in Mixed Integer Programming

In chapter entitled "Lexicography and degeneracy: Can a pure cutting plane algorithm work?", we discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method for Integer Linear Programming (ILP) problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprising phenomenon. In chapter entitled "Minimal Infeasible Subsystems and Benders cuts", taking inspiration from general cutting plane methods for MIP, we propose alternative selection criteria for Benders cuts, and analyze them computationally. Our approach is based on the correspondence between minimal infeasible subsystems of an infeasible Linear Program, and the vertices of the so-called alternative polyhedron. The choice of the "most effective" violated Benders cut then corresponds to the selection of a suitable vertex of the alternative polyhedron, hence a clever choice of the dual objective function is crucial--whereas the textbook Benders approach uses a completely random selection policy, at least when the so-called feasibility cuts are generated. Computational results on a testbed of MIPLIB instances are presented. We show that the proposed methods allow for a speedup of 1 to 2 orders of magnitude with respect to a textbook implementation. In chapter entitled "Fast Approaches to Improve the Robustness of a Railway Timetable", we address the problem of finding a robust train timetable. The Train Timetabling Problem (TTP) consists in finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function which counts for the efficiency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network. We propose and analyze computationally four different methods to improve the robustness of a given TTP solution. The approaches combine Linear Programming (LP) and ad-hoc Stochastic Programming/Robust Optimization techniques. The computational results on real-world instances show that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) Stochastic Programming approach.

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.