A sampling-based algorithm for integer linear optimization

This thesis explores the development of a heuristic approach for solving Mixed-Integer Programming (MIP) problems, inspired by concepts originally formulated within the field of balanced sampling. The work aims to investigate whether a method designed to preserve statistical balance through probabilistic mechanisms can be effectively adapted to guide the search for feasible solutions in mathematical optimization. This interdisciplinary perspective connects ideas from statistics, linear algebra, and optimization, with the goal of bridging the gap between sampling theory and heuristic problem solving. The proposed approach reinterprets the geometric and stochastic principles of the Cube method within an optimization framework, testing its performance on both linear and quadratic benchmark problems. The experimental results highlight the challenges and potential of this adaptation, showing that while the method faces structural limitations in classical MIP settings, it opens promising directions for quadratic and nonlinear formulations. Overall, the study contributes to a broader understanding of how sampling-based reasoning can inform the design of heuristic optimization strategies.

Questa tesi esplora lo sviluppo di un approccio euristico per la risoluzione di problemi di programmazione mista intera (MIP), ispirato a concetti originariamente formulati nel campo del campionamento bilanciato. Il lavoro mira a indagare se un metodo progettato per preservare l’equilibrio statistico attraverso meccanismi probabilistici possa essere efficacemente adattato per guidare la ricerca di soluzioni ammissibili nell’ottimizzazione matematica. Questa prospettiva interdisciplinare collega idee provenienti dalla statistica, dall’algebra lineare e dall’ottimizzazione, con l’obiettivo di colmare il divario tra la teoria del campionamento e la risoluzione euristica dei problemi. L’approccio proposto reinterpreta i principi geometrici e stocastici del metodo del cubo all’interno di un quadro di ottimizzazione, testandone le prestazioni su problemi di benchmark sia lineari che quadratici. I risultati sperimentali evidenziano le sfide e il potenziale di questo adattamento, dimostrando che, sebbene il metodo presenti limitazioni strutturali nelle impostazioni MIP classiche, apre direzioni promettenti per formulazioni quadratiche e non lineari. Nel complesso, lo studio contribuisce a una più ampia comprensione di come il ragionamento basato sul campionamento possa informare la progettazione di strategie di ottimizzazione euristica.