Locally Constrained Decision Making via Two-Stage Distributed Simplex

In this paper we propose a distributed algorithm for solving linear programs with combinations of local and global constraints in a multi-agent setup. A fully distributed and asynchronous algorithm is proposed. The computation of the local decision makers involves the solution of two distinct (local) optimization problems, namely a local copy of a global linear program and a smaller problem used to generate ”problem columns”. We show that, when running the proposed algorithm, all decision makers agree on a common optimal solution, even if the original problem has several optimal solutions, or detect unboundedness and infeasibility if necessary.