LP, QP & MIP on the JVM

If you need to solve mathematical optimisation LP, QP or MIP models without calling native code – running only pure Java code – there are very few options. In fact, ojAlgo is the only alternative that handles both LP and QP models as well as MIP versions of those.

Commercial solvers like CPLEX, GUROBI, MOSEK and others are very capable. ojAlgo is nowhere near having the same capabilities, but there is a huge set of optimisation problems that do not require these top-notch solvers. This is where ojAlgo is an alternative, and choosing ojAlgo has its benefits:

  • Pure Java – no need to handle any kind of native code. Provided that you code in Java, or some other language that runs on the JVM, this is highly desirable.
  • Open Source with a permissive license – that means no cost, no license management, no restrictions on usage.
  • Available at Maven Central – just declare the dependency using your favourite dependency management tool, and you’re good to go.
  • No transitive dependencies – ojAlgo itself has no dependencies (truly and absolutely zero)!
  • ojAlgo separates between model and solver (the declaration of the problem and the algorithm that finds the solution) and it’s possible to plug in 3:d party solvers. This means that if it in fact turns out you do need a solver like CPLEX, GUROBI or MOSEK there is no need to change any code. Just register a different solver. Integrations for the top commercial solvers already exist – just plug it in. This, naturally, also lets you switch between different 3:d party solvers without effort.
  • If you need help with anything related to ojAlgo, maths, optimisation or Java development Optimatika offers support.

What Can You Expect From ojAlgo?

LP

In a recent benchmark (conducted by us) it was shown that ojAlgo is the fastest pure Java LP solver available and that it is comparable to CPLEX for small models (no more than 1k variables or constraints).

Pure Java LP Solver Benchmark

The chart below originates from that benchmark. It shows execution times for Apache Commons Math (ACM) and ojAlgo relative to CPLEX. Read the original benchmark for details and explanations.

ojAlgo & ACM compared to CPLEX

From that chart it can also be extrapolated that as the model size grows beyond 1k (variables or constraints) the capabilities of a solver like CPLEX start to show, and ojAlgo will appear increasingly slow. We don’t have hard facts, but based on experience estimate that at around 10k ojAlgo will become too slow to be useful. That means:

  • < 1k: No problem!
  • 1k < 10k: Should work, but may appear slow.
  • > 10k: Don’t think so…

This is just a very rough indication of what to expect. Actual performance of a particular model depend on many more things than just the size. Then, of corse, you need to weigh in your performance requirements.

QP

Could potentially handle problems of the same size as the LP solver. The main difficulty users encounter is with the mathematical properties of the model. The problems handled by ojAlgo’s QP solver really need to be convex. Most models reported to be problematic have this problem – they’re not convex. There is a correlation between problem size and numerical difficulties. As models grow larger it often becomes difficult to ensure (numerical) convexity.

  • Potentially same size as LP.
  • Need to pay attention to mathematical properties when generating models to make sure they actually meet the solver requirements (convexity)

MIP

Adding integrality constraints on the variables typically makes the problem much harder to solve, but also makes it harder to reason about what size problems a particular solver can handle. Even tiny MIP model can be very very difficult to solve. Then there are also cases where integrality constraints make little difference. The range of possibilities is from “same as LP or QP” to “just can’t do it”.

  • In general, expect to only be able to solve models clearly smaller than corresponding (relaxed) LP or QP models.
  • The difference between ojAlgo and the top commercial solvers is greater for MIP models than for LP models.
  • A MIP solver is a complex piece of software that comes with a variety of configuration options. To get the most from whatever solver you’re using you need to tune those configurations.

To know if ojAlgo can handle your MIP or not you really need to give it a try. There is no other way.

Other Pure Java Alternatives

  • LP: There is the Apache Commons Math SimplexSolver. We’ve benchmarked against it, and believe we proved ojAlgo to be superior.
  • QP: There is a library called JOptimizer. As far as we can tell it is an abandoned project, and when we try to benchmark against it we have problems getting it to function properly. Therefore we conclude this is not really an alternative.
  • MIP: We’re not aware of any other pure Java MIP solvers, but there is a different category of tools that can be used to solve some of the same problems a MIP solver would be used for – constraint programming. This is not our area of expertise. Search for tools like OptaPlanner, Choco-solver, JaCoP or just “constraint programming” to learn more.

For mathematical programming on the JVM ojAlgo is essentially the only alternative. There is no other library that offers an equivalent set of tools.