Evaluating Simple Fully Automated Heuristics for Adaptive Constraint Propagation

• 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
• ISSN: 1082-3409; 2375-0197
• DOI: 10.1109/ICTAI.2012.123

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.