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.

[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.