Control of large-scale MLD systems via multi-agent reformulation and decentralized optimization

This thesis addresses the optimal control of large-scale engineering systems that can be found in a variety of domains and, in particular, in the energy sector. We consider systems involving physical and logical components and described by linear equations and inequalities involving both discrete and continuous state and input variables. If also operational constraints and specifications are expressed in terms of linear inequalities, then, one can adopt the Mixed Logical Dynamical (MLD) system modeling framework and translate the optimal control problem into a Mixed Integer Program (MIP), which is linear (hence a MILP) if the performance index is also linear. Since the complexity of a MIP is intrinsically combinatorial and grows exponentially with the number of discrete decision variables, optimal control of an MLD system becomes computationally intensive or even prohibitive when its size increases, thus calling for appropriate resolution strategies. Additionally, if the MLD is affected by uncertainty only known from data, then one needs to devise solutions that are determined based on observed uncertainty instances but yet robust against unseen ones. In this work, we propose an optimization framework that faces the combinatorial complexity arising in the optimal operation of large-scale MLD systems by taking advantage of the structure (if any) of the problem at hand to decompose it in smaller partially coupled sub-problems and recover computational tractability via decentralized solution-seeking schemes. The decomposition strategy aims at disclosing the (hidden) partially separable structure of a linearly constrained optimization program via manipulation of its constraint matrix. Similarly to standard schemes, it translates the matrix permutation problem into a graph partitioning problem by means of a suitable graph representation of the sparsity pattern of the matrix at hand. The graph partitioning, however, is performed via a novel strategy that attributes a probability to the arcs in the graph based on the matrix structure and identifies clusters of nodes based on the similarity between the evolutions of the probability distribution vectors obtained by initializing a random walk at each node. For those instances of the optimal MLD operation problem that can be reformulated as a multi-agent constraint-coupled MILP, we propose novel computationally efficient decentralized optimization schemes that distribute computation among the agents, with a coordinating unit enforcing the coupling constraint. These schemes can also be applied to the case of an actual multi-agent system. In such a setting, privacy of information may be a concern, and the fact that the proposed schemes do not require the agents to share with the central unit any information related to their individual operational limitation and contribution to the performance index can then be of interest. We then broaden our scope and consider non-convex problems characterized by a scalar complicating constraint, i.e., such that its removal from the formulation simplifies the resolution of the problem. We propose an iterative bisection method for the dual problem that generates a sequence of feasible primal solutions with a cost that improves throughout iterations. Application to multi-agent problems with a scalar coupling constraint results in a decentralized resolution scheme where a central unit is in charge of the update of the (scalar) dual variable while agents compute their local primal variables. Finally, we consider the case when uncertainty is affecting the local constraints of a multi-agent constraint-coupled system and derive probabilistic feasibility guarantees for the decentralized solution to the optimization program obtained by enforcing the local constraints only for the uncertainty instances available to each agent. The generalization properties of the data-based privacy-preserving solution are shown to depend on the size of each local dataset and on the complexity of the uncertain individual constraint sets. Explicit bounds are derived in the case of linear individual constraints. The methods introduced in the thesis are supported via a solid theoretical analysis. Their effectiveness and applicability are showcased via extensive simulations on realistic applications in the energy sector that inspired our work.