Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
@AmirAliAhmadi Page not found – BCLC May 6 at 16:09

Your Answer


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

Browse other questions tagged or ask your own question.