Automatic Dominance Breaking for a Class of Constraint Optimization Problems
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1192-1200. https://doi.org/10.24963/ijcai.2020/166
Exploiting dominance relations in many Constraint Optimization Problems can drastically speed up the solving process in practice. Identification and utilization of dominance relations, however, usually require human expertise. We present a theoretical framework for a useful class of constraint optimization problems to detect dominance automatically and formulate the generation of the associated dominance breaking nogoods as constraint satisfaction. By controlling the length and quantity of the nogoods, our method can generate dominance break- ing nogoods of varying strengths. Experimentation confirms runtime improvements of up to three orders of magnitude against manual methods.
Constraints and SAT: Constraint Optimization
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Constraints: Modeling, Solvers, Applications