4
$\begingroup$

I would like to solve the following type of LP problems:

enter image description here

where M and N are very large numbers, they are on the order of a few hundreds of thousands and tens of thousands, respectively.

As is clear from the above formulation, each constraint links only a few variables, leading to an extremely sparse coefficient matrix.

Which methods and (free) libraries do you suggest for solving this issue very effectively (within a few minutes)? Is there one which can start from a known feasible solution provided by the user?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

One of the best-performing free LP solvers exploiting sparsity is HiGHS (https://github.com/ERGO-Code/HiGHS). It allows passing a starting point.

For comparing relative performance of a number of LP solvers on a standardized test set, take a look at the Mittelmann benchmarks (https://plato.asu.edu/ftp/lpopt.html)

Improve this answer
$\endgroup$
5
$\begingroup$

Based on the Mittelmann benchmarks, I would agree that HiGHS is a contender, as is Clp (which is faster than HiGHS on some test problems, slower on others). You might also want to look at SCIP, which is highly regarded as a mixed integer program solver but will certainly solve LPs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.