Résumé: La contrainte Cumulative est couramment utilisée pour résoudre des problèmes d’ordonnancement à l’aide de la programmation par contraintes. Le raisonnement énergétique est une technique de filtrage très puissante pour cette contrainte. Toutefois, ses algorithmes de vérification et de filtrage traitent O(n2) intervalles de temps, ce qui les rend trop lents pour être utilisés en pratique. Nous présentons une nouvelle technique permettant de traiter uniquement O(n log n) intervalles. Nous montrons également comment calculer l’énergie dans un intervalle en O(log n). Cela nous permet de proposer un algorithme de vérification en O(n log2 n) et un algorithme de filtrage en O(n2 log n). En pratique, ces deux algorithmes appliquent le raisonnement énergique plus rapidement que l’état de l’art.
http://www2.ift.ulaval.ca/~quimper/Seminaires/