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.
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.
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:
- 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)
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
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.
- 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.