A data-driven decentralized solution to uncertain multi-agent MILPs with a vehicle-to-grid application

This thesis addresses multi-agent optimization problems affected by uncertainty that can be formulated as Mixed Integer Linear Programs (MILPs) with an al- most separable structure. More specifically, the cost function is the sum of the agents’ local cost functions and constraints are both local and global, the latter kind creating a coupling in the agents’ local optimization variables. Scalable approaches to tackle the combinatorial complexity of the resulting MILP have been recently developed in the distributed optimization literature with reference to the deterministic case. The presence of uncertainty in large- scale optimization problems has been instead addressed according to a distributed approach only in a convex set-up (hence without discrete optimization variables). In this thesis, we fill in this gap by proposing a data-driven decentralized scheme to determine a solution that is feasible for all uncertainty instances except for a set whose probability depends on the size of the data-set, according to a certain bound. The efficacy of the proposed solution strategy is shown via simulation on a vehicle-to-grid case study, which also highlights the privacy-preserving feature of the decentralized implementation.

Questa tesi affronta problemi multi-agente affetti da incertezza che possono essere formulati come problemi di programmazione lineare mista intera (MILP – Mixed Integer Linear Program), con una struttura quasi separabile. In particolare, la funzione di costo è la somma delle funzioni di costo locali di ogni agente, e i vincoli sono sia locali che globali, con questi ultimi che creano un accoppiamento tra le variabili di ottimizzazione dei singoli agenti. Nell’ambito dell’ottimizzazione distribuita, sono stati sviluppati di recente approcci scalabili per far fronte alla complessità combinatoria di questa tipologia di MILP, con riferimento al caso deterministico. Problemi di ottimizzazione di larga scala affetti da incertezza sono stati invece affrontati con tecniche di ot- timizzazione distribuita solo sotto ipotesi di convessità (e quindi in assenza di variabili di ottimizzazione discrete). In questa tesi si colma questa lacuna introducendo uno schema decentraliz- zato che si basa sulle osservazioni disponibili dell’incertezza per calcolare una soluzione. Tale soluzione è garantita essere ammissibile anche per le realizzazioni di incertezza non viste, ad eccezione di un insieme la cui probabilità dipende secondo una certa legge dalla numerosità dei dati utilizzati. L’efficacia del metodo proposto viene dimostrata per simulazione con riferi- mento ad un’applicazione vehicle-to-grid, che consente anche di mettere in luce come l’implementazione decentralizzata preservi la riservatezza dei dati.