"Benchmarks" on small models

[infinity77]

Dear HiGHS Community,

I am not entirely sure this belongs to the Q&A section, but I have been doing quite a lot (too many...) benchmarks on the models I have, comparing HiGHS with GLPK.

Preamble

Please do not take any of this as a criticism, HiGHS is a phenomenal solver: it may well be that my problems are too small, and I understand that HiGHS may be geared to shine when confronted with (much) larger LPs.

I have done this to learn, and better understand if HiGHS could be a better candidate as a solver than others I was testing. In addition, there might be options/settings that I could use to make HiGHS faster, and maybe in my ignorance I am just not aware of them: any suggestion would be welcome.

Setup

I am using both HiGHS and GLPK via the C API, not the executable. These are the only settings I have changed:

For GLPK:

presolve = 1
method = GLP_DUALP
tol_bnd = 1e-6
tol_dj = 1e-6

For HiGHS:

kkt_tolerance = 1e-6
allow_unbounded_or_infeasible = 1
user_bound_scale = -10

Both GLPK and HiGHS are compiled with Visual Studio 2022 Professional (both compiled to the metal), on Windows 10 64 bit (Intel Core i7-13850HX, 32 GB RAM).

The only things I am timing is the actual solving of the LP, everything else (problem setup, collecting results, etc...) is irrelevant as they are much faster than everything else. So, I am timing the following:

For GLPK:

int glp_simplex(glp_prob *P, const glp_smcp *parm);

For HiGHS:

HighsInt Highs_run(void* highs)

Timing results are the mean of 50 iterations, with 4 preliminary "warmup" iterations for the machine to get into the proper state.

The model is reconstructed from scratch at each iteration (but the reconstruction and setup time are not measured), to avoid both GLPK and HiGHS warm-starting from a known solution.

Results

I understand my models are quite small, although some of them get up to matrices having 6,000 x 7,000 sizes - albeit with very few nonzeros.

The following scatter plot shows HiGHS vs. GLPK on all 67 snapshots of different models I have, measuring solve time for both solvers. Please note that both X and Y scales are logarithmic. The units of measurement is milliseconds.

To be clear: If a point is below the diagonal, this means that GLPK was faster than HiGHS. If it's above the diagonal, it means HiGHS was faster than GLPK:

After that, I have extracted the LPs for which either HiGHS or GLPK took more than 1 ms to solve (ther are 16 of them) - as some of my models are very small and differences of a few microseconds are irrelevant.

The graph below is a column chart with timings for both GLPK and HiGHS (time on the left Y axis), with the ratio HiGHS / GLPK as a black line on the right Y axis. For each LP, its characteristics (number of rows, number of columns, number of nonzeros and their percentage) is reported as a X axis label:

Elapsed (solve) time is reported inside the bar for each solver, and the ratio HiGHS/GLPK is also in a text box above the black line. Please note that the left Y scale is logarithmic

As you can see, for most models GLPK is on average at least twice as fast. For only 3 LPs HiGHS was a bit faster (around 20%, highlighted in red boxes/red texts). I have many more LPs (up to matrices of 10,000 x 10,000) for which the results seem consistent - i.e., GLPK generally faster.

Conclusion

It's highly likely that chasing milliseconds is not going to take me anywhere. It's also likely that there is nothing more I can do with/to HiGHS to make the benchmarks look different. But if anyone has any suggestion on what I could tweak to gain more performance from HiGHS on small models I would be very happy to test.

Please do not take any of this as a criticism - I have spent more time than I planned on this but it was very enjoyable to work with HiGHS' code: if the answer is "HiGHS is coded to perform well on large LPs/MILPs and not geared towards small LPs", then that's also OK.

If need be, I can share any (or all) of my 67 benchmarks LPs.

Any comment is most welcome. Thank you.

[jajhall]

Yes, HiGHS is designed for large, hard LPs and MIPs, and there may be overheads that make it slower than GLPK on small instances like these. We've certainly seen lesser solvers out-perform it on small MIPs.

I'd be curious to have these 16 instances to see what their nature is. I also have to ask whether they are random in any way.

[odow]

Something similar is observed here: https://discourse.julialang.org/t/an-idea-to-explain-a-drastic-difference-in-computation-times-for-optimizing-a-jump-model-and-the-unexpected-ranking-of-solvers-used/131253

Even Gurobi is was much slower than GLPK. Sometimes it is the right tool for the job.

[infinity77]

Yes, HiGHS is designed for large, hard LPs and MIPs, and there may be overheads that make it slower than GLPK on small instances like these. We've certainly seen lesser solvers out-perform it on small MIPs.

I'd be curious to have these 16 instances to see what their nature is. I also have to ask whether they are random in any way.

Models are not random in any way. They are generated from a custom network flow problem.

I am attaching the models (in LP format as exported by GLPK) to this message. If MPS format is preferred, please do let me know, I'll try and export them from HiGHS.

HiGHS_Benchmarks.zip

ADDED

In MPS format as exported by HiGHS as well.

HiGHS_Benchmarks_MPS.zip

[jajhall]

Models are not random in any way. They are generated from a custom network flow problem.

I guessed so, but wanted to eliminate this reason for relatively poor performance of HiGHS

[jajhall]

HiGHS is running presolve for all these LPs, and it's faster with presolve than without.

About half the time (39-63%) is spent performing presolve

Relatively little time (5-30%) is spent solving the presolved LP

However, after postsolve, it's having to run a few simplex iterations to clean up small primal and dual infeasibilities. More time (17-36%) is spent doing this than solving the presolved LP

I doubt whether GLPK's presolve will be reducing the LP as much (so spending less time) but enough to make the main solve significantly cheaper. Then, after postsolve, maybe there are no small primal and dual infeasibilities to clean up (due to GLPK having fewer presolve rules) so that time is not required.

I can't put more time into this now, but it's interesting, as we know there are users who want to solve vast numbers of very easy LPs/MIPs, and someday we should see whether we can improve performance by skipping some of the more sophisticated tricks that are a bad "investment" for small problems.

Note that there are no changes to option settings that I see enhancing performance

[infinity77]

Thank you @odow and @jajhall for your answers.

I perfectly understand that your resources and expertise should be spent on more worthy problems - such as improving performances on large LPs/MIPs. Please keep up the good work.

I look forward to a future in which small problems can use the tricks you mentioned, to have faster runtimes.