A distributed simplex algorithm for degenerate linear programs and multi-agent assignments
详细信息 查看全文
- 作者：Mathias B¨¹rger ; Giuseppe Notarstefano ; Francesco Bullo ; Frank Allg?wer
- 关键词：Distributed simplex ; Distributed linear programming ; Asynchronous algorithm ; Multi-agent task assignment
- 刊名：Automatica
- 出版年：2012
- 出版时间：September, 2012
- 年：2012
- 卷：48
- 期：9
- 页码：2298-2304
- 全文大小：957 K
文摘
In this paper we propose a novel distributed algorithm to solve degenerate linear programs on asynchronous peer-to-peer networks with distributed information structures. We propose a distributed version of the well-known simplex algorithm for general degenerate linear programs. A network of agents, running our algorithm, will agree on a common optimal solution, even if the optimal solution is not unique, or will determine infeasibility or unboundedness of the problem. We establish how the multi-agent assignment problem can be efficiently solved by means of our distributed simplex algorithm. We provide simulations supporting the conjecture that the completion time scales linearly with the diameter of the communication graph.