دانلود کتاب Instance-Specific Algorithm Configuration

فهرست مطالب :

Preface
Contents
1 Introduction
1.1 Outline
2 Related Work
2.1 Algorithm Construction
2.2 Instance-Oblivious Tuning
2.3 Instance-Specific Regression
2.4 Adaptive Methods
2.5 Chapter Summary
3 Instance-Specific Algorithm Configuration
3.1 Clustering the Instances
3.1.1 Motivation
3.1.2 Distance Metric
3.1.3 k-Means
3.1.4 g-Means
3.2 Training Solvers
3.2.1 Local Search
3.2.2 GGA
3.3 ISAC
3.4 Chapter Summary
4 Training Parameterized Solvers
4.1 Set Covering Problem
4.1.1 Solvers
4.1.2 Numerical Results
4.2 Mixed Integer Programming
4.2.1 Solver
4.2.2 Numerical Results
4.3 SAT
4.3.1 Solver
4.3.2 Numerical Results
4.4 Machine Reassignment
4.4.1 Solver
4.4.2 Numerical Results
4.5 Chapter Summary
5 ISAC for Algorithm Selection
5.1 Using ISAC as Portfolio Generator
5.2 Algorithm Configuration vs. Algorithm Selectionof SAT Solvers
5.2.1 Pure Solver Portfolio vs. SATzilla
5.2.2 Meta-Solver Configuration vs. SATzilla
5.2.3 Improved Algorithm Selection
5.2.4 Latent-Class Model-Based Algorithm Selection
5.3 Comparison with Other Algorithm Configurators
5.3.1 ISAC vs. ArgoSmart
5.3.2 ISAC vs. Hydra
5.4 Chapter Summary
6 Dynamic Training
6.1 Instance-Specific Clustering
6.1.1 Nearest Neighbor-Based Solver Selection
6.1.2 Improving Nearest Neighbor-Based Solver Selection
6.1.2.1 Distance-Based Weighting
6.1.2.2 Adaptive Neighborhood Size
6.1.2.3 Experimental Evaluation
6.2 Building Solver Schedules
6.2.1 Static Schedules
6.2.2 A Column Generation Approach
6.2.3 Dynamic Schedules
6.2.4 Semi-static Solver Schedules
6.2.4.1 Quality of Results Generated by Column Generation
6.2.5 Fixed-Split Selection Schedules
6.3 Chapter Summary
7 Training Parallel Solvers
7.1 Parallel Solver Portfolios
7.1.1 Parallel Solver Scheduling
7.1.2 Solving the Parallel Solver Scheduling IP
7.1.3 Minimizing Makespan and Post-processing the Schedule
7.2 Experimental Results
7.2.1 Impact of the IP Formulation and Neighborhood Size
7.2.2 Impact of Parallel Solvers and the Numberof Processors
7.2.3 Parallel Solver Selection and Scheduling vs. the State of the Art
7.3 Chapter Summary
8 Dynamic Approach for Switching Heuristics
8.1 Learning Dynamic Search Heuristics
8.2 Boosting Branching in Cplex for MIP
8.2.1 MIP Features
8.2.2 Branching Heuristics
8.2.2.1 Most Fractional Rounding (MF)
8.2.2.2 Less Fractional Rounding (LF)
8.2.2.3 Less Fractional and Highest Objective Rounding (LFHO)
8.2.2.4 Most Fractional and Highest Objective Rounding (MFHO)
8.2.2.5 Pseudocost Branching Weighted Score (PW)
8.2.2.6 Pseudocost Branching Product Score (P)
8.2.3 Dataset
8.3 Numerical Results
8.4 Chapter Summary
9 Evolving Instance-Specific Algorithm Configuration
9.1 Evolving ISAC
9.1.1 Updating Clusters
9.1.2 Updating Solver Selection for a Cluster
9.1.2.1 Removing Solvers
9.1.2.2 Adding Solvers
9.1.2.3 Removing Instances
9.1.2.4 Adding Instances
9.2 Empirical Results
9.2.1 SAT
9.2.2 MaxSAT
9.3 Chapter Summary
10 Improving Cluster-Based Algorithm Selection
10.1 Benchmark
10.1.1 Dataset and Features
10.2 Motivation for Clustering
10.3 Alternate Clustering Techniques
10.3.1 X-Means
10.3.2 Hierarchical Clustering
10.4 Feature Filtering
10.4.1 Chi-Squared
10.4.2 Information Theory-Based Methods
10.5 Numerical Results
10.6 Extending the Feature Space
10.7 SNNAP
10.7.1 Choosing the Distance Metric
10.7.2 Numerical Results
10.8 Chapter Summary
11 Conclusion
References