I have a program where I need to solve a linear programming problem in a fast loop. The language I'm using is Java and any kind of bindings to other languages are not acceptable. Libraries might be acceptable, given permissive license, but I generally prefer own code to libraries.
The problem is very simple. It has five variables, six inequalities of the type
expression >= 0 and all of the five variables obviously need to be non-negative too.
Specifically, the problem is to minimize
a + b - c*A - B >= 0 C - c >= 0 D + d - c*E - b >= 0 a + b + c - F >= 0 e - a*G >= 0 e - d*H >= 0 a >= 0 b >= 0 c >= 0 d >= 0 e >= 0
e are variables and
H are constants. Some of the constants (
F) change rapidly and some (
H) stay constant for the duration of the application execution.
The problem is that I have to find an optimal solution preferably over 10 million times per second in a single modern CPU core (yes, I'm using multiple cores, each of them solving the same linear programming problem repeatedly; the aggregate throughput needs to be in excess of 100 million solutions per second).
What would be the fastest approach for solving such a small linear programming problem? I see that there are quite many algorithms capable of solving even complex problems, but are they beneficial for such simple problems?
I see that there are 462 ways to pick 5 equations out of 11, so the approach of solving a different linear system of equations and checking whether the non-picked conditions hold, would not be fastest, right?