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.

A distributed simplex algorithm for degenerate linear programs and multi-agent assignments / Mathias Bürger; Giuseppe Notarstefano; Francesco Bullo; Frank Allgöwer. - In: AUTOMATICA. - ISSN 0005-1098. - STAMPA. - 48:(2012), pp. 2298-2304. [10.1016/j.automatica.2012.06.040]

A distributed simplex algorithm for degenerate linear programs and multi-agent assignments

Giuseppe Notarstefano;
2012

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.
2012
A distributed simplex algorithm for degenerate linear programs and multi-agent assignments / Mathias Bürger; Giuseppe Notarstefano; Francesco Bullo; Frank Allgöwer. - In: AUTOMATICA. - ISSN 0005-1098. - STAMPA. - 48:(2012), pp. 2298-2304. [10.1016/j.automatica.2012.06.040]
Mathias Bürger; Giuseppe Notarstefano; Francesco Bullo; Frank Allgöwer
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/671807
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 79
  • ???jsp.display-item.citation.isi??? 66
social impact