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:

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:
Kiziltan z.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/7855
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact