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.

A distributed simplex algorithm and the multi-agent assignment problem

G. Notarstefano;
2011

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.
2011
IEEE American Control Conference
2639
2644
M. Burger; G. Notarstefano; F. Allgower; F. Bullo
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/671995
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 9
social impact