A Hybrid Dynamic Arity Search Heuristic for Constraint Programming
- Resource Type
- Conference
- Authors
- Xia, Wei; Yap, Roland H. C.
- Source
- 2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI) ICTAI Tools with Artificial Intelligence (ICTAI), 2020 IEEE 32nd International Conference on. :126-131 Nov, 2020
- Subject
- Components, Circuits, Devices and Systems
Computing and Processing
Robotics and Control Systems
Signal Processing and Analysis
Switches
Tools
Programming
Search problems
Automobiles
Hybrid electric vehicles
Optimization
search heuristics
adaptive heuristics
CSP
constraint solver
constraint programming
- Language
- ISSN
- 2375-0197
Effective and robust search heuristics are critical for solving constraint satisfaction or optimization problems. In this paper, we propose a new hybrid heuristic which uses the idea of reducing the dynamic arity of constraints, called Constraint-Arity-Reduction (CAR). The hybrid heuristic is formed with a base heuristic which switches to CAR using a switching heuristic. We experimented with hybrids of CAR combining existing state-of-the-art search heuristics. Experimental results on a variety of structured benchmarks show that hybrid CAR heuristics is an effective and competitive strategy, which can successfully reduce the search space and improve the performance of existing heuristics on a variety of problems.