10

I am solving (or say, trying to find good solutions for) an arbitrary combinatorial optimization problem, think of it as a Vehicle Routing Problem with a bunch of side constraints that are not relevant for this question. I coded an Adaptive Large Neighborhood Search (ALNS) for it.

I want to explore "easy" opportunities to enhance its speed by using some kind of parallelization, to at least make use of what every modern computer has available nowadays (more than a single core).

I have already tried two simple "tweaks". 1) Simply run the ALNS for each available thread and pick the best solution at the end, and 2) Run the ALNS for each available thread, but ensure that after every X iterations each thread continues with the best solution of all the threads at that time.

My question is if there are other alternatives to parallelize an ALNS which are easy to implement, won't require days of coding, and potentially impact the runtime/solution quality in a positive way?

Ps. I code in C++, so suggestions tailored towards that are welcome.

EhsanK
  • 5,864
  • 3
  • 17
  • 54
Albert Schrotenboer
  • 1,859
  • 12
  • 27

2 Answers2

5

Another paradigm to parallelize search heuristics is the Backbone strategy. See for example this paper.

The main idea is to run multiple instances of an arbitrary heuristic in parallel, and then compare the resulting solutions of each instance. "structures" (e.g. subtours in TSP) common in all/most solutions (called Backbones) are used to reduce the problem size (e.g. TSP: reduce the subtour to 2 nodes), and then the same approach is used on the reduced problem.

Michael Feldmeier
  • 2,856
  • 14
  • 40
2

I've implemented reproducible parallelization on a number of Local Search variants with incremental score calculation (= delta constraint and fitness evaluation). Some of our requirements you might be able to forgo (most notably OO/FP support), but others (such as not sacrificing incremental calculation) are crucial to get better results.

For more information, see this blog post and we're finishing up an academic paper that will include all the details too.

Geoffrey De Smet
  • 4,851
  • 10
  • 34