v1.15 Parallel MIP

[Thell]

Woohoo! This has been a long time coming and a BIG "thank you" is deserved, so...

Thank You!

Now how do we use it and when during the solving is it used and what kind of performance improvement has been seen?

---

I set 'parallel=on' and 'threads=8' and see the following output:

Solving MIP model with:
   10507 rows
   9079 cols (3320 binary, 0 integer, 18 implied int., 5741 continuous, 0 domain fixed)
   48106 nonzeros
   Thread count 8 (of 16 threads). Using 1 max workers. Parallel search off

So I assume it is working but my CPU is sitting at 7-8% which is what I'd see with a single thread. In contrast, when run as 7 processes in a 'first to finish' race the CPU is usually around 45-50% meaning each core is being utilized.

BTW - this is on multi-commodity flow problems with assignment, budget and capacity constraints.

[jajhall]

Since you have only "1 max workers", you have "Parallel search off", so no parallelism

Looking at the method that defines the maximum number of workers,

HiGHS/highs/mip/HighsMipSolver.h

Line 161 in 8396001

HighsInt getMaxNumWorkers() const {

with more than one thread - as your output states - the only way to have "1 max workers" is if the parallel option is not on (since your original MIP is not a sub-MIP).

How are you setting parallel=on?

NB @Opt-Mucca

[Thell]

How are you setting parallel=on?

    # Testing HiGHS Parallel MIP
    model.setOptionValue("parallel", "On")
    model.setOptionValue("threads", 8)

AHA! I see it... it should be "on" not "On". 🤦 Well, it was closer than my first try of 'true'.

Now I see...

Solving MIP model with:
   10507 rows
   9079 cols (3320 binary, 0 integer, 18 implied int., 5741 continuous, 0 domain fixed)
   48106 nonzeros
   Thread count 8 (of 16 threads). Using 14 max workers. Parallel search on

and the CPU% is consistently hitting ~50% and then dropping to ~10% and going right back up. During a restart/symmetry detection it stays in the low range and then goes back up. That's exactly what I would expect for the sharing and restarting. 👍

LP Iters is about 3x more than the 1 worker and B&B Expl% is ~3.5x.

Thank you (again)!

Excellent! Time for some benching. (I'll report some results later.)

---

So, as a general high level 'how this works' what's the story? The workers are processes with state sharing and the worker count is based on the CPU count, not a given option value? And, threads are per worker instance, still controlled by the 'threads' option, or are threads not considered in the workers? (Not that threads ever really did anything for MIP anyhow).

[jajhall]

AHA! I see it... it should be "on" not "On". 🤦 Well, it was closer than my first try of 'true'.

I thought we were stripping the case from prospective string option settings. I'll follow this up.

Of course, if a call such as

model.setOptionValue("parallel", "On")

to set an option is not accepted, then method returns HighsStatus::kError.

[jajhall]

AHA! I see it... it should be "on" not "On". 🤦 Well, it was closer than my first try of 'true'.

I thought we were stripping the case from prospective string option settings. I'll follow this up.

Of course, if a call such as

model.setOptionValue("parallel", "On")

to set an option is not accepted, then method returns HighsStatus::kError.

Case is stripped from values used to set bool options, but not string options. Of course string options relating to files are case sensitive, but we can strip the case from the rest.

Would also allow folk to use, for example,

solver=HiPO

[Thell]

I didn't note any printed message regarding the option and since it was a "quick and dirty - let's see it work" setup of setting those options out of the app's normal option setting it wouldn't have been captured but you are right, I should also check the status when setting an option. Any which way, "on" works.

[Thell]

Yes, an error is given. Lesson learned.

ERROR: Value "On" for parallel option is not one of "off", "choose" or "on"

[Opt-Mucca]

@Thell Thanks for the kind words! The current change is somewhere between 20-25% performance improvement on four cores (the feature is very much in the stage where minor changes can still have pretty large effects). As you observed though, the node throughput and LP iterations increase a lot.

As @jajhall said in the previous answer: To currently use "parallel MIP" set parallel=on (some more info can be found here: https://ergo-code.github.io/HiGHS/dev/parallel/ as well as potentially updated instructions if you're reading this years later)

High level overview of how it works:
A worker is an object that can run heuristics, generate cuts, and process nodes while buffering all global information until some deterministic sync point. Currently they're only used when the search starts, so most of the root node is still processed in serial (the existing parallelism not withstanding). We currently spawn 1.7x (going to spend a lot of time this release tuning this parameter) workers per thread and let work stealing distribute which thread processes which worker. For now the tasks are all issued in one batch, where HiGHS waits for them all to complete, and then syncs the buffered information and re-issues new tasks. The threads parameter (and parallel=on) would be the only way to influence "how parallel" HiGHS is.

Any feedback, especially if it's performance related, is welcome. I'm interested in what numbers you observe.

A side point: Any chance you'd want to share the multi-commodity flow instance? There is a long-term plan to write a MCF separator, and getting some instances early would be helpful.

[Thell]

My prelim bench instances show that the current 1.7x was indeed a good choice. While the CPU% and LPIters do go up fairly linearly as the worker count goes up that doesn't directly translate into a higher Expl% or finding tighter bounds quicker; which is completely understandable with cpu context switching. I did, however, expect that 7 workers would do better than 14 on my 8 physical core cpu and was surprised that 8 threads -> 14 workers was over 30% faster. So I will be doing the benches using parallel='on' and threads=0.

The task batching effect must have been what I was witnessing when seeing the CPU% rise and fall so abruptly from full to single. What distinguishes one workers task from the others? The portion of the B&B tree assigned to it (I don't even know if that makes sense)?

As for the MCF instance. Sure I can provide as many as desired. The application that is used is the BDO Empire Optimizer for Black Desert Online and it uses a variety of inputs to create and solve a user's particular problem. The problem difficulty for the MIP solver ranges from trivial to almost purely combinatoric on multiple layers, taking several hours, and is almost purely based on the coverage density of the problem because the transit layer is a road-network like planar graph restricted low range [0..=3] node weighted costs.

They are terminal to root flow problems. All of the instances have an upper limit of 25 roots (because of the input graph) and less than 1,000 total nodes (less than 2k edges), and I artificially restrict the transit layers to the nearest_n towns and root consideration to the top_n root values with an upper bound on the flow across any intermediate and the assignments are capacity restricted using a SOS1 setup.

But, yes, if those types of small size instances can be of use I'll be glad to supply some.

I also have a pure MCF instance generator for only the flow portion of that same graph for the routing problem when user's interact with their empire using Wokerman. The generator is a fuzzer which generates instances using one of 15 different clustering strategies and then solves the instance using the exact solution (via one of MIP, scipstp or Dreyfus Wagner) to validate the approximation which is used on the site for real-time routing.

Those instances of 'pure MCF' may be more beneficial.

That can generate 10s of thousands of distinct instances for MCF but of course the MIP solving of that many instances is unrealistic, so I use scipstp for solving the MCF using a composite of Node Weighted Steiner Tree problems and that setup is validated using the MCF MIP.

[Opt-Mucca]

Each worker is assigned a different node from somewhere in the branch-and-bound-tree and will only generate cuts from the associated LP solution, run from heuristics from that node, and process nodes that are descendants of the assigned node. After processing enough nodes and reaching a leaf node the worker is done, and will wait for all other workers to finish (tasks are naturally not uniformly weighted, so many instances still wait on one task for now).

That's what BDO stood for!! I've saved an instance from #1862 . If that's still representative then there's no need to send another empire instance, otherwise I'll gladly take another one. I'll update my description of the instance too.

For the 'pure MCF' instances: I'll happily take one or two if you want to attach them to this discussion. I probably won't ever plan to put them into some general testing, but I would appreciate having the instances there for later development.

[mocenigo]

Each worker is assigned a different node from somewhere in the branch-and-bound-tree and will only generate cuts from the associated LP solution, run from heuristics from that node, and process nodes that are descendants of the assigned node. After processing enough nodes and reaching a leaf node the worker is done, and will wait for all other workers to finish (tasks are naturally not uniformly weighted, so many instances still wait on one task for now).

If a worker finds a new cut, is it added immediately to the global pool of cuts or only when the workers have finished?

[Opt-Mucca]

Only when all workers in the batch are finished with their tasks. We're currently only communicating cuts that were either explicitly added to the worker's LPs or used in propagation (think I added the second condition at some point.....). So worker A might potentially have a great cut for worker B, but it won't be communicated unless it's marked as helpful by worker A independently. I imagine there's some improvement to be made here still, but it's not a current priority.

[Thell]

Nice! I think I will be saying bye-bye First to Finish. 👋

Runtimes (s):

Test	v1.14¹	v1.15¹	v1.15²
600	3924	4365	5362³
500	1935	3119	1651
400	960	886	500
300	625	917	420
200	1016	847	642
100	314	386	206

¹ - Custom multi-process First-to-Finish controller with solution sharing using 7 processes
² - Controller 'clones' disabled, parallel='on', threads=0
³ - A re-run using a different random seed completed in 2592 (123456789 instead of 0)
All other things equal - including random seeds of FtF clones.

bench_logs.md
model.lp.txt

The RHS of the 'budget' constraint for the model is set at 600 and is the only value to be altered in the test runs.

[Thell]

One last bench run on those same instances, which I thought you might find interesting...

Since there is now no need to the heavy duty controller, with all the callback machinery to handle the sync'ing of the incumbents and logging and so on I rewrote the controller to a much smaller and cleaner implementation and re-ran the benches with each test using the 123456789 seed:

Runtimes (s):

Test	v1.14¹	v1.15¹	v1.15²	v1.15⁴
600	3924	4365	5362³	2096
500	1935	3119	1651	1015
400	960	886	500	526
300	625	917	420	626
200	1016	847	642	467
100	314	386	206	175

¹ - Custom multi-process First-to-Finish controller with solution sharing using 7 processes
² - Controller 'clones' disabled, parallel='on', threads=0
³ - A re-run using a different random seed (123456789 instead of 0) completed in 2592
⁴ - Controller rewrite to eliminate callbacks, all seeds set to 123456789
All other things equal - including random seeds of FtF clones.

Now those are numbers I like. Particularly seeing the '600' test case, using the same seed as the 2592 run dropping so significantly simply by eliminating callback handling overhead!

Thanks again guys!

[mocenigo]

A simple test with my cryptography MILP models, gives for one instance
Time with 1 thread only (I did not want to re-install 1.14, I am lazy) about 130 sec
Time with 4 threads: 82 sec
Time with 8 threads: 45 sec
More I cannot really do because my laptop has an M3 cpu with 8 cores. (And, in fact, if I try to use more threads than cores, the solving time increases a bit.)

[Opt-Mucca]

Thanks for another beautiful data point! Any chance you're comfortable sharing the instance with a one sentence description (don't mind whatsoever if the variable names or some coefficients are obfuscated)?

[odow]

Mark, we should be including these reports in the report for Breakthrough. They’re nice independent verifications of your results.

[Opt-Mucca]

Should I start keeping a list of these, or this is just something to keep in mind for when we need to write up a report?

[odow]

I think both. They're good in slides, in a written report, and just as third-party validation. It's a much easier sell to someone that "look, other people took our code and got a 2x speedup; you don't have to believe my results"

[mocenigo]

I intend to provide Julian (and the entire team) with a lot of examples, and python code to generate them, since I am interested in understanding what else can be done to accelerate my type of problems.

The TL;DR is:

1. Cryptographers have been modelling block ciphers and hash functions with MILP since the 2011 Mouha-Wang-Gu-Preneel paper (DBLP: https://dblp.org/rec/conf/cisc/MouhaWGP11.html).
2. It seems to me that no cryptographer has taken the effort of trying to understand how the structure of the programs so arising may be exploited to accelerate the solving time, for instance by developing ad-hoc heuristics, or using callbacks and adding cuts, with one exception: I think Patrick Derbez may have done something, but I do not have the knowledge to understand how his callbacks work.
3. Cryptographers are happy with the performance of Gurobi, since it is quite fast and, asymptotically, significantly faster than HiGHS, on these problems–and free for them if they are in academia.
4. The cryptographers at the Technology Innovation Institute in Abu Dhabi had a large grant to perform automatic cryptanalysis, but, since they are a private research institution, they could not get free licenses. So, at some point they spent a lot of the grant in Gurobi time. This is one of the reasons they started to use also other types of solvers, such as CP and SAT/SMT. For some types of problems, a SAT/SMT formulation can be solved with small SAT/SMT solver faster than with Gurobi.
5. Some researchers have started trying to use Machine Learning to guide MILP solving, but this is only word-of-mouth at the moment, I do not remember papers or preprints.

So, it seems that there is potential for some work here, even original and publication-worthy research.

[Opt-Mucca]

Sending 1-10 problems that you think are representative is always helpful. We're slowly trying to build a test set of user instances, but it takes time to get something that is large enough to be helpful.

That's a brilliant summary! Thanks for getting me a bit interested in a new field. I was unaware that the performance gap was meaningfully larger on such instances. SAT / CP being good at some instances here would be expected.

[mocenigo]

Sending 1-10 problems that you think are representative is always helpful. We're slowly trying to build a test set of user instances, but it takes time to get something that is large enough to be helpful.

That's a brilliant summary! Thanks for getting me a bit interested in a new field. I was unaware that the performance gap was meaningfully larger on such instances. SAT / CP being good at some instances here would be expected.

Hi Mark, I have sent a few problems to Julian, and also another email today to describe what we cryptographers use MILP solvers for. I hope this is the start for a fruitful discussion.