ojAlgo contains pure Java LP, QP and MIP solvers. That’s something very unique. There are very few pure Java alternatives in this area. Most mathematical optimisation solvers are native code. Often there is a Java interface, but that still requires the native code to be available on the machine that runs the code. All the best solvers are commercial software with strict license key management, Regardless of what you think of the price, it is a complication to install the native code and manage the license. If an Open Source pure Java solver, accessible by simply specifying the Maven coordinates, can handle your problem it would be much preferred. So what’s available?

To be considered for this benchmark:

- Pure Java – absolutely no native code dependencies
- Available as a dependency artifact (Usable by Maven, Gradle or what ever)
- Open Source with a reasonably permissive license

## Apache Commons Math vs ojAlgo

For linear programming Apache Commons Math (ACM) contains an LP solver. That, and the ojAlgo solver, are essentially the only alternatives. (There are some further alternatives mentioned at the end of this post.) This benchmark compares them to each other, and to the industry standard (native code) CPLEX solver.

## netlib/lp

The Netlib collection of LP models is a commonly used set of test models. It’s been around for a long time. As a reference solver we use the community edition of CPLEX which is limited to 1000 variables/constraints. With that model size constraint there are 45 models in the Netlib collection. All those models are included in this benchmark. No model has been removed for any other reason.

The actual models files used here are downloaded from the CUTEr web site.

## Methodology

Each model-solver combination is evaluated multiple times – repeated until consecutive invocation times are stable within 1%. When that happens the fastest time recorded, overall, is picked and used to compare with the other solver’s results.

If a solver fails to find a correct solution for a particular model, no time is recorded. That model-solver pair is instead just marked as FAILED.

Usually JMH is used for all benchmarking, but not this time. That’s because sometimes a solver would not finish at all – it would timeout or hang. Couldn’t figure out how to deal with that using JMH.

ojAlgo contains a modelling tool (class) named ExpressionsBasedModel. In all cases the solvers are invoked via that model. The ExpressionsBasedModel is independent of any/all solvers. That includes the ojAlgo solvers. Even within ojAlgo the model implementation and the various solver implementations are independent of each other. They are linked via “integrations”. Each solver that should be able to be invoked from an ExpressionsBasedModel needs to register a solver integration. Regardless of which solver is tested the model files are parsed constructing an ExpressionsBasedModel. ExpressionsBasedModel then has presolve functionality which is executed regardless of which solver is later invoked. The time measured/compared corresponds only to the integration and solver specific code.

The ACM and CPLEX solver integrations are written by the ojAlgo developer. Writing an integration is straight forward – not complicated code. If you want the details, check out the code:

### Versions used

- ojAlgo: 49.2.1
- ojAlgo-commons-math3: 3.1.0 (Commons Math: 3.6.1)
- ojAlgo.cplex: 3.0.1 (IBM ILOG CPLEX Optimization Studio v12.8.0)

## Benchmark Results

