A distributed simplex algorithm and the multi-agent assignment problem

A distributed simplex algorithm and the multi-agent assignment problem,Mathias Burger,Giuseppe Notarstefano,Frank Allgower,Francesco Bullo

A distributed simplex algorithm and the multi-agent assignment problem   (Citations: 1)
BibTex | RIS | RefWorks Download
In this paper we propose a novel distributed algorithm to solve degenerate linear programs on asynchronous networks. Namely, we propose a distributed version of the well known simplex algorithm. We prove its convergence to the global lexicographic minimum for possibly fully degenerate problems and provide simulations supporting the conjecture that the completion time scales linearly with the diameter of the graph. The algorithm can be interpreted as a dual version of the constraints consensus algorithm proposed in (1) to solve abstract programs when the last is applied to linear programs. Finally, we study a multi-agent task assignment problem and show that it can be solved by means of our distributed simplex algorithm. I. INTRODUCTION The increasing interest in performing complex tasks via multi- agent systems (e.g. sensor and robotic networks) has raised the interest in solving distributed optimization problems. The funda- mental paradigms in distributed computation are that: (i) infor- mation, relevant for the solution of the problem, is distributed all over a network of processors with limited memory and computation capability, and (ii) the overall computation relies only on local com- putation and information exchange amongst neighboring processors. Optimizing linear objectives over linear constraints takes a central role in the optimization literature and thus deserves particular attention also in distributed computation. In this paper we consider a distributed version of linear programs. In particular, we consider linear programs in standard form where the number of decision variables is much larger than the number of equality constraints. Each processor in the network is assigned only the information relative to a subset of the decision variables. The objective is to agree on a global minimum of the problem, if it exists, or agree that the problem is either unbounded or infeasible. Particular attention is given to degenerate linear programs, in which more than one solution is optimal and a mutual agreement of all agents on one solution is required. Although distributed and parallelized optimization algorithms have been studied for a long time, see e.g. (2), the multi-agent perspective has recently become subject of renewed interest in the control and optimization theory community. While several interior point algorithms were proposed to solve quadratic programs and other convex programs (3), (4), (5), (6), to the best of our knowledge a theory for distributed linear programming is missing. The idea of parallelizing and distributing the computation of the simplex M. B¨ urger and F. Allg¨
Published in 2011.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The research contribution in the coordinated patrolling activity during this working period has focused on two main aspects: i) develop distributed algorithms for distributed task assignment among the vehicles during the patrolling [8], and ii) develop cooperative control law that guarantee containment in a leader follower scenario [16]...

    Andreas Birket al. The CO3AUVs (Cooperative Cognitive Control for Autonomous Underwater V...

Sort by: