Large-scale MILP solution via a multi-agent reformulation

Mixed Integer Linear Programs (MILPs) arise in different contexts and engineering applications and allow to formulate a variety of decision-making problems involving systems comprising continuous and logical components. If the system is large-scale, however, the resulting MILP is typically hard to solve because of its combinatorial complexity due to the presence of integer decision variables: finding an optimal solution is often not viable in practice, and one has to resort to heuristic approaches to recover computational tractability and find a solution that is – at least – feasible. This issue has been also addressed in recent works on decentralized optimization for multi-agent systems. In particular, an approach has been proposed for computing a feasible solution to constraint-coupled multi-agent MILPs, while quantifying its sub-optimality level. In a constraint-coupled multi-agent MILP, multiple agents cooperatively aim at optimizing the sum of their individual cost functions with respect to local decision variables subject to both individual and global constraints originating from resource sharing. The introduced decentralized strategy reduces the overall large-scale MILP to multiple lower-dimensional ones (one per agent) that are repeatedly solved a finite number of times by the agents while exchanging information on the coupling constraints. The strategy is most effective if the number of agents is large compared to the number of coupling constraints. In this thesis, we propose a resolution scheme for a large-scale MILP with a hidden constraint-coupled multi-agent structure: such a structure is recovered first, and then the previously mentioned decentralized optimization scheme is applied. In order to disclose the hidden constraint-coupled multi-agent structure, we need to manipulate the matrix defining the linear (local and global) constraints and reduce it to a singly-bordered block-angular form, where the blocks define both local constraints and local decision variables of the fictitious agents, whereas the border corresponds to the coupling constraints. We translate the matrix reformulation problem into a hyper-graph partitioning problem and introduce a novel partitioning algorithm that accounts for the specific requirements of our setting: i) maximize the number of fictitious agents while minimizing the border size, and ii) evenly distribute the discrete decision variables among the agents so as to uniformly split the computational load. Performance of the novel partitioning strategy in terms of quality of the obtained result, sensitivity with respect to user-defined parameters, and computational time is assessed through extensive simulations.

I programmi lineari misto-interi (MILPs) si presentano in diversi contesti e applicazioni ingegneristiche e permettono di formulare una grande varietà di problemi decisionali che coinvolgono sistemi formati da componenti continue e discrete. Tuttavia, nel caso di sistemi di larga scala il MILP risultante è tipicamente difficile da risolvere a causa della sua complessità combinatoria, dovuta alla presenza di variabili decisionali intere: spesso trovare una soluzione ottima non è possibile in pratica ed è necessario ricorrere ad approcci euristici per recuperare la trattabilità computazionale e trovare una soluzione che sia almeno ammissibile, cioè compatibile con tutti i vincoli. Questo problema è stato affrontato anche in articoli recenti relativi all'ottimizzazione decentralizzata per sistemi multi-agente. In particolare, è stato proposto un approccio per calcolare una soluzione ammissibile per MILP multi-agente con vincoli di accoppiamento, quantificando il suo livello di sub-ottimalità. In un MILP multi-agente con vincoli di accoppiamento, gli agenti collaborano per ottimizzare la somma delle loro funzioni di costo individuali, agendo sulle rispettive variabili decisionali locali e rispettando sia vincoli individuali che globali, originati dalla condivisione delle risorse. La strategia decentralizzata introdotta riduce il MILP globale di larga scala a un insieme di sotto-problemi di dimensione inferiore (uno per agente) che vengono risolti ripetutamente un numero finito di volte dagli agenti, scambiando informazioni sui vincoli di accoppiamento. Tanto maggiore è il numero di agenti rispetto al numero di vincoli di accoppiamento, tanto più efficace la strategia. In questa tesi, proponiamo uno schema di risoluzione per MILP di larga scala che hanno una struttura nascosta multi-agente con vincoli di accoppiamento: tale struttura viene prima evidenziata, per poi applicare lo schema di ottimizzazione decentralizzato citato in precedenza. Al fine di rivelare la struttura multi-agente nascosta, è necessario manipolare la matrice che definisce i vincoli lineari e ridurla a una forma blocco-angolare a bordo singolo, dove i blocchi definiscono sia i vincoli locali che variabili di decisione locali degli agenti fittizi, mentre il bordo corrisponde ai vincoli di accoppiamento. Il problema di riformulazione della matrice viene tradotto in un problema di partizionamento di un iper-grafo e viene introdotto un nuovo algoritmo di partizionamento che tiene conto dei requisiti specifici dello scenario considerato: i) massimizzare il numero di agenti fittizi riducendo al minimo la dimensione del bordo e ii) distribuire uniformemente le variabili decisionali discrete tra gli agenti in modo da dividere uniformemente il carico computazionale. Le prestazioni della nuova strategia di partizionamento vengono valutate in simulazione, in termini di qualità del risultato ottenuto, sensibilità rispetto ai parametri definiti dall'utente e tempo di calcolo.