Support for `std::execution::par` for multi-thread parallel solving of subproblems

[spoorendonk]

C++17 supports parallel execution policies in algorithms like std::for_each using an execution policy std::execution::par

See https://en.cppreference.com/w/cpp/algorithm/for_each https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

This would mean compiling with the C++17 standard library (and linking with Intel TBB for GCC). On the other hand one does not need to rely on MPI.

Implementation could be something like changing (or controlling by parameter to still support MIP)

https://github.com/coin-or/Dip/blob/caecc1a924f9c28725898cb3bfbd5d8e0dafe4fc/Dip/src/DecompAlgo.cpp#L4815-L4817

with

std::vector<int> subprobIndexVec(m_numConvexCon);
std::iota(subprobIndexVec.begin(), subprobIndexVec.end(), 0);

std::for_each(std::execution::par, subprobIndexVec.begin(), subprobIndexVec.end(), [&](auto subprobIndex){
   // solve subproblem
});

[tkralphs]

I guess I would stay away from anything requiring C++17 for now unless there is a compelling reason. OpenMP is widely supported also in older compilers and I would like to be able to possibly build DipPy with older compilers on Linux in order to support the manylinux architecture. I guess we could always do an #ifdef to build with C++17 when available, but is there a downside to OpenMP? The newer standards seem to not be supported uniformly, especially by Microsoft compilers.

[spoorendonk]

Good point with the backwards compatibility. Maybe I was a little fast. I guess OpenMP is fine.

Which brings me to parallel processing of the branch tree?

https://github.com/coin-or/Dip/blob/8355253e06347700324b3bd3435266d0204695a1/Dip/src/AlpsDecompModel.cpp#L147

without going MPI. Maybe it is an ALPS issue?

I know you did some test with distributed branch-and-bound with mixed results? Or am I mistaken?

[tkralphs]

Yes, I've done a lot of work on parallel processing of the tree and that's a long conversation. But the short answer is that yes, it's not easy and it's likely that either parallelizing the block solves or parallelizing the column generation itself in some way (solve the MILPs themselves in parallel) is going to be more effective. Still, I have on my long-term TODO list to parallelize the branching tree in DIP. Since DIP is built on top of ALPS, which is itself already a parallel search framework, this should be easy. However, there are some issues in the way DIP is implemented that actually make it difficult. Basically, we need to be able to serialize the node descriptions, which isn't as straightforward as it sounds. I need to spend a little more time on it someday.

With that said, ALPS currently doesn't have a shared memory parallel mode, it only works in parallel with MPI, and that is something else needed in the long run.

[spoorendonk]

Let's close this for now an open another on branch tree parallelization when we get there