Skip to Main content Skip to Navigation
Conference papers

Partitionnement Déterministe pour Résoudre les Problèmes de Programmation Par Contraintes en utilisant le Framework Parallèle Bobpp

Abstract : This paper presents a deterministic parallelization to explore a Constraint Programming search space. This work is an answer to an industrial project named PAJERO, which is in need of a parallel constraint solver which always responds with the same solution whether using sequential or parallel machines. It is well known that parallel tree search changes the order in which the exploration of solution space is done. In the context where the first solution found is returned, using a different number of cores may change the returned solution. In the literature, several non deterministic strategies have been proposed to parallelize the exploration of Constraint Programming search space. Most of them are based on the Work Stealing technique used to partition the Constraint Programming search space on demand and during the execution of the search algorithm. Our study focuses on the determinism of the parallel search versus the sequential one. We consider that the sequential search algorithm is deterministic, then propose an elegant solution introducing a total order on the nodes in which the parallel algorithm always gives the same solution as the sequential one regardless of the number of cores used. To evaluate this deterministic strategy, we ran tests using the Google OR-Tools Constraint Programming solver on top of our parallel Bobpp framework. The performances are illustrated by solving Constraint Programming problems modeled in FlatZinc format.
Complete list of metadata

https://hal.inria.fr/hal-01003040
Contributor : Tarek Menouer <>
Submitted on : Wednesday, June 11, 2014 - 9:48:31 AM
Last modification on : Friday, January 10, 2020 - 3:42:21 PM
Long-term archiving on: : Thursday, September 11, 2014 - 10:50:20 AM

Files

Identifiers

  • HAL Id : hal-01003040, version 1
  • ARXIV : 1406.2844

Collections

Citation

Tarek Menouer, Bertrand Le Cun. Partitionnement Déterministe pour Résoudre les Problèmes de Programmation Par Contraintes en utilisant le Framework Parallèle Bobpp. ComPAS 2014 : conférence en parallélisme, architecture et systèmes, Apr 2014, Neuchâtel, Suisse. ⟨hal-01003040⟩

Share

Metrics

Record views

212

Files downloads

433