```
Model Name Solver Name Result State Time
==================================================================================
ADLITTLE ACM OPTIMAL 22.426024ms
ADLITTLE CPLEX OPTIMAL 2.113305ms
ADLITTLE ojAlgo OPTIMAL 1.915458ms
AFIRO ACM OPTIMAL 1.391531ms
AFIRO CPLEX OPTIMAL 0.939916ms
AFIRO ojAlgo OPTIMAL 0.270061ms
AGG ACM OPTIMAL 152.590234ms
AGG CPLEX OPTIMAL 5.023971ms
AGG ojAlgo OPTIMAL 20.111355ms
AGG2 ACM OPTIMAL 766.970903ms
AGG2 CPLEX OPTIMAL 5.877653ms
AGG2 ojAlgo OPTIMAL 129.460341ms
AGG3 ACM OPTIMAL 819.196383ms
AGG3 CPLEX OPTIMAL 6.562171ms
AGG3 ojAlgo OPTIMAL 121.725585ms
BANDM ACM FAILED TIMEOUT
BANDM CPLEX OPTIMAL 9.603582ms
BANDM ojAlgo OPTIMAL 81.503454ms
BEACONFD ACM OPTIMAL 181.233339ms
BEACONFD CPLEX OPTIMAL 3.551974ms
BEACONFD ojAlgo OPTIMAL 2.928371ms
BLEND ACM OPTIMAL 21.918102ms
BLEND CPLEX OPTIMAL 1.885936ms
BLEND ojAlgo OPTIMAL 1.620513ms
BOEING1 ACM FAILED TIMEOUT
BOEING1 CPLEX OPTIMAL 11.803661ms
BOEING1 ojAlgo OPTIMAL 397.175871ms
BOEING2 ACM FAILED WRONG
BOEING2 CPLEX OPTIMAL 2.884595ms
BOEING2 ojAlgo OPTIMAL 22.24863ms
BORE3D ACM FAILED TIMEOUT
BORE3D CPLEX OPTIMAL 3.06909ms
BORE3D ojAlgo OPTIMAL 4.967841ms
BRANDY ACM FAILED TIMEOUT
BRANDY CPLEX OPTIMAL 5.379036ms
BRANDY ojAlgo OPTIMAL 15.948558ms
CAPRI ACM FAILED WRONG
CAPRI CPLEX OPTIMAL 5.061319ms
CAPRI ojAlgo OPTIMAL 131.900266ms
DEGEN2 ACM FAILED TIMEOUT
DEGEN2 CPLEX OPTIMAL 14.308872ms
DEGEN2 ojAlgo OPTIMAL 1149.761792ms
E226 ACM FAILED TIMEOUT
E226 CPLEX OPTIMAL 5.750909ms
E226 ojAlgo OPTIMAL 60.99703ms
ETAMACRO ACM FAILED TIMEOUT
ETAMACRO CPLEX OPTIMAL 11.194794ms
ETAMACRO ojAlgo OPTIMAL 179.563236ms
FFFFF800 ACM FAILED TIMEOUT
FFFFF800 CPLEX OPTIMAL 11.796835ms
FFFFF800 ojAlgo OPTIMAL 191.998794ms
FINNIS ACM FAILED TIMEOUT
FINNIS CPLEX OPTIMAL 8.555869ms
FINNIS ojAlgo OPTIMAL 1008.726483ms
FORPLAN ACM FAILED WRONG
FORPLAN CPLEX OPTIMAL 6.773515ms
FORPLAN ojAlgo OPTIMAL 21.917906ms
GROW15 ACM FAILED TIMEOUT
GROW15 CPLEX OPTIMAL 32.647047ms
GROW15 ojAlgo OPTIMAL 144.403432ms
GROW22 ACM FAILED TIMEOUT
GROW22 CPLEX OPTIMAL 102.329952ms
GROW22 ojAlgo OPTIMAL 648.230608ms
GROW7 ACM FAILED TIMEOUT
GROW7 CPLEX OPTIMAL 8.268607ms
GROW7 ojAlgo OPTIMAL 14.790675ms
ISRAEL ACM OPTIMAL 90.318246ms
ISRAEL CPLEX OPTIMAL 3.297254ms
ISRAEL ojAlgo OPTIMAL 43.415429ms
KB2 ACM OPTIMAL 7.02671ms
KB2 CPLEX OPTIMAL 0.925989ms
KB2 ojAlgo OPTIMAL 1.271386ms
LOTFI ACM OPTIMAL 501.538426ms
LOTFI CPLEX OPTIMAL 3.031368ms
LOTFI ojAlgo OPTIMAL 6.917218ms
PILOT4 ACM FAILED TIMEOUT
PILOT4 CPLEX OPTIMAL 24.621775ms
PILOT4 ojAlgo OPTIMAL 1950.835936ms
RECIPELP ACM OPTIMAL 85.041284ms
RECIPELP CPLEX OPTIMAL 1.655691ms
RECIPELP ojAlgo OPTIMAL 1.002435ms
SC105 ACM OPTIMAL 27.933561ms
SC105 CPLEX OPTIMAL 1.460601ms
SC105 ojAlgo OPTIMAL 1.556106ms
SC205 ACM OPTIMAL 175.705924ms
SC205 CPLEX OPTIMAL 3.183428ms
SC205 ojAlgo OPTIMAL 11.046528ms
SC50A ACM OPTIMAL 4.812759ms
SC50A CPLEX OPTIMAL 1.168827ms
SC50A ojAlgo OPTIMAL 0.287116ms
SC50B ACM OPTIMAL 4.162332ms
SC50B CPLEX OPTIMAL 1.282519ms
SC50B ojAlgo OPTIMAL 0.332079ms
SCAGR25 ACM FAILED TIMEOUT
SCAGR25 CPLEX OPTIMAL 8.857776ms
SCAGR25 ojAlgo OPTIMAL 253.828789ms
SCAGR7 ACM FAILED WRONG
SCAGR7 CPLEX OPTIMAL 2.690116ms
SCAGR7 ojAlgo OPTIMAL 4.946822ms
SCFXM1 ACM FAILED WRONG
SCFXM1 CPLEX OPTIMAL 7.796758ms
SCFXM1 ojAlgo OPTIMAL 30.668442ms
SCFXM2 ACM FAILED TIMEOUT
SCFXM2 CPLEX OPTIMAL 14.577211ms
SCFXM2 ojAlgo OPTIMAL 319.671044ms
SCORPION ACM OPTIMAL 951.903684ms
SCORPION CPLEX OPTIMAL 4.072282ms
SCORPION ojAlgo OPTIMAL 19.000254ms
SCSD1 ACM FAILED TIMEOUT
SCSD1 CPLEX OPTIMAL 3.688359ms
SCSD1 ojAlgo OPTIMAL 8.681358ms
SCTAP1 ACM FAILED TIMEOUT
SCTAP1 CPLEX OPTIMAL 4.318584ms
SCTAP1 ojAlgo OPTIMAL 27.225691ms
SEBA ACM FAILED TIMEOUT
SEBA CPLEX OPTIMAL 5.686363ms
SEBA ojAlgo OPTIMAL 2148.491912ms
SHARE1B ACM OPTIMAL 325.097456ms
SHARE1B CPLEX OPTIMAL 3.129655ms
SHARE1B ojAlgo OPTIMAL 12.54679ms
SHARE2B ACM OPTIMAL 27.81404ms
SHARE2B CPLEX OPTIMAL 1.9142ms
SHARE2B ojAlgo OPTIMAL 2.090121ms
STAIR ACM FAILED WRONG
STAIR CPLEX OPTIMAL 10.844157ms
STAIR ojAlgo OPTIMAL 100.143446ms
STOCFOR1 ACM OPTIMAL 32.948899ms
STOCFOR1 CPLEX OPTIMAL 2.125558ms
STOCFOR1 ojAlgo OPTIMAL 1.801554ms
TUFF ACM FAILED TIMEOUT
TUFF CPLEX OPTIMAL 6.93337ms
TUFF ojAlgo FAILED TIMEOUT
VTP-BASE ACM FAILED WRONG
VTP-BASE CPLEX OPTIMAL 1.967ms
VTP-BASE ojAlgo OPTIMAL 2.781205ms
```

