1
$\begingroup$

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 e, given:

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

where a, b, c, d and e are variables and A ... H are constants. Some of the constants (A, B, C, D, and F) change rapidly and some (E, G and 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?

$\endgroup$
  • $\begingroup$ At 4 GigaHertz and a generous 4 instructions per cycle, you get 16 billion instructions per second per core. Divide that by 10 million problems per second, and you're left with 1600 instructions per problem. That's extremely tight. Can you spread the solves out over many more cores? $\endgroup$ – Brian Borchers Apr 8 at 23:27
  • $\begingroup$ Strangely enough, my initial attempt by solving the problem by considering points where the solution is most likely to be, is over 10x faster than an existing Java-based linear programming solver. Not only that, but it gives accurate solutions in all cases I have tested so far! $\endgroup$ – juhist Apr 9 at 16:42
  • $\begingroup$ That's really not surprising since most LP solvers have a lot of overhead that you can avoid in your approach. $\endgroup$ – Brian Borchers Apr 9 at 19:30

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.