Handling Complexity in Large-Scale Cyber-Physical Systems Through Distributed Computation

We consider the optimal operation of constrained cyber-physical systems that can be described by a mixed logical dynamical model with a linear cost. When the number of discrete decision variables is large, the resulting mixed-integer linear program (MILP) is hard -- if not even impossible -- to solve in practice. In this chapter, we focus on large-scale MILPs with a multi-agent structure and propose a resolution scheme that recovers computability by decomposition of the problem into multiple lower-dimensional MILPs, one per subset of decision variables associated with an agent. If the discrete decision variables are equally divided among the resulting sub-MILPs, then distributed optimization can prove effective in providing a feasible solution to the original MILP. Also, a bound on the possible performance degradation is provided which is tighter as the ratio between the number of coupling constraints and the number of agents decreases. The introduced resolution scheme is compared with a recently proposed alternative on an application to charging of plug-in electric vehicles. Results show that the proposed approach always performs better than its competitor irrespective of the number of agents and parameters.