Improve calculation speed to obtain IIS

[datejada]

First, it is great to have compute_conflict! available in solvers like HiGHS. It's amazing! Thanks, @odow and @joaquimg

It may be too much to ask, but just in case. Is it possible to make it faster?

Here are three sizes of infeasible models: small, medium, and large.

Good news: For the small case, the IIS results are fast using Gurobi or HiGHS, and the output is the same.

Room for improvement: Gurobi's compute_conflict! is a couple of seconds, while HiGHS's compute_conflict! (which uses this package) I ran for more than 30 minutes for the medium and large cases and stopped both before finishing, so I don't have the total time, but I will update it once I have the full results.

Here is the code I used:

using JuMP
using HiGHS
using Gurobi

# Create a JuMP model from files
model = read_from_file("small-size-infeasible-problem.lp")
#model = read_from_file("medium-size-infeasible-problem.mps")
#model = read_from_file("large-size-infeasible-problem.mps")

set_optimizer(model, HiGHS.Optimizer)
#set_optimizer(model, Gurobi.Optimizer)
optimize!(model)
compute_conflict!(model)
if get_attribute(model, MOI.ConflictStatus()) == MOI.CONFLICT_FOUND
    iis_model, reference_map = copy_conflict(model)
    print(iis_model)
end

These are the package versions:
[2e9cd046] Gurobi v1.7.5
[87dc4568] HiGHS v1.19.0
[4076af6c] JuMP v1.27.0

Julia version: 1.11.6

Here are the links to download the files:

small-size-infeasible-problem.zip

medium-size-infeasible-problem.zip

https://filesender.surf.nl/?s=download&token=7f00f6a4-a58b-4b18-87cb-2372909d1ef5

[odow]

Okay. So I think the underlying issue is that we're querying the model row-by-row with HiGHS after a call to optimize, which is when the model is in column-major form. I wonder if I should add a special case to HiGHS.jl that does the transpose, since this comes up a few times.

[odow]

There are some improvements in v0.2. The medium cases finishes in a few minutes. I don't have access to the large.

But our algorithm is fundamentally different to Gurobi's. (They appear to deduce from presolve; they don't seem to solve any LPs.)