Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(18)
Algorithm Design
Assignment Problem
Convex Programming
Degeneration
Distributed Algorithm
Distributed Computing
Distributed Optimization
Information Exchange
Interior Point Algorithm
Linear Constraint
Optimal Algorithm
Optimality Theory
Quadratic Program
Simplex Algorithm
Task Assignment
Time Scale
Linear Program
Multi Agent System
Subscribe
Academic
Publications
A distributed simplex algorithm and the multiagent assignment problem
A distributed simplex algorithm and the multiagent assignment problem,Mathias Burger,Giuseppe Notarstefano,Frank Allgower,Francesco Bullo
Edit
A distributed simplex algorithm and the multiagent assignment problem
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Mathias Burger
,
Giuseppe Notarstefano
,
Frank Allgower
,
Francesco Bullo
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 multiagent
task assignment
problem and show that it can be solved by means of our distributed simplex algorithm. I. INTRODUCTION The increasing interest in performing complex tasks via multi
agent systems
(e.g. sensor and robotic networks) has raised the interest in solving
distributed optimization
problems. The funda mental paradigms in distributed computation are that: (i) infor mation, relevant for the solution of the problem, is distributed all over a network of processors with limited memory and computation capability, and (ii) the overall computation relies only on local com putation and
information exchange
amongst neighboring processors. Optimizing linear objectives over linear constraints takes a central role in the optimization literature and thus deserves particular attention also in distributed computation. In this paper we consider a distributed version of linear programs. In particular, we consider linear programs in standard form where the number of decision variables is much larger than the number of equality constraints. Each processor in the network is assigned only the information relative to a subset of the decision variables. The objective is to agree on a global minimum of the problem, if it exists, or agree that the problem is either unbounded or infeasible. Particular attention is given to degenerate linear programs, in which more than one solution is optimal and a mutual agreement of all agents on one solution is required. Although distributed and parallelized optimization algorithms have been studied for a long time, see e.g. (2), the multiagent perspective has recently become subject of renewed interest in the control and optimization theory community. While several
interior point
algorithms were proposed to solve quadratic programs and other convex programs (3), (4), (5), (6), to the best of our knowledge a theory for distributed linear programming is missing. The idea of parallelizing and distributing the computation of the simplex M. B¨ urger and F. Allg¨
Published in 2011.
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(1)
...The research contribution in the coordinated patrolling activity during this working period has focused on two main aspects: i) develop distributed algorithms for distributed task assignment among the vehicles during the patrolling [
8
], and ii) develop cooperative control law that guarantee containment in a leader follower scenario [16]...
Andreas Birk
,
et al.
The CO3AUVs (Cooperative Cognitive Control for Autonomous Underwater V...
References
(14)
Distributed Abstract Optimization via Constraints Consensus: Theory and Applications
(
Citations: 1
)
Giuseppe Notarstefano
,
Francesco Bullo
Journal:
IEEE Transactions on Automatic Control  IEEE TRANS AUTOMAT CONTR
, vol. 56, no. 10, pp. 22472261, 2011
Parallel and Distributed Computation: Numerical Methods
(
Citations: 1747
)
D. P. Bertsekas
,
J. N. Tsitsiklis
Published in 1989.
Constrained Consensus and Optimization in MultiAgent Networks
(
Citations: 35
)
Angelia Nedic ´
,
Asuman Ozdaglar
,
Pablo A. Parrilo
Journal:
IEEE Transactions on Automatic Control  IEEE TRANS AUTOMAT CONTR
, vol. 55, no. 4, pp. 922938, 2010
Distributed Subgradient Methods for MultiAgent Optimization
(
Citations: 85
)
A. Nedic
,
Asuman Ozdaglar
Journal:
IEEE Transactions on Automatic Control  IEEE TRANS AUTOMAT CONTR
, vol. 54, no. 1, pp. 4861, 2009
On distributed convex optimization under inequality and equality constraints via primaldual subgradient methods
(
Citations: 9
)
Minghui Zhu
,
Sonia Martinez
Published in 2010.
Sort by:
Citations
(1)
The CO3AUVs (Cooperative Cognitive Control for Autonomous Underwater Vehicles) project: Overview and current progresses
Andreas Birk
,
Gianluca Antonelli
,
Andrea Caiti
,
Giuseppe Casalino
,
Giovanni Indiveri
,
Antonio Pascoal
,
Andrea Caffaz
Conference:
OCEANS  Europe  EUROPE
, 2011