The Experts below are selected from a list of 13290 Experts worldwide ranked by ideXlab platform
Frank Allgöwer - One of the best experts on this subject based on the ideXlab platform.
-
a distributed Simplex Algorithm for degenerate linear programs and multi agent assignments
Automatica, 2012Co-Authors: Mathias Bürger, Giuseppe Notarstefano, Francesco Bullo, Frank AllgöwerAbstract: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 and the multi-agent assignment problem
Proceedings of the 2011 American Control Conference, 2011Co-Authors: Mathias Bürger, Giuseppe Notarstefano, Frank Allgöwer, Francesco BulloAbstract: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.
Francesco Bullo - One of the best experts on this subject based on the ideXlab platform.
-
a distributed Simplex Algorithm for degenerate linear programs and multi agent assignments
Automatica, 2012Co-Authors: Mathias Bürger, Giuseppe Notarstefano, Francesco Bullo, Frank AllgöwerAbstract: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 and the multi-agent assignment problem
Proceedings of the 2011 American Control Conference, 2011Co-Authors: Mathias Bürger, Giuseppe Notarstefano, Frank Allgöwer, Francesco BulloAbstract: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.
Vincent Boyer - One of the best experts on this subject based on the ideXlab platform.
-
HPCC - Multi GPU Implementation of the Simplex Algorithm
2011 IEEE International Conference on High Performance Computing and Communications, 2011Co-Authors: Mohamed Esseghir Lalami, Vincent BoyerAbstract:The Simplex Algorithm is a well known method to solve linear programming (LP) problems. In this paper, we propose an implementation via CUDA of the Simplex method on a multi GPU architecture. Computational tests have been carried out on randomly generated instances for non-sparse LP problems. The tests show a maximum speedup of 24:5 with two Tesla C2050 boards.
-
multi gpu implementation of the Simplex Algorithm
High Performance Computing and Communications, 2011Co-Authors: Mohamed Esseghir Lalami, Didier Elbaz, Vincent BoyerAbstract:The Simplex Algorithm is a well known method to solve linear programming (LP) problems. In this paper, we propose an implementation via CUDA of the Simplex method on a multi GPU architecture. Computational tests have been carried out on randomly generated instances for non-sparse LP problems. The tests show a maximum speedup of 24:5 with two Tesla C2050 boards.
Mathias Bürger - One of the best experts on this subject based on the ideXlab platform.
-
a distributed Simplex Algorithm for degenerate linear programs and multi agent assignments
Automatica, 2012Co-Authors: Mathias Bürger, Giuseppe Notarstefano, Francesco Bullo, Frank AllgöwerAbstract: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 and the multi-agent assignment problem
Proceedings of the 2011 American Control Conference, 2011Co-Authors: Mathias Bürger, Giuseppe Notarstefano, Frank Allgöwer, Francesco BulloAbstract: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.
James B. Orlin - One of the best experts on this subject based on the ideXlab platform.
-
A network Simplex Algorithm with O(n) consecutive degenerate pivots
Operations Research Letters, 2002Co-Authors: Ravindra K. Ahuja, James B. Orlin, Prabha Sharma, P. T. SokkalingamAbstract:In this paper, we suggest a new pivot rule for the primal Simplex Algorithm for the minimum cost flow problem, known as the network Simplex Algorithm. Due to degeneracy, cycling may occur in the network Simplex Algorithm. The cycling can be prevented by maintaining strongly feasible bases proposed by Cunningham (Math. Programming 11 (1976) 105; Math. Oper. Res. 4 (1979) 196); however, if we do not impose any restrictions on the entering variables, the Algorithm can still perform an exponentially long sequence of degenerate pivots. This phenomenon is known as stalling. Researchers have suggested several pivot rules with the following bounds on the number of consecutive degenerate pivots: m,n^2,k(k+1)/2, where n is the number of nodes in the network, m is the number of arcs in the network, and k is the number of degenerate arcs in the basis. (Observe that k=
-
a polynomial time primal network Simplex Algorithm for minimum cost flows
Symposium on Discrete Algorithms, 1996Co-Authors: James B. OrlinAbstract:Developing a polynomial time primal network Simplex Algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such Algorithm that runs in O(min(n 2m lognC, n 2m2 logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network Simplex Algorithm called the “premultiplier Algorithm”. We then develop a cost-scaling version of the premultiplier Algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm 2 logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).
-
The Scaling Network Simplex Algorithm
Operations Research, 1992Co-Authors: Ravindra K. Ahuja, James B. OrlinAbstract:In this paper, we present a new primal Simplex pivot rule and analyze the worst case complexity of the resulting Simplex Algorithm for the minimum cost flow, the assignment, and the shortest path problems. We consider networks with n nodes, m arcs, integral arc capacities bounded by an integer number U, and integral arc costs whose magnitudes are bounded by an integer number C. Our pivot rule may be regarded as a scaling version of Dantzig's pivot rule. Our pivot rule defines a threshold value Δ, which is initially at most 2C, and the rule permits any arc with a violation of at least Δ/2 to be the editing variable. We select the leaving arc so that strong feasibility of the basis is maintained. When there is no arc satisfying this rule, then we replace Δ by Δ/2 and repeat the process. The Algorithm terminates when Δ < 1. We show that the Simplex Algorithm using this rule performs O(nmU log C) pivots and can be implemented to run in O(m2U log C) time. Specializing these results for the assignment and short...
