MATHEMATICAL PROGRAMMING METHODS FOR PARTIALLY UNDEFINED OPTIMIZATION MODELS

This thesis proposes novel methods for formulating and solving partially undefined mathematical programming models. By leveraging mathematical programming methods and off-the-shelf solvers, we aim to automate the process of generating compact algebraic representations for unknown components. Our approach addresses limitations of existing methods, such as lack of interpretability and control over model complexity. We explore various learning scenarios, including static and interactive settings, and consider both objective function and constraint learning. Our contributions include: - static constraint learning – we develop methods to approximate unknown convex polyhedra from positive and negative data points, using mixed-integer linear programming and column generation; - interactive constraint learning – we design algorithms to solve 0-1 linear programs with missing constraints and learn surrogate constraints, using an oracle-based approach inspired by active learning techniques; - online objective learning – we propose a novel algorithm based on mixed-integer linear programming for online facility location with non-linear profit functions. Our work advances the field of automatic mathematical programming model formulation and provides practical tools for solving complex optimization problems with incomplete information.

Questa tesi propone nuovi metodi per formulare e risolvere modelli di programmazione matematica parzialmente indefiniti. Mediante l'utilizzo di metodi di programmazione matematica e solutori per modelli di programmazione lineare e quadratica, puntiamo ad automatizzare il processo di generare rappresentazioni algebriche compatte per componenti ignote. Il nostro approccio copre limitazioni dei metodi esistenti, quali scarsa interpretabilità e limitato controllo sulla complessità del modello. Esploriamo diversi scenari di apprendimento, che includono situazioni statiche e dinamiche, e consideriamo sia l'apprendimento di funzioni obiettivo che di vincoli. I nostri contributi includono: - apprendimento statico di vincoli – sviluppiamo metodi per approssimare poliedri convessi ignoti da punti positivi e negativi, usando programmazione lineare misto-intera e column generation; - apprendimento di vincoli interattivo – ideiamo algoritmi per risolvere programmi lineari 0-1 con vincoli mancanti ed imparare vincoli surrogati, usando un approccio basato su oracolo ispirato a tecniche di apprendimento attivo; - apprendimento online di funzioni obiettivo – proponiamo un algoritmo inedito basato su programmazione lineare misto-intera per un problema di facility location online con funzioni di profitto non lineari. Il nostro lavoro apporta contributi al campo della formulazione automatica di modelli di programmazione matematica e fornisce strumenti pratici per risolvere problemi di ottimizzazione complessi con informazione incompleta.