The symmetry breaking ordering constraints and design of efficient global constraints for propagation of such ordering and constraint are discussed. Efficient linear time propagation algorithms were devised for lexicographic ordering and the multiset ordering constraint. The lexicographic ordering constraint was identified on a pair of vectors of 0/1 variable together with a sum constraint on each vector. The results show that these ordering constraints are effective in breaking row and column symmetries as they significantly reduce the size of the search space and the time to solve the problems. Keywords:
Kiziltan z. (2004). Symmetry Breaking Ordering Constraints. AI COMMUNICATIONS, 17(3), 167-169.
Symmetry Breaking Ordering Constraints
KIZILTAN, ZEYNEP
2004
Abstract
The symmetry breaking ordering constraints and design of efficient global constraints for propagation of such ordering and constraint are discussed. Efficient linear time propagation algorithms were devised for lexicographic ordering and the multiset ordering constraint. The lexicographic ordering constraint was identified on a pair of vectors of 0/1 variable together with a sum constraint on each vector. The results show that these ordering constraints are effective in breaking row and column symmetries as they significantly reduce the size of the search space and the time to solve the problems. Keywords:I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
