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.