Combinatorial Search: From Algorithms to Systems

Combinatorial Search: From Algorithms to Systems
	Foreword
	Contents
	List of Figures
	List of Tables
Chapter 1: Introduction
Chapter 2: Boosting Distributed Constraint Networks
	2.1 Introduction
	2.2 Previous Work
	2.3 Technical Background
		2.3.1 Distributed Constraint Satisfaction Problems
		2.3.2 DisCSP Algorithms
		2.3.3 Performance of DisCSP Algorithms
	2.4 Risks in Search
		2.4.1 Randomization Risk
		2.4.2 Selection Risk
	2.5 Boosting Distributed Constraint Satisfaction
		2.5.1 Utilizing Competition with Portfolios
		2.5.2 Utilizing Cooperation with Aggregation
		2.5.3 Categories of Knowledge
		2.5.4 Interpretation of Knowledge
		2.5.5 Implementation of the Knowledge Sharing Policies
		2.5.6 Complexity
	2.6 Empirical Evaluation
		2.6.1 Basic Performance
		2.6.2 Randomization Risk
		2.6.3 Selection Risk
		2.6.4 Performance with Aggregation
		2.6.5 Scalability
		2.6.6 Idle Time
	2.7 Summary
Chapter 3: Parallel Tree Search for Satisfiability
	3.1 Introduction
	3.2 Previous Work
	3.3 Technical Background
		3.3.1 DPLL Search
		3.3.2 Modern SAT Solvers
		3.3.3 Multicore Architectures
		3.3.4 AIMD Feedback Control-Based Algorithm
	3.4 ManySAT: A Parallel SAT Solver
		3.4.1 Restart Policies
		3.4.2 Heuristic
		3.4.3 Polarity
		3.4.4 Learning
		3.4.5 Clause Sharing
		3.4.6 Summary
	3.5 Evaluation
		3.5.1 Performance Against a Sequential Algorithm
		3.5.2 Performance Against Other Parallel SAT Solvers
	3.6 Control-Based Clause Sharing
		3.6.1 Throughput and Quality-Based Control Policies
		3.6.2 Experiments
	3.7 Summary
Chapter 4: Parallel Local Search for Satisfiability
	4.1 Introduction
	4.2 Previous Work
		4.2.1 Incomplete Methods for Parallel SAT
		4.2.2 Cooperative Sequential Algorithms
	4.3 Technical Background
		4.3.1 Local Search for SAT
		4.3.2 Refinements
	4.4 Knowledge Sharing in Parallel Local Search for SAT
		4.4.1 Using Best Known Configurations
		4.4.2 Weighting Best Known Configurations
		4.4.3 Restart Policy
	4.5 Experiments
		4.5.1 Experimental Settings
		4.5.2 Practical Performances with Four Cores
		4.5.3 Practical Performances with Eight Cores
		4.5.4 Analysis of the Diversification/Intensification Trade-off
		4.5.5 Analysis of the Limitations of the Hardware
	4.6 Summary
Chapter 5: Learning Variable Dependencies
	5.1 Introduction
	5.2 Previous Work
	5.3 Technical Background
	5.4 Exploiting Weak Dependencies in Tree-Based Search
		5.4.1 Weak Dependencies
		5.4.2 Example
		5.4.3 Computing Weak Dependencies
		5.4.4 The domFD Dynamic Variable Ordering
		5.4.5 Complexities of domFD
	5.5 Experiments
		5.5.1 The Problems
		5.5.2 Searching for All Solutions or for an Optimal Solution
		5.5.3 Searching for a Solution with a Classical Branch-and-Prune Strategy
		5.5.4 Searching for a Solution with a Restart-Based Branch-and-Prune Strategy
		5.5.5 Synthesis
	5.6 Summary
Chapter 6: Continuous Search
	6.1 Introduction
	6.2 Related Work
	6.3 Technical Background
		6.3.1 Constraint Satisfaction Problems
		6.3.2 Supervised Machine Learning
	6.4 Continuous Search in Constraint Programming
	6.5 Dynamic Continuous Search
		6.5.1 Representing Instances: Feature Definition
		6.5.2 Feature Pre-processing
		6.5.3 Learning and Using the Heuristics Model
		6.5.4 Generating Examples in Exploration Mode
		6.5.5 Imbalanced Examples
	6.6 Experimental Validation
		6.6.1 Experimental Settings
		6.6.2 Practical Performances
		6.6.3 The Power of Adaptation
	6.7 Summary
Chapter 7: Autonomous Search
	7.1 Introduction
	7.2 Solver Architecture
		7.2.1 Problem Modeling/Encoding
		7.2.2 The Evaluation Function
		7.2.3 The Solving Algorithm
		7.2.4 Configuration of the Solver: The Parameters
		7.2.5 Control
		7.2.6 Existing Classifications and Taxonomies
	7.3 Architecture of Autonomous Solvers
		7.3.1 Control by Self-adaptation
		7.3.2 Control by Supervised Adaptation
		7.3.3 Searching for a Solution vs. Solutions for Searching
		7.3.4 A Rule-Based Characterization of Solvers
	7.4 Case Studies
		7.4.1 Tuning Before Solving
			Preprocessing Techniques
			Parameter Tuning on Preliminary Experiments
			Component Setting Before Solving
		7.4.2 Control During Solving
			Controlling Encoding
			Controlling Variable Orderings and Value Selection in Search Heuristics
			Evolving Heuristics
			Controlling Evaluation Function
			Parameter Control in Metaheuristic Algorithms
		7.4.3 Control During Solving in Parallel Search
	7.5 Summary
Chapter 8: Conclusion and Perspectives
References