3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Aug 5, 2013 at 7:44
  • 6
    $\begingroup$ In general, linear programming is P-complete, so it's unlikely to have very efficient parallel algorithms. $\endgroup$
    – Sasho Nikolov
    Aug 5, 2013 at 15:13
  • 5
    $\begingroup$ 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 is used to solve large LPs that have special structure. Many times the subproblems can be solved in parallel. $\endgroup$
    – Austin Buchanan
    Aug 5, 2013 at 15:31

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy