A Distributed Simplex Algorithm: Basic Concepts and Applications

September 27, 2011, room 2217, Enginering Bldg II

Mathias Burger

University of Stuttgart, Engineering Cybernetics


Recent advances in communication technology and the emergence of the multi-agent paradigm for control systems design, awoke new interest in solving optimization and coordination problems with distributed information structures. In this talk, I present a novel distributed algorithm to solve degenerate linear programs over asynchronous communication networks. The algorithm is a distributed version of the well known simplex algorithm for general linear programs. I also introduce a variation of the algorithm, which allows to handle structured problems with combinations of local and global constraints. Our algorithm can efficiently be applied to important problems, including the multi-agent assignment and the distributed pre-ordering problem.

Speaker's Bio

Mathias Bürger is a Ph.D. candidate at the University of Stuttgart, Germany, under the direction of Frank Allgöwer. He received is Dipl.-Ing. degree in Engineering Cybernetics from the University of Stuttgart in 2009. Before that, he visited as a DAAD fellow the University of Toronto and Queen's University, Kingston, Canada, and had a research stay at the Service Center for Automation Technologies of BASF SE. His research interests include distributed optimization methods and clustering analysis of dynamical networks.

Video URL: