02/02/2021

Towards More Practical and Efficient Automatic Dominance Breaking

Jimmy H.M. Lee, Allen Z. Zhong

Keywords:

Abstract Paper Similar Papers

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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38947933
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 19:40 
 0
 0
 0
 0
 4:59 
 0
 0
 0
 0
 19:54 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 5:19 
 0
 0
 0
 0
 0:59 
 0
 0
 0
 0
 6:23 
 0
 0
 0
 0
 14:37 
 0
 0
 0
 0
 15:17 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 4:48 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 5:01 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 13:13 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 2:30 
 0
 0
 0
 0
 10:19 
 0
 0
 0
 0
 12:02 
 0
 0
 0
 0
 10:19 
 0
 0
 0
 0
 12:12 
 0
 0
 0
 0
 14:16 
 0
 0
 0
 0
 11:43 
 0
 0
 0
 0
 9:28 
 0
 0
 0
 0
 10:40 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 11:22 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 13:17 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 12:50 
 0
 0
 0
 0
 13:36 
 0
 0
 0
 0
 8:11 
 0
 0
 0
 0
 6:35 
 0
 0
 0
 0
 17:01 
 0
 0
 0
 0
 2:50 
 0
 0
 0
 0
 5:11 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 6:15