Pure Java LP Solver Benchmark
First published in October 2021, then updated in February 2022.
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: 51.0.0 (49.2.1, when first published)
- 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 24.40253ms
ADLITTLE CPLEX OPTIMAL 2.031104ms
ADLITTLE ojAlgo OPTIMAL 1.054404ms
AFIRO ACM OPTIMAL 1.90258ms
AFIRO CPLEX OPTIMAL 0.774987ms
AFIRO ojAlgo OPTIMAL 0.265833ms
AGG ACM OPTIMAL 202.008793ms
AGG CPLEX OPTIMAL 4.644614ms
AGG ojAlgo OPTIMAL 4.314918ms
AGG2 ACM OPTIMAL 1003.03178ms
AGG2 CPLEX OPTIMAL 6.620704ms
AGG2 ojAlgo OPTIMAL 5.598157ms
AGG3 ACM OPTIMAL 1049.772191ms
AGG3 CPLEX OPTIMAL 6.68621ms
AGG3 ojAlgo OPTIMAL 6.683239ms
BANDM ACM FAILED TIMEOUT
BANDM CPLEX OPTIMAL 9.297724ms
BANDM ojAlgo OPTIMAL 18.997663ms
BEACONFD ACM OPTIMAL 226.700469ms
BEACONFD CPLEX OPTIMAL 3.562922ms
BEACONFD ojAlgo OPTIMAL 2.276825ms
BLEND ACM OPTIMAL 23.515548ms
BLEND CPLEX OPTIMAL 1.663466ms
BLEND ojAlgo OPTIMAL 0.950342ms
BOEING1 ACM FAILED TIMEOUT
BOEING1 CPLEX OPTIMAL 11.606891ms
BOEING1 ojAlgo OPTIMAL 86.987504ms
BOEING2 ACM FAILED UNSTABLE
BOEING2 CPLEX OPTIMAL 3.054295ms
BOEING2 ojAlgo OPTIMAL 6.611392ms
BORE3D ACM FAILED TIMEOUT
BORE3D CPLEX OPTIMAL 2.952702ms
BORE3D ojAlgo OPTIMAL 2.375518ms
BRANDY ACM FAILED TIMEOUT
BRANDY CPLEX OPTIMAL 5.69342ms
BRANDY ojAlgo OPTIMAL 4.875528ms
CAPRI ACM FAILED UNSTABLE
CAPRI CPLEX OPTIMAL 5.650528ms
CAPRI ojAlgo OPTIMAL 28.585122ms
DEGEN2 ACM FAILED TIMEOUT
DEGEN2 CPLEX OPTIMAL 14.352009ms
DEGEN2 ojAlgo OPTIMAL 145.216013ms
E226 ACM OPTIMAL 688.73097ms
E226 CPLEX OPTIMAL 7.112912ms
E226 ojAlgo OPTIMAL 11.579217ms
ETAMACRO ACM FAILED TIMEOUT
ETAMACRO CPLEX OPTIMAL 9.666118ms
ETAMACRO ojAlgo OPTIMAL 26.447114ms
FFFFF800 ACM FAILED TIMEOUT
FFFFF800 CPLEX OPTIMAL 10.651637ms
FFFFF800 ojAlgo OPTIMAL 52.345121ms
FINNIS ACM FAILED TIMEOUT
FINNIS CPLEX OPTIMAL 8.399524ms
FINNIS ojAlgo OPTIMAL 190.659009ms
FORPLAN ACM FAILED UNSTABLE
FORPLAN CPLEX OPTIMAL 5.595419ms
FORPLAN ojAlgo OPTIMAL 7.328905ms
GROW15 ACM FAILED TIMEOUT
GROW15 CPLEX OPTIMAL 36.568825ms
GROW15 ojAlgo OPTIMAL 206.485576ms
GROW22 ACM FAILED TIMEOUT
GROW22 CPLEX OPTIMAL 99.33184ms
GROW22 ojAlgo OPTIMAL 1495.329128ms
GROW7 ACM FAILED TIMEOUT
GROW7 CPLEX OPTIMAL 8.778534ms
GROW7 ojAlgo OPTIMAL 11.92479ms
ISRAEL ACM OPTIMAL 149.444501ms
ISRAEL CPLEX OPTIMAL 3.815925ms
ISRAEL ojAlgo OPTIMAL 6.528239ms
KB2 ACM OPTIMAL 6.761116ms
KB2 CPLEX OPTIMAL 1.033355ms
KB2 ojAlgo OPTIMAL 0.543901ms
LOTFI ACM OPTIMAL 599.764915ms
LOTFI CPLEX OPTIMAL 2.859463ms
LOTFI ojAlgo OPTIMAL 1.524653ms
PILOT4 ACM FAILED UNSTABLE
PILOT4 CPLEX OPTIMAL 25.350613ms
PILOT4 ojAlgo OPTIMAL 443.840806ms
RECIPELP ACM OPTIMAL 101.984305ms
RECIPELP CPLEX OPTIMAL 1.763613ms
RECIPELP ojAlgo OPTIMAL 0.822763ms
SC105 ACM OPTIMAL 32.575308ms
SC105 CPLEX OPTIMAL 1.758967ms
SC105 ojAlgo OPTIMAL 0.552629ms
SC205 ACM OPTIMAL 236.686857ms
SC205 CPLEX OPTIMAL 2.698923ms
SC205 ojAlgo OPTIMAL 2.925706ms
SC50A ACM OPTIMAL 5.635887ms
SC50A CPLEX OPTIMAL 1.271988ms
SC50A ojAlgo OPTIMAL 0.28155ms
SC50B ACM OPTIMAL 5.107918ms
SC50B CPLEX OPTIMAL 0.970393ms
SC50B ojAlgo OPTIMAL 0.187952ms
SCAGR25 ACM FAILED UNSTABLE
SCAGR25 CPLEX OPTIMAL 8.306402ms
SCAGR25 ojAlgo OPTIMAL 70.463888ms
SCAGR7 ACM OPTIMAL 135.951426ms
SCAGR7 CPLEX OPTIMAL 2.769207ms
SCAGR7 ojAlgo OPTIMAL 2.072001ms
SCFXM1 ACM FAILED UNSTABLE
SCFXM1 CPLEX OPTIMAL 7.687805ms
SCFXM1 ojAlgo OPTIMAL 9.042746ms
SCFXM2 ACM FAILED TIMEOUT
SCFXM2 CPLEX OPTIMAL 14.680769ms
SCFXM2 ojAlgo OPTIMAL 63.902875ms
SCORPION ACM OPTIMAL 1236.17844ms
SCORPION CPLEX OPTIMAL 4.051542ms
SCORPION ojAlgo OPTIMAL 7.651202ms
SCSD1 ACM FAILED UNSTABLE
SCSD1 CPLEX OPTIMAL 3.65711ms
SCSD1 ojAlgo OPTIMAL 4.699689ms
SCTAP1 ACM FAILED UNSTABLE
SCTAP1 CPLEX OPTIMAL 4.531862ms
SCTAP1 ojAlgo OPTIMAL 10.589084ms
SEBA ACM FAILED TIMEOUT
SEBA CPLEX OPTIMAL 5.573434ms
SEBA ojAlgo OPTIMAL 133.949868ms
SHARE1B ACM OPTIMAL 387.575914ms
SHARE1B CPLEX OPTIMAL 3.196878ms
SHARE1B ojAlgo OPTIMAL 3.344322ms
SHARE2B ACM OPTIMAL 35.89297ms
SHARE2B CPLEX OPTIMAL 1.99975ms
SHARE2B ojAlgo OPTIMAL 1.065237ms
STAIR ACM FAILED UNSTABLE
STAIR CPLEX OPTIMAL 10.086863ms
STAIR ojAlgo OPTIMAL 26.062774ms
STOCFOR1 ACM OPTIMAL 43.634004ms
STOCFOR1 CPLEX OPTIMAL 2.047131ms
STOCFOR1 ojAlgo OPTIMAL 0.959562ms
TUFF ACM FAILED TIMEOUT
TUFF CPLEX OPTIMAL 6.589792ms
TUFF ojAlgo FAILED TIMEOUT
VTP-BASE ACM FAILED UNSTABLE
VTP-BASE CPLEX OPTIMAL 2.149045ms
VTP-BASE ojAlgo OPTIMAL 1.876053ms
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 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 more than 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.
What Changed Between The Original Post And The Update?
- ojAlgo was updated from v49.2.1 to v51.0.0 which is faster – the gap between ojAlgo and ACM increased.
- The benchmark requirements on “success” was relaxed a bit resulting in ACM passing 1 additional case – it still fails more than half the cases.
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.
- ← Previous
Common Mistake - Next →
JDK17 Benchmark