Evaluating Simple Fully Automated Heuristics for Adaptive Constraint Propagation

Despite the advancements in constraint propagation methods, most CP solvers still apply fixed predetermined propagators on each constraint of the problem. However, selecting the appropriate propagator for a constraint can be a difficult task that requires expertise. One way to overcome this is throu...

Full description

Saved in:
Bibliographic Details
Main Authors: Paparrizou, A., Stergiou, K.
Format: Conference Proceeding
Language:English
Subjects:
Boolean functions
constraint programming
constraint propagation
Data structures
Monitoring
Robustness
search
Search problems
Tuning
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Despite the advancements in constraint propagation methods, most CP solvers still apply fixed predetermined propagators on each constraint of the problem. However, selecting the appropriate propagator for a constraint can be a difficult task that requires expertise. One way to overcome this is through the use of machine learning. A different approach uses heuristics to dynamically adapt the propagation method during search. The heuristics of this category proposed in [1] displayed promising results, but their evaluation and application suffered from two important drawbacks: They were only defined and tested on binary constraints and they required calibration of their input parameters. In this paper we follow this line of work by describing and evaluating simple, fully automated heuristics that are applicable on constraints of any arity. Experimental results from various problems show that the proposed heuristics can outperform a standard approach that applies a preselected propagator on each constraint resulting in an efficient and robust solver.
ISSN:1082-3409
2375-0197
DOI:10.1109/ICTAI.2012.123