1
$\begingroup$

I need to get feeling for the feasible size of a LPP, that can be solved on a PC. Say, its a good one (8 cores @ 3+GHz, 64GB RAM). We also assume that number of variables is close to the number of additional conditions.

I know it depends on the solver, but what size is feasible for solution in several hours/few days? 1000 of variables? A million? Order of magnitude would be enough.

Update. Let's consider a general form: matrix is not sparce/diagonal/blotchy or whatever. Let's say matrix's rows are filled with many hundreds of values (@ thousands of variables).

$\endgroup$
1
$\begingroup$

There is no simple answer. The running time depends not only on the number of variables, but also on the "difficulty" of the system of inequalities. The best you can do is to try to benchmark on representative problem instances.

$\endgroup$
2
$\begingroup$

I would assume a few times n^3 operations for n variables. How many operations per second can you perform? Using vector operations is not too difficult. Using 8 cores for one problem is hard. Depending on your programming effort you will be able to do between 1 and 100 billion operations per second, or 100 to 10,000 trillion operations per day, or very roughly n = 20,000 to 100,000. Buy a lot of RAM as well.

$\endgroup$
2
$\begingroup$

For continuous LP, problems with millions of nonzeros are solved routinely. I'd expect problems with 10 millions nonzeros to be solvable, barring numerical issues. You can find some benchmarks here, but they do not include the best commercial solvers, which I remember solve all problems.

This is my guess from experience, and I think common knowledge in the field, but can vary a lot:

  • This could be a lot more for particular problem structures that you can exploit with a specialized algorithm
  • Some kinds of problems may of course be harder to solve
  • Solvers improve. Maybe my knowledge is already outdated and it's closer to 100 millions :D

The example you cite (a dense matrix) is very uncommon in practice, for example. This is why I use the number of nonzeros as a metric rather than the number of rows/columns.

$\endgroup$

Your Answer

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

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