Correlation Heuristics for Constraint Programming
Effective general-purpose search strategies are an important component in Constraint Programming. We introduce a new idea, namely, using correlations between variables to guide search. Variable correlations are measured and maintained by using domain changes during constraint propagation. We propose two variable heuristics based on the correlation matrix, crbs-sum and crbs-max. We evaluate our correlation heuristics with well known heuristics, namely, dom/wdeg, impact-based search and activity-based search. Experiments on a large set of benchmarks show that our correlation heuristics are competitive with the other heuristics, and can be the fastest on many series.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems
Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based se…
SchedulingGenetic-based Constraint Programming for Resource Constrained Job Scheduling
Resource constrained job scheduling is a hard combinatorial optimisation problem that originates in the mining industry. Off-the-shelf solvers cannot solve this problem satisfactorily in reasonable timeframes, while othe…
SchedulingLearning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
Constraint programming is known for being an efficient approach for solving combinatorial problems. Important design choices in a solver are the branching heuristics, which are designed to lead the search to the best sol…
Graph Neural NetworkQ-LearningVariable SelectionSequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing
Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP), yet classical CP models based on successor variables cannot always deal with optional visits or insertio…
Matheuristics to optimize refueling and maintenance planning of nuclear power plants
Planning the maintenance of nuclear power plants is a complex optimization problem, involving a joint optimization of maintenance dates, fuel constraints and power production decisions. This paper investigates Mixed Inte…