How to improve ability for HiGHS to solve problems and what can influence the performance? #1763
Replies: 4 comments 1 reply
-
|
The HiGHS MIP solver - like all practical open-source MIP solvers - is single-threaded.
Not easily, no, otherwise we'd have done it. We have plans to parallelise the tree search, which should enhance performance significantly. Please don't try to implement this yourself! Problem dimensions and solution time are only loosely correlated for MIP - and the proportion of integer variables is another factor. Some very large MIPs are solved easily; some relatively small MIPs are unsolved by commercial codes. Note that this isn't an "issue" |
Beta Was this translation helpful? Give feedback.
-
Thank you very much for your corrections. I'm aware that HiGHS is currently one of the most advanced tools available, but may I ask if there are any open-source tools available for parallel tree searching? My use case requires fast solving as much as possible. Additionally, are there tools that can leverage GPU for parallel solving? Moreover, are there any metrics currently available to estimate the complexity of problems, or is complexity judged solely based on empirical values? |
Beta Was this translation helpful? Give feedback.
-
For parallel tree searching in the abstract, perhaps there are open-source tools, but nothing I know of for MIP. And even if there were such tools, integrating them into a code with the complexity of our MIP solver would be a nightmare. No, the HiGHS MIP solver was written with parallel tree search in mind, and I know essentially how to do it
Due to the consequences of exploiting matrix sparsity, it's hard to predict the complexity of LPs, even empirically. It's harder still for MIPs |
Beta Was this translation helpful? Give feedback.
-
|
@jajhall I was wondering if there is a timeline for parallelizing the tree search. I'm not sure if it's trivial to break it down to smaller tasks for people to pick up but if so I'd be willing to put some time on that. |
Beta Was this translation helpful? Give feedback.
-
|
I'll start work on it in September. The way that the MIP solver has been written it should be a single task. Hence, thanks for offering, but I can't see it being efficient to involve others |
Beta Was this translation helpful? Give feedback.
-
Hello,
I want to leverage HiGHS for problem-solving purposes.
Firstly, my focus has been on conducting benchmarks to assess HiGHS' computing capabilities effectively.
Then I selected the MIPLIB2017 benchmark(https://miplib.zib.de/tag_benchmark.html), like "30n20b8" and "50v-10", for evaluation.
The benchmark result are as follows:
benchmark variables constraint time (s)
30n20b8 18380 576 1955.54
50v-10 2013 233 23657.89
In those tests, I found that the CPU utilization appears to be suboptimal when HiGHS solving MIP problems.
Most of the time, only one thread appears to be actively engaged in problem-solving tasks.
So I want to explore strategies for enhancing the utilization of multi-threading capabilities within HiGHS. Does multi-thread solving can be realized easily to solve MIP problems?
Furthermore, I am puzzled by the discrepancy between the benchmark results of "50v-10"
which has fewer variables and constraints than "30n20b8", yet is solved at a slower pace than the latter.
Thank you for any reply.
Beta Was this translation helpful? Give feedback.
All reactions