METIS discussion

[odow]

This is an issue for @filikat and @galabovaa.

At JuMP-dev '25, @amontoison and I were discussing HiGHS, METIS, compilation, and distribution.

Our conclusion is that the easiest path forward is for HiGHS to vendor the source code of GKLib and METIS into ERGO-Code/HiGHS (or ERGO-Code/METIS).

This would let you choose the version of METIS to use, you could delete much of the code that is unused, and you could carry the various patches that you need.

To avoid conflicts with other libraries that use METIS, you should:

• rename the so name from libmetis to libmetishighs
• add a prefix (like highs_) to all symbols so that there are no conflicts between the symbols of libmetishighs and libmetis.

The main reasons for vendoring METIS are:

• There are breaking changes in minor releases of METIS. 5.10 and 5.20 are not compatible due to changes in the C API
• We're likely NOT going to update METIS_jll in Julia from @amontoison's fork of 5.10 to a newer version
• Vendoring would make it muuuuuch easier to compile and distribute because everyone would be building from source with the same version. The only dependency would then by a BLAS, which are much more standardised and easier to distribute on different platforms.

The main reason against vendoring METIS is the license. The resulting binaries would be Apache instead of MIT, but building without HiPO would still let you have a MIT licensed binary.

[filikat]

I agree that It's probably the best way forward.

A few things to mention:

• I actually noticed that version 5.2.1, although a bit slower, computes a better ordering. There is only a marginal difference on the Mittelmann benchmark, but it makes a huge difference on the PyPSA models. So, we decided that it is better if we use the latest version, with all the patches and fixes required.
• I already made some changes to Metis to make it thread-safe, and this is available in Ivet's fork, which is what is recommended in the HiGHS installation instructions. Using a non-thread-safe version may create problems if we decide to reorder multiple matrices concurrently, or if users create multiple instances of HiPO within a single process.
• Ivet and I already talked about including Metis into HiGHS. I already prepared a minimal version of Metis 5.1.0 which includes only the code that we actually need. The source code of GKlib+Metis goes from 1.3MB to 270KB (for comparison, the current HiGHS source is 6.5MB). I can easily do the same for 5.2.1 at any moment.
• I agree that having to install and link Metis to HiGHS is creating some issues to people who want to use HiPO. Having it as part of our source code would much simplify the process. It would also guarantee that Metis is compiled with the same integer type as HiGHS.
• We could still have an option to provide an external Metis library, in case the user really wants to use their own, or for us to test potential newer Metis versions in the future.

[amontoison]

@filikat With Nick Gould, we interfaced METIS 4, METIS 5.1.0, and METIS 5.2.1 in GALAHAD. All versions are available.
You may get different results, and some versions perform better than others depending on the problems, but the behavior also strongly depends on the options you pass to METIS. If you use the vanilla options with 5.1.0, it may be worth tuning them before upgrading to a newer release.

cc @nimgould

[filikat]

@amontoison I did play a bit with the options, especially no2hop and pfactor. They do make a big difference sometimes.

The problem is that whatever Metis options we set as default in HiGHS, they need to work for generic problems.
I did some tests and it seems that changing the Metis options works for some problems but not for others. We need the default behaviour of HiGHS to be good for as many problems as possible, so I'm a bit wary of using non-default options in Metis as a default in HiGHS.

The default Metis 5.2.1 seems to produce slightly better orderings than the default 5.1.0; for the PyPSA problems it performs enormously better.
As you said each problem will behave differently. We can surely have HiGHS options available to the user to set Metis options, but most people will use HiGHS with default options. Changing Metis options in HiGHS would be quite an advanced feature that most people don't even know about.

[nimgould]

Just an observation from GALAHAD land. As Alexis mentioned, we have a Metis module, actually an extraction of the Metis nodend parts as those are all we need, that provides native access to Metis 5.1/5.2, but also optional hooks into the license-restricted Metis 4.0 (with instructions of how to find and link the latter). The reason for this is that we have often observed, both in GALAHAD and HSL, Metis 4.0 finds much better orderings, and is faster in doing so. We also support both 32 and 64 bit integers at the same time, for what it is worth. I should also add that nested dissection (and that is what Metis does) can be very bad for matrices with (permuted) band structure, and for these band-width reduction and the like are preferred.

Good luck with HiGHS, I look forward very much to seeing your fully-developed QP solvers ... and a healthy comparison with those in GALAHAD!

[filikat]

Thanks for your comments @nimgould!
I was thinking of having multiple orderings running in parallel and to choose the one that works best for the given problem. I was thinking of adding AMD (which should be available from SuiteSparse with a similar license as Metis). Are you suggesting that reverse Cuthill-McKee is also worth having?

[nimgould]

Yes, I would add RCM if you cam find an open-source one. Is SuiteSparse really open, or is it LGPL? If not, I believe that there is at least one open source
variant of AMD (one that predates the ACM TOMS version, but is a good drop in).

[filikat]

SuiteSparse's AMD is BSD 3-clause.
I haven't checked RCM, but I found a very detailed description and pseudo-code in a book by George and Liu, and it doesn't look too complicated, so I may try to implement it myself.

[filikat]

Actually, an implementation of RCM is available under MIT license as part of the old sparsepak https://people.sc.fsu.edu/~jburkardt/f77_src/sparsepak/sparsepak.html. This is exactly the same code described in the book that I mentioned before.

[filikat]

@odow Is there a reason why you suggest building Metis as a separate library, rather than building it as part of libhighs? Is it to keep libhighs MIT licensed?
I already have a branch where I added the code of AMD, which is licensed BSD 3-clause, and it was quite easy to build it together with HiGHS.