Parallelization of stochastic-local-search algorithms using high-level parallel patterns

• Michael Roßbory
• Georgios Chasparis

Mathematical models for optimization can help companies optimizing their production and planning processes and therefore to reduce costs and increase quality. But applying such models effectively is challenging. Developers need expertise in mathematics and skills in software development to implement them. Furthermore optimization algorithms are inherently computationally very intensive. Parallelization reduces this computation time severely, but adds additional complexity, especially when low-level parallelization techniques are applied. Therefore developers would have to be experts in concurrent programming, too.

In this paper we present a stochastic-local-search algorithm to solve such an optimization problem from industry encountered in the slitting of metal sheets used in the production of electrical transformers. Furthermore we introduce a high-level pattern based parallelization approach that has been developed in the ParaPhrase project, depict how it can easily be applied to parallelize this optimization algorithm, without introducing the additional complexity of traditional low-level approaches, and describe why and how parallelization improves the result of the optimization process.