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.