Parallel Constraint Programming
| Autor: | Arnaud Malapert, Jean-Charles Régin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
020203 distributed computing
Parallelism (rhetoric) Computer science business.industry Backtracking Embarrassingly parallel Cloud computing 02 engineering and technology Constraint (information theory) Search algorithm 0202 electrical engineering electronic engineering information engineering Decomposition (computer science) Constraint programming 020201 artificial intelligence & image processing business Algorithm |
| Zdroj: | Handbook of Parallel Constraint Reasoning ISBN: 9783319635156 Handbook of Parallel Constraint Reasoning |
| DOI: | 10.1007/978-3-319-63516-3_9 |
| Popis: | Constraint programming (CP) is an efficient technique for solving combinatorial optimization problems. In CP a problem is defined over variables that take values in domains and constraints which restrict the allowed combination of values. CP uses for each constraint an algorithm that removes values of variables that are inconsistent with the constraint. These algorithms are called while a domain is modified. Then, a search algorithm such as a backtracking or branch-and-bound algorithm is called to find solutions. Several methods have been proposed to combine CP with parallelism. In this chapter, we present some of them: parallelization of the propagator, parallel propagation, search splitting, also called work-stealing, problem decomposition, also called embarrassingly parallel search (EPS), and portfolio approaches. We detail the two giving the best performances in practice: the work-stealing approach and embarrassingly parallel search. We give some experiments supporting this claim on a single multi-core machine, on a data center and on the cloud. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|