Abstract

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.

Autore Pugliese

• Notarstefano Giuseppe

Tutti gli autori

• M. Bürger , G. Notarstefano , F. Bullo , F. Allgöwer

Titolo volume/Rivista

AUTOMATICA

Anno di pubblicazione

2012

ISSN

0005-1098

ISBN

Non Disponibile

Numero di citazioni Wos

28

Ultimo Aggiornamento Citazioni

25/04/2018

Numero di citazioni Scopus

32

Ultimo Aggiornamento Citazioni

26/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile