Coverart for item
The Resource Handbook of parallel constraint reasoning, Youssef Hamadi, Lakhdar Sais, editors, (electronic book)

Handbook of parallel constraint reasoning, Youssef Hamadi, Lakhdar Sais, editors, (electronic book)

Label
Handbook of parallel constraint reasoning
Title
Handbook of parallel constraint reasoning
Statement of responsibility
Youssef Hamadi, Lakhdar Sais, editors
Contributor
Editor
Subject
Genre
Language
eng
Summary
This is the first book presenting a broad overview of parallelism in constraint-based reasoning formalisms. In recent years, an increasing number of contributions have been made on scaling constraint reasoning thanks to parallel architectures. The goal in this book is to overview these achievements in a concise way, assuming the reader is familiar with the classical, sequential background. It presents work demonstrating the use of multiple resources from single machine multi-core and GPU-based computations to very large scale distributed execution platforms up to 80,000 processing units. The contributions in the book cover the most important and recent contributions in parallel propositional satisfiability (SAT), maximum satisfiability (MaxSAT), quantified Boolean formulas (QBF), satisfiability modulo theory (SMT), theorem proving (TP), answer set programming (ASP), mixed integer linear programming (MILP), constraint programming (CP), stochastic local search (SLS), optimal path finding with A*, model checking for linear-time temporal logic (MC/LTL), binary decision diagrams (BDD), and model-based diagnosis (MBD). The book is suitable for researchers, graduate students, advanced undergraduates, and practitioners who wish to learn about the state of the art in parallel constraint reasoning
Member of
Cataloging source
N$T
Dewey number
006.3
Index
index present
LC call number
Q340
Literary form
non fiction
Nature of contents
  • dictionaries
  • handbooks
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
  • Hamadi, Youssef
  • Sais, Lakhdar
http://library.link/vocab/subjectName
  • Constraints (Artificial intelligence)
  • Parallel programming (Computer science)
  • Computer Science
  • Artificial Intelligence (incl. Robotics)
  • Theory of Computation
  • Operations Research/Decision Theory
  • Optimization
Label
Handbook of parallel constraint reasoning, Youssef Hamadi, Lakhdar Sais, editors, (electronic book)
Instantiates
Publication
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
  • Intro; Foreword; Preface; Contents; List of Contributors; Part I Theory and Algorithms; 1 Parallel Satisfiability; 1.1 Introduction; 1.2 Preliminaries; 1.2.1 Satisfiability (SAT); 1.2.2 Local Search Algorithms for SAT; 1.2.3 The DPLL Algorithm; 1.2.4 Resolution Refutation; 1.2.5 The CDCL Algorithm; 1.2.6 Parallel Computing Architectures; 1.2.7 Measuring Speedups; 1.3 Divide-and-Conquer Approaches; 1.3.1 Problem Decomposition and Load Balancing; 1.3.2 Implementations of Search-Space-Splitting Solvers; 1.3.3 Search Space Splitting in CDCL; 1.3.4 Cube and Conquer
  • 1.4 Parallel Portfolios -- Diversify and Conquer!1.4.1 Virtual Best Solver; 1.4.2 Pure Portfolio Solvers and Diversification; 1.4.3 Clause-Sharing Portfolios; 1.4.4 Impact of Diversification and Clause Sharing; 1.4.5 Examples of Parallel Portfolio Solvers; 1.5 Parallel Local Search; 1.5.1 Multiple Flips; 1.5.2 Portfolios; 1.6 Future Challenges; Acknowledgements; References; 2 Cube-and-Conquer for Satisfiability; 2.1 Introduction; 2.2 Preliminaries; 2.3 Combining CDCL and Lookahead; 2.4 Creating Cubes: The Basic Method; 2.5 Creating Cubes: a General Methodology; 2.5.1 General Framework
  • 2.5.2 Cutoff Heuristic2.5.3 Heuristics for Splitting; 2.6 Solving Cubes; 2.6.1 Sequential Solving; 2.6.2 Solving Cubes in Parallel; 2.7 Interleaving the Cube and Conquer Phases; 2.7.1 Ineffective Lookahead Heuristics; 2.7.2 Concurrent Cube-and-Conquer; 2.7.3 Cubes on Demand; 2.8 Proofs of Unsatisfiability; 2.9 Experimental Evaluation; 2.9.1 Application Benchmarks; 2.9.2 The Boolean Pythagorean Triples Problem; 2.10 Conclusions; Acknowledgements; References; 3 Parallel Maximum Satisfiability; 3.1 Introduction; 3.2 Maximum Satisfiability; 3.2.1 Sequential MaxSAT Algorithms
  • 3.2.1.1 Linear Search Algorithms3.2.1.2 Unsatisfiability-Based Algorithms; 3.2.1.3 Other Algorithmic Solutions and Implementation Issues; 3.3 Parallel MaxSAT; 3.3.1 Portfolio Approaches; 3.3.1.1 Parallel Unsatisfiability-Based Algorithms; 3.3.1.2 Parallel Linear Search Algorithms; 3.3.1.3 Implementation Issues; 3.3.2 Search Space Splitting; 3.3.2.1 Interval Splitting; 3.3.2.2 Guiding Paths; 3.3.2.3 Other Splitting Schemes and Implementation Issues; 3.3.3 Clause Sharing; 3.3.3.1 Conditions for Safe Clause Sharing; 3.3.3.2 Clause-Sharing Heuristics
  • 3.3.3.3 Comparison Between Clause-Sharing Heuristics3.4 Deterministic Parallel MaxSAT; 3.4.1 Motivation; 3.4.2 Deterministic Solver; 3.4.2.1 Standard Synchronization; 3.4.2.2 Period Synchronization; 3.4.2.3 Dynamic Synchronization; 3.4.3 Comparison Between Non-deterministic and Deterministic Solvers; 3.5 Research Directions; 3.5.1 Scalability; 3.5.2 Clause Sharing; Acknowledgments; References; 4 Parallel Solving of Quantified Boolean Formulas; 4.1 Introduction; 4.2 Background; 4.3 Sequential Search-Based QBF Solving; 4.4 Parallel QBF Solving at a Glance; 4.5 Parallel QBF-Solving Approaches
Extent
1 online resource.
Form of item
online
Isbn
9783319635163
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/978-3-319-63516-3
System control number
  • on1030892434
  • (OCoLC)1030892434
Label
Handbook of parallel constraint reasoning, Youssef Hamadi, Lakhdar Sais, editors, (electronic book)
Publication
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
  • Intro; Foreword; Preface; Contents; List of Contributors; Part I Theory and Algorithms; 1 Parallel Satisfiability; 1.1 Introduction; 1.2 Preliminaries; 1.2.1 Satisfiability (SAT); 1.2.2 Local Search Algorithms for SAT; 1.2.3 The DPLL Algorithm; 1.2.4 Resolution Refutation; 1.2.5 The CDCL Algorithm; 1.2.6 Parallel Computing Architectures; 1.2.7 Measuring Speedups; 1.3 Divide-and-Conquer Approaches; 1.3.1 Problem Decomposition and Load Balancing; 1.3.2 Implementations of Search-Space-Splitting Solvers; 1.3.3 Search Space Splitting in CDCL; 1.3.4 Cube and Conquer
  • 1.4 Parallel Portfolios -- Diversify and Conquer!1.4.1 Virtual Best Solver; 1.4.2 Pure Portfolio Solvers and Diversification; 1.4.3 Clause-Sharing Portfolios; 1.4.4 Impact of Diversification and Clause Sharing; 1.4.5 Examples of Parallel Portfolio Solvers; 1.5 Parallel Local Search; 1.5.1 Multiple Flips; 1.5.2 Portfolios; 1.6 Future Challenges; Acknowledgements; References; 2 Cube-and-Conquer for Satisfiability; 2.1 Introduction; 2.2 Preliminaries; 2.3 Combining CDCL and Lookahead; 2.4 Creating Cubes: The Basic Method; 2.5 Creating Cubes: a General Methodology; 2.5.1 General Framework
  • 2.5.2 Cutoff Heuristic2.5.3 Heuristics for Splitting; 2.6 Solving Cubes; 2.6.1 Sequential Solving; 2.6.2 Solving Cubes in Parallel; 2.7 Interleaving the Cube and Conquer Phases; 2.7.1 Ineffective Lookahead Heuristics; 2.7.2 Concurrent Cube-and-Conquer; 2.7.3 Cubes on Demand; 2.8 Proofs of Unsatisfiability; 2.9 Experimental Evaluation; 2.9.1 Application Benchmarks; 2.9.2 The Boolean Pythagorean Triples Problem; 2.10 Conclusions; Acknowledgements; References; 3 Parallel Maximum Satisfiability; 3.1 Introduction; 3.2 Maximum Satisfiability; 3.2.1 Sequential MaxSAT Algorithms
  • 3.2.1.1 Linear Search Algorithms3.2.1.2 Unsatisfiability-Based Algorithms; 3.2.1.3 Other Algorithmic Solutions and Implementation Issues; 3.3 Parallel MaxSAT; 3.3.1 Portfolio Approaches; 3.3.1.1 Parallel Unsatisfiability-Based Algorithms; 3.3.1.2 Parallel Linear Search Algorithms; 3.3.1.3 Implementation Issues; 3.3.2 Search Space Splitting; 3.3.2.1 Interval Splitting; 3.3.2.2 Guiding Paths; 3.3.2.3 Other Splitting Schemes and Implementation Issues; 3.3.3 Clause Sharing; 3.3.3.1 Conditions for Safe Clause Sharing; 3.3.3.2 Clause-Sharing Heuristics
  • 3.3.3.3 Comparison Between Clause-Sharing Heuristics3.4 Deterministic Parallel MaxSAT; 3.4.1 Motivation; 3.4.2 Deterministic Solver; 3.4.2.1 Standard Synchronization; 3.4.2.2 Period Synchronization; 3.4.2.3 Dynamic Synchronization; 3.4.3 Comparison Between Non-deterministic and Deterministic Solvers; 3.5 Research Directions; 3.5.1 Scalability; 3.5.2 Clause Sharing; Acknowledgments; References; 4 Parallel Solving of Quantified Boolean Formulas; 4.1 Introduction; 4.2 Background; 4.3 Sequential Search-Based QBF Solving; 4.4 Parallel QBF Solving at a Glance; 4.5 Parallel QBF-Solving Approaches
Extent
1 online resource.
Form of item
online
Isbn
9783319635163
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/978-3-319-63516-3
System control number
  • on1030892434
  • (OCoLC)1030892434

Library Locations

Processing Feedback ...