4
$\begingroup$

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!

  • 0
    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 cplex2017-10-04

0 Answers 0