Towards More Practical and Efficient Automatic Dominance Breaking

Authors

  • Jimmy H.M. Lee The Chinese University of Hong Kong
  • Allen Z. Zhong The Chinese University of Hong Kong

DOI:

https://doi.org/10.1609/aaai.v35i5.16505

Keywords:

Constraint Optimization, Constraint Programming

Abstract

Dominance breaking is shown to be an effective technique to improve the solving speed of Constraint Optimization Problems (COPs). The paper proposes separate techniques to generalize and make more efficient the nogood generation phase of an automated dominance breaking framework by Lee and Zhong's. The first contribution is in giving conditions that allow skipping the checking of non-efficiently checkable constraints and yet still produce sufficient useful nogoods, thus opening up possibilities to apply the technique on COPs that were previously impractical. The second contribution identifies and avoids the generation of dominance breaking nogoods that are both logically and propagation redundant. The nogood generation model is strengthened using the notion of Common Assignment Elimination to avoid generation of nogoods that are subsumed by other nogoods, thus reducing the search space substantially. Extensive experimentation confirms the benefits of the new proposals.
AAAI-21 Proceedings Cover

Downloads

Published

2021-05-18

How to Cite

Lee, J. H., & Zhong, A. Z. (2021). Towards More Practical and Efficient Automatic Dominance Breaking. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3868-3876. https://doi.org/10.1609/aaai.v35i5.16505

Issue

Vol. 35 No. 5: AAAI-21 Technical Tracks 5

Section

AAAI Technical Track on Constraint Satisfaction and Optimization