A learning Portfolio solver for optimizing the performance of constraint programming problems on multi-core computing systems

摘要

This paper describes a learning parallel constraint programming (CP) solver designed for solving CPrnproblems with several instances on massively parallel computing platforms comprising multi-core parallelrnmachines or Many Integrated Cores. The CP solver proposed in this work is based on a Portfolio parallelizationrnthat employs a linear reward inaction learning algorithm in order to obtain the best possible performancernfor a large set of instances of the same problem. The linear reward inaction algorithm enables the predictionrnof the number of cores to be assigned to each search strategy based on previous experiments, reducing therncomputing time required to solve constraint satisfaction and optimization problems. The underlying principlernof the Portfolio approach is to run N sequential search strategies using N computing cores (N To NrnPortfolio) where each core uses its own strategy in order to perform a search that is different from strategiesrnused by the other cores. The first strategy that finds a solution stops all other strategies. The problem withrnthe N To N Portfolio approach is that the number of search strategies is very small compared with the currentrnnumber of computing cores used by the parallel machines. However, using an internal parallelizationrnfor each search strategy, it is possible to run N parallel search using P computing cores with P u0002 N (NrnTo P Portfolio). This N To P Portfolio performs suboptimally for solving different CP problems becausernmany computing resources are wasted. To improve this Portfolio model, an adaptive N To P Portfolio wasrnproposed, which tries to privilege the strategy that is most likely to find a solution first in order to give itrnmore computing cores than the other strategies. However, the main problem with the adaptive Portfolio isrnthat it loses all the learned information at the end of each search; it is designed to solve just one CP problem.rnFurthermore, many computational resources are wasted by both Portfolio solvers, the non-adaptive (N TornN and N To P) and the adaptive N To P Portfolio, when employed in some industrial projects, such as thernPAJERO project, which always solves different instances of the same CP problem. To minimize the amountrnof wasted resources and to learn the most efficient search strategies, we propose a new learning Portfoliornsolver that uses a learning algorithm that configures automatically number of cores to each search. The performancernobtained using the different Portfolio solvers is compared and illustrated by solving CP problemsrnusing as example the Google OR-Tools solver.