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 programs 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!

  • 4
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 19 '11 at 14:37
  • $\begingroup$ This should maximize laziness. $\endgroup$ – Amir Ali Ahmadi Sep 14 '13 at 19:15
  • $\begingroup$ @AmirAliAhmadi Page not found $\endgroup$ – BCLC May 6 '16 at 16:09
  • $\begingroup$ CVXGEN $\endgroup$ – Rodrigo de Azevedo Feb 2 '17 at 12:52
  • $\begingroup$ How long does a commercial solver take to solve the problem? Deciding what approximation is required is easier to know once we know that as a benchmark. Usually feasibility is returned pretty quickly by commerical solvers. You can apply settings such as - "solve for x seconds, then return best available solution", in most solvers such as gurobi and cplex $\endgroup$ – skr Oct 4 '17 at 1:28

Your Answer

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

Browse other questions tagged or ask your own question.