search

ERGO-Code / HiGHS

Linear optimization software
MIT License
980 stars 181 forks source link

Time limit not enforced during presolve #1501

Open SolverMax opened 12 months ago

SolverMax commented 12 months ago

It appears that HiGHS does not check the time_limit option during presolve. I have a model that spends a lot of time in presolve. It does not stop on the time limit while presolve is running, but does stop after presolve is complete. If I turn off presolve, then the time limit is enforced.

jajhall commented 12 months ago

It doesn't check everywhere in presolve. If you can let me have your model then I'll investigate. Thanks

SolverMax commented 12 months ago

Test model and further detail at https://github.com/SolverMax/Random/tree/main/HiGHS-testing/Presolve

jajhall commented 12 months ago

I've reproduced this behaviour.

Presolve is normally a relatively small proportion of solution time so, a time limit that's meaningful for solution time is very rarely reached in presolve.

There is a time-out check in the one part of presolve that can take an exceptional amount of time, so I can easily add it to the regular presolve

However, we can't currently update what's on PyPI, so you won't be able to use the fixed code for a while

SolverMax commented 12 months ago

It is an unusual model, so I suspect this isn't a common occurrence. By the way, the full data set has 1 million+ binary variables, which HiGHS solves to optimality in a few minutes (with almost all that time in presolve). Impressive. The time limit isn't a problem - I raised the issue because the behaviour is unexpected. No hurry for a fix.

jajhall commented 12 months ago

Thanks: with that number of binary variables, it's probably a good job that presolve works well!

I'll still put in the time-out, as it's easily done

jajhall commented 12 months ago

This is rather better now. MIP presolve spends a lot of time probing to fix binary variables, and during this call there's no test for time-out (although I could add it). Hence presolve can run quite a long time beyond the time limit.

Dario-Mantegazza commented 4 months ago

Hi, I'm not an expert of OR or LP but I'm tasked with using HIGHS with linopy. I too noticed that the pre-solve do not respect the time limit when dealing with large problems 14+M variables or even 40M variables. From my understanding, the time limit argument is enforced only on the optimization part; the presolve phase runs as long as it wants. Are there any additional arguments that I don't know of like a time-limit-presolve or that is the wanted behavior?

jajhall commented 4 months ago

The time limit is imposed for some presolve operations, but others can go into a "black hole" where the current run time isn't tested

Dario-Mantegazza commented 4 months ago

I see, can you give more details so I can cross-check with our experts and see if we end up in those black holes? Thanks anyway

jajhall commented 4 months ago

Your experts wouldn't know what's happening in presolve. If you can give me a small instance of your model using

https://linopy.readthedocs.io/en/latest/generated/linopy.model.Model.to_file.html

I can try to reproduce the issue (with an artificially low time limit)

Dario-Mantegazza commented 4 months ago

Your experts wouldn't know what's happening in presolve. If you can give me a small instance of your model using

https://linopy.readthedocs.io/en/latest/generated/linopy.model.Model.to_file.html

I can try to reproduce the issue (with an artificially low time limit)

Ok, fair 😄 I have to discuss with my other colleague if we can share information. Maybe we can continue this conv in private to see if the HiGHS lib can benefit from our issue. I will keep you posted here. Thanks for the availability :)