<p>I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches for solving LP problems in a parallel way, but I wonder if there are specific methods which are efficient for such (real-world, by the way) systems.  </p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2013-08-05T07:44:21.297Z
For what it's worth, I would expect that linear programs of that size should be easily solvable using standard (sequential) LP algorithms/implementations.  It's still an interesting question whether there are good ways to take advantage of parallelism, in general.
D.W.
CC BY-SA 3.0
2013-08-05T15:13:04.867Z
In general, linear programming is P-complete, so it's unlikely to have very efficient parallel algorithms.
Sasho Nikolov
CC BY-SA 3.0
2013-08-05T15:31:14.387Z
Like D.W. mentioned, that size LP is easily solved. Even LPs with millions of variables/constraints are routinely solved (usually with sparse constraint matrices). On the practical side, [Benders' decomposition](http://en.wikipedia.org/wiki/Benders%27_decomposition) is used to solve large LPs that have special structure. Many times the subproblems can be solved in parallel.
Austin Buchanan
<linear-programming><convex-optimization><parallel>
Linear programming optimization problems using parallel algorithms
rursw1
# Linear programming optimization problems using parallel algorithms

(Asked by: username_0 on 2013-08-05)

I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches for solving LP problems in a parallel way, but I wonder if there are specific methods which are efficient for such (real-world, by the way) systems.

Thanks in advance.

**Tags:** linear-programming, convex-optimization, parallel

> **Comments:**
> **username_1**: For what it's worth, I would expect that linear programs of that size should be easily solvable using standard (sequential) LP algorithms/implementations.  It's still an interesting question whether there are good ways to take advantage of parallelism, in general.  
> **username_2**: In general, linear programming is P-complete, so it's unlikely to have very efficient parallel algorithms.  
> **username_3**: Like username_1 mentioned, that size LP is easily solved. Even LPs with millions of variables/constraints are routinely solved (usually with sparse constraint matrices). On the practical side, [Benders' decomposition](http://en.wikipedia.org/wiki/Benders%27_decomposition) is used to solve large LPs that have special structure. Many times the subproblems can be solved in parallel.  

---

## 0 answers

