Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 variables and ~18-100 inequalities. The system is real-time, so I have ~100 microseconds to compute the solution. The good thing is that exact solution is not always required, and if computation takes too long, feasible point very close to an optimal one would work too. The bad thing is that very rarely problem is infeasible and I need to detect that in a realistic time. Given these requirements, could you please suggest what category of algorithms should I look at: interior-point or simplex? The ease of implementation is also an advantage.

Thanks!

share|improve this question
3  
I believe that for small programs like yours, there's no reason to bother with interior-point algorithms, though they do mesh with your "approximate solution" laxity. Simplex is also easier to program. But beware that if you try to program it yourself, the result is going to be numerically unstable. So instead follow some standard implementation, like the one in Numerical Recipes. –  Yuval Filmus May 19 '11 at 14:37
    
This should maximize laziness. –  Amir Ali Ahmadi Sep 14 '13 at 19:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.