Automatic matrix decomposition for reducing performance variability in mixed-interger programming solvers

When it comes to modelling optimization problems for real-world scenarios coming from sectors like finance, production planning or network design it is necessary to have integer variables. This makes Mixed-Integer Programming essential when we want to solve optimization problems in these fields. Extensive research has been conducted into how these problems should be formulated and various improvements to the algorithms used to solve them have been made during the last 50 years. Nevertheless, there is a feature which has been discovered more recently that has not been addressed much in research papers so far. We are talking about performance variability, which stands for different runtimes measured when solving shuffled but mathematically equivalent versions of the same problem. This thesis aims to build a framework to experiment with various optimization problem instances, investigate the causes of performance variability more thoroughly, and try to mitigate its effect through the reorderings of rows and columns of problem coefficient matrices. The framework allowed us to simulate adversarial behaviour where, given a problem instance, we generated different equivalent forms according to well-defined transformations. Once done with that, we experimented with different methods to rearrange rows and columns of the different forms in order to reach a unique form which ideally would lead to more stable solving times. While doing that, we not only measured runtime variability but we also tried to define other metrics based on matrices structures that were correlated with solve time variability, and gave us more information about what are the features of a problem that influence solver behaviour. Doing that, we tried to get a better understanding of the transformations that occur to coefficients matrices when processed by state-of-the-art solver software.

Quando si tratta di modellare problemi di ottimizzazione che emergono da scenari del mondo reale provenienti da settori come la finanza, la pianificazione della produzione o la progettazione di reti, è necessario utilizzare variabili intere. Questo rende la Programmazione Mista Intera (Mixed-Integer Programming) indispensabile quando si vogliono risolvere problemi di ottimizzazione in questi ambiti. Negli ultimi 50 anni sono state condotte ricerche approfondite su come questi problemi dovrebbero essere formulati e sono stati apportati numerosi miglioramenti agli algoritmi utilizzati per risolverli. Tuttavia, esiste una caratteristica emersa più recentemente che finora non è stata affrontata in modo significativo nella letteratura scientifica. Stiamo parlando della variabilità delle prestazioni, ovvero della differenza nei tempi di esecuzione misurati quando si risolvono formulazioni matematicamente equivalenti dello stesso problema ottenute riordinando le righe e le colonne. Questa tesi si propone di costruire un framework per sperimentare con varie istanze di problemi di ottimizzazione, indagare meglio le cause della variabilità delle prestazioni e cercare di mitigarne l’effetto attraverso il riordinamento di righe e colonne della matrice dei coefficienti del problema. Il framework ci ha permesso di simulare un comportamento avversario in cui, data un’istanza di problema, generiamo diverse forme equivalenti secondo trasformazioni ben definite. Una volta fatto ciò, sperimenteremo con diversi metodi per riordinare le righe e le colonne delle varie forme al fine di ottenere una forma unica che, idealmente, porterà a tempi di risoluzione più stabili. Nel fare ciò, non ci siamo limitati a misurare la variabilità del tempo di esecuzione, ma cercheremo anche di definire altre metriche basate sulla struttura delle matrici che siano correlate con la variabilità del tempo di risoluzione. Queste metriche ci forniranno maggiori informazioni sulle caratteristiche di un problema che influenzano il comportamento del risolutore, permettendoci così di comprendere meglio le trasformazioni subite dalle matrici dei coefficienti durante l’elaborazione da parte degli algoritmi più avanzati disponibili oggi.