Activity-Based Search for Black-Box Contraint-Programming Solvers

2011/05/31 by Laurent Michel, Pascal Van Hentenryck, Michel, L. +1 · 1 citation
Computer Science · Decision Sciences · Engineering · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Mathematical Software (cs.MS) #Scheduling and Optimization Algorithms #Scheduling and Timetabling Solutions

paper · pdf · doi:10.48550/arxiv.1105.6314

openalex publication_date 2011/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Robust search procedures are a central component in the design of black-box constraint-programming solvers. This paper proposes activity-based search, the idea of using the activity of variables during propagation to guide the search. Activity-based search was compared experimentally to impact-based search and the WDEG heuristics. Experimental results on a variety of benchmarks show that activity-based search is more robust than other heuristics and may produce significant improvements in performance.

Cited by

• Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks

Related

• Correlation Heuristics for Constraint Programming
• Search Combinators
• Learning Robust Search Strategies Using a Bandit-Based Approach
• Intelligent search strategies based on adaptive Constraint Handling Rules
• An AlphaZero-Inspired Approach to Solving Search Problems