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:

  1. Pure Java – absolutely no native code dependencies
  2. Available as a dependency artifact (Usable by Maven, Gradle or what ever)
  3. 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

  1. 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.)
  2. 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.
  3. 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.

Leave a Reply