What is the fastest way to solve small linear programs inside a loop?

Hi,

I'm running linprog inside a large time loop to solve small (m,n <=3) linear programs but it is my code's bottle neck. I found that using Simplex ("Large scale off) instead of interior point in the options makes it a little faster. Is there a faster way to do this? matrix "A" is always small and dense (m,n<=3). I tried TOMLAB's MINOS and LPOPT and QPOPT but still linprog is faster. I don't know maybe i'm not using TOMLAB correctly or that they're just better for large problem sizes.

Is there an easy way to just code a faster LP solver for small problems. For my current problem linprog is taking ~.0012 sec for a single iteration to solve 2*2 problems. I have it inside a nested loop, below is a pseudo code:

 for t =1:nt
   for n = 1:N
         linprog
   end
 end

So it would be much better to have it to be as fast as say ~0.0005 sec/iteration. I want to do this before attempting to make the inner loop parallel. The outer loop cannot be made parallel because of dependencies (time loop).

I would highly appreciate any help guys because my simulations need to be faster than real-time.

Thanks,

Eyas

[Li Wang]

Hi Eyas,

Any updates on this problem. I am also facing the same problem. My LP is very small (6 decision variables, 6 eqn constraints, 6 ineqn constraints), but has to be solved more than 10K+ times.

I am thinking about 1) giving the LP x0 from previous problem (Aeq, Aeqn are the same, beq and b changes a little), so that it can be solved recursively 2) reduce solution tolerance (I only need +/-1 precision) 3) try other efficient small LP solver. But no good result yet.

Would you mind sharing any progress on this problem,

Best,

Li

[Alec]

It seems like linprog has a non-trivial amount of problem setup/verification/teardown. On my machine about ≥0.001 secs. It might be better to wrap up a C++ solver that will directly solve the small problems rather than do a lot of preamble.

Answer 1

[Matt J]

You could try concatenating the separate linear programs into a single large one. E.g., concatenate the objective function vectors f_i into one big f vector.