Premium
A learning Portfolio solver for optimizing the performance of constraint programming problems on multi‐core computing systems
Author(s) -
Menouer Tarek,
Sukhija Nitin,
Bertrand Le Cun
Publication year - 2016
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3840
Subject(s) - solver , computer science , portfolio , multi core processor , constraint satisfaction problem , constraint programming , mathematical optimization , portfolio optimization , massively parallel , set (abstract data type) , parallel computing , artificial intelligence , mathematics , stochastic programming , probabilistic logic , financial economics , economics , programming language
Summary This paper describes a learning parallel constraint programming (CP) solver designed for solving CP problems with several instances on massively parallel computing platforms comprising multi‐core parallel machines or Many Integrated Cores. The CP solver proposed in this work is based on a Portfolio parallelization that employs a linear reward inaction learning algorithm in order to obtain the best possible performance for a large set of instances of the same problem. The linear reward inaction algorithm enables the prediction of the number of cores to be assigned to each search strategy based on previous experiments, reducing the computing time required to solve constraint satisfaction and optimization problems. The underlying principle of the Portfolio approach is to run N sequential search strategies using N computing cores ( N To N Portfolio ) where each core uses its own strategy in order to perform a search that is different from strategies used by the other cores. The first strategy that finds a solution stops all other strategies. The problem with the N To N Portfolio approach is that the number of search strategies is very small compared with the current number of computing cores used by the parallel machines. However, using an internal parallelization for each search strategy, it is possible to run N parallel search using P computing cores with P ≫ N ( N To P Portfolio ). This N To P Portfolio performs suboptimally for solving different CP problems because many computing resources are wasted. To improve this Portfolio model, an adaptive N To P Portfolio was proposed, which tries to privilege the strategy that is most likely to find a solution first in order to give it more computing cores than the other strategies. However, the main problem with the adaptive Portfolio is that it loses all the learned information at the end of each search; it is designed to solve just one CP problem. Furthermore, many computational resources are wasted by both Portfolio solvers, the non‐adaptive ( N To N and N To P ) and the adaptive N To P Portfolio , when employed in some industrial projects, such as the PAJERO project, which always solves different instances of the same CP problem. To minimize the amount of wasted resources and to learn the most efficient search strategies, we propose a new learning Portfolio solver that uses a learning algorithm that configures automatically number of cores to each search. The performance obtained using the different Portfolio solvers is compared and illustrated by solving CP problems using as example the Google OR‐Tools solver. Copyright © 2016 John Wiley & Sons, Ltd.