Abstract

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.

Autore Pugliese

• Notarstefano Giuseppe

Tutti gli autori

• M. Burger , G. Notarstefano , F. Allgower , F. Bullo

Titolo volume/Rivista

PROCEEDINGS OF THE AMERICAN CONTROL CONFERENCE

Anno di pubblicazione

2011

ISSN

0743-1619

ISBN

Non Disponibile

Numero di citazioni Wos

5

Ultimo Aggiornamento Citazioni

28/04/2018

Numero di citazioni Scopus

14

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile