Conflict Ordering Search for Scheduling Problems
(2015) Principles and Practice of Constraint Programming — Location: Cork Ireland
Files
cp2015_cos.pdf
Open Access - Adobe PDF
- 316.55 KB
Details
- Authors
- et. al.
- Abstract
- We introduce a new generic scheme to guide backtrack search, called Conflict Ordering Search (COS), that reorders variables on the basis of conflicts that happen during search. Similarly to generalized Last Conflict (LC), our approach remembers the last variables on which search decisions failed. Importantly, the initial ordering behind COS is given by a specified variable ordering heuristic, but contrary to LC, once consumed, this first ordering is forgotten, which makes COS conflict-driven. Our preliminary experiments show that COS – although simple to implement and parameter-free – is competitive with specialized searches on scheduling problems. We also show that our approach fits well within a restart framework, and can be enhanced with a value ordering heuristic that selects in priority the last assigned values.
- Affiliations
Citations
Gay, S., Hartert, R., Schaus, P., & et al. (2015). Conflict Ordering Search for Scheduling Problems. Lecture Notes in Computer Science. Published. Principles and Practice of Constraint Programming, Cork Ireland. https://doi.org/10.1007/978-3-319-23219-5_10