  We address the optimal design of a large scale multi-agent system where each
agent has discrete and/or continuous decision variables that need to be set so
as to optimize the sum of linear local cost functions, in presence of linear
local and global constraints. The problem reduces to a Mixed Integer Linear
Program (MILP) that is here addressed according to a decentralized iterative
scheme based on dual decomposition, where each agent determines its decision
vector by solving a smaller MILP involving its local cost function and
constraint given some dual variable, whereas a central unit enforces the global
coupling constraint by updating the dual variable based on the tentative primal
solutions of all agents. An appropriate tightening of the coupling constraint
through iterations allows to obtain a solution that is feasible for the
original MILP. The proposed approach is inspired by a recent method to the MILP
approximate solution via dual decomposition and constraint tightening, and
presents the advantage of guaranteeing feasibility in finite-time and providing
better performance guarantees. The two approaches are compared on a numerical
example on plug-in electric vehicles optimal charging.
