MATHEMATICAL PROGRAMMING METHODS FOR PARTIALLY UNDEFINED OPTIMIZATION MODELS

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.

Grantor dc:publisher

Università degli Studi di Milano

Year dc:date

2024

Author dc:creator

• MESSANA, ROSARIO

Contributors dc:contributor

• tutor: A. Ceselli ; coordinatore: R. Sassi
• R. Messana
• CESELLI, ALBERTO
• SASSI, ROBERTO

• mathematical programming
• data-driven optimization
• machine learning
• linear programming
• integer programming
• 0-1 linear programming
• combinatorial optimization
• dantzig-wolfe
• column generation
• polyhedral separation
• constraint learning
• objective learning
• active learning
• oracle-based optimization
• online learning
• non-convex optimization
• online combinatorial optimization
• knapsack problem
• generalized assignment problem
• facility location
• edge computing
• Settore INF/01 - Informatica

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

http://dx.doi.org/10.13130/messana-rosario_phd2024-12-04
10.13130/messana-rosario_phd2024-12-04

OAI identifier oai:identifier

oai:air.unimi.it:2434/1119904