Calculating IISs

[ghauser8]

Hi Team,

Are there any plans to provide an Irreducible Infeasible Subsystem (IIS) calculator as part of the HiGHS solver?

I've heard one of the big reasons people stick with commercial solvers is for IIS logging and compute capabilities. I've done a cursory search and haven't found any open-source calculators for IISs.

If HiGHS isn't planning to do this, do you know of/have a recommendation for an open-source IIS solver?

Thanks in advance!

[jajhall]

It's already WIP in HiGHS, because I know it's values by practitioners. I started in the summer but ran out of time and also realised that I should do work on the primal simplex solver to support IIS. It's a lot of work to do well, and I know of no open-source solver that offers it. Unfortunately I can't see myself having time to return to it until next summer

[rschwarz]

I've heard that SCIP has some support for IIS and have just found the MinIISC application within in, but I'm not sure if it's really performing the same function.

[jajhall]

When I searched for open-source IIS capability, I found this, too. Reading more just now, I see that it does relate to IIS for LP. However, it focuses on finding the IIS of minimum cover, and requires a MIP to be solved. Since it's not clear how to use it to find a single IIS - that only needs hot-started LP solves - it didn't look the be a practical code for this problem. Tellingly, perhaps, it's not listed as a feature of SCIP - when it would be a very valuable tool to offer. Hence I deduce that it's not an "available" technique for what users want to know.

[rschwarz]

Sorry for the noise, then. My quick glance suggested that a minimum cover is solved in order to find the IIS...

[jajhall]

No problem, your query caused me to go back and find out more about what Pfetsch did for SCIP. An IIS if minimal cover might be satisfying to find from a research point of view, but practitioners would rather have a small IIS found heuristically

[ghauser8]

Thanks for the discussion, this is all good info. Glad to see you're way ahead of me!

[Dysg]

The inclusion of an Irreducible Infeasible Subsystem (IIS) calculator in the HiGHS solver would indeed be beneficial, as IIS functionality is a key feature in many commercial solvers. Currently, there’s no official word on HiGHS incorporating this, but it’s worth keeping an eye on updates. For open-source IIS solvers, alternatives like SCIP or COIN-OR's Cbc may offer relevant functionality, though with varying capabilities.

Hope this helps! For more help you should ask a developer to solve this issue.

[jajhall]

For open-source IIS solvers, alternatives like SCIP or COIN-OR's Cbc may offer relevant functionality, though with varying capabilities.

There's no sign of IIS calculation in Cbc, and there was an exchange on the SCIP mailing list this morning about it being implemented for SCIP, but it "will sadly not be as performant as the algorithms implemented in some of the closed-source solvers. A substantial amount of work needs to be done for that to happen."