## Results Interpretation

CPLEX, of course, solves all these models without any problems – fast and reliable. It can easily solve models much larger than these. It should be pointed out that CPLEX is not just any native code solver. It’s a top notch commercial solver that has been the industry leader for decades.

For a few of the smallest/simplest models ojAlgo is actually faster than CPLEX (most likely related to overhead calling native code) but as size/complexity scales up CPLEX is clearly much faster. Also, ojAlgo fails to solve one of the models. (A model named TUFF – means though/difficult in Swedish – where ojAlgo cycles and never even finds a feasible solution.)

Apache Commons Math (ACM) fails to solve more than half of the models. The failures include returning the wrong solution (not the same as CPLEX) never returning a solution at all (hanging) or returning different results with subsequent executions. In the cases where it does return a correct solution it is typically an order of magnitude slower than ojAlgo. Being slower is not good. Failing to solve that many models is bad. Not being able to trust the results must be unacceptable!

The chart above shows ojAlgo and ACM execution times as functions of CPLEX execution time. (x-y scatter plot where the x-values are always CPLEX’s execution time for a particular model, and the y-values are ojAlgo’s or ACM’s execution times for the same model.) As can be seen in the chart there are fewer points for ACM than for ojAlgo. That’s because ACM failed to solve several models. Further it can be seen that the ACM dots are typically positioned higher than the corresponding ojAlgo dots. That’s because ACM took longer to solve the models. Also, note that towards the right hand side of the chart (models that took CPLEX a little longer) there are no dots for ACM. That’s because ACM failed to solve all of those models. The dashed line represents y == x which is just CPLEX. This should give an idea about how much slower ojAlgo and ACM are compared to CPLEX as well as how they scale with increasing size and numerical difficulty.

## Other Alternatives

- The JOptimizer library contains a selection of solvers for convex problems (incl. LP). The project’s web site has disappeared, and with that all documentation. Integrating with ojAlgo has not been very successful. Originally it was planned to be part of this benchmark, but it simply didn’t work well enough. (Think maybe the various convex solvers work better than the LP stuff.)
- Recently discovered SSC – it’s a pure Java simplex solver. Just browsing the code it looks very promising! This is however not (yet) released as a dependency artifact (nor is the source code available at GitHub or similar) and that disqualifies it from being included here.
- Other than that the alternative is to use native code. There are several native code (both Open Source and commercial) solver packages available with Java interfaces.