Implementation and Evaluation of Counting-Based Search for Table Constraints in the OscaR Solver

Dans ce mémoire, nous allons nous intéresser à la programmation par contraintes, un outil efficace en ce qui concerne la résolution de problèmes combinatoires. Nous allons nous intéresser aux problèmes utilisant les contraintes table et plus particulièrement leur implémentation compacte qui a été grandement améliorée par l'utilisation de la structure de données «sparse bit set» réversible. Nous contribuerons en créant une heuristique de recherche basée sur le dénombrement utilisant l'information sur les supports des contraintes table. Nous allons implémenter puis évaluer un algorithme de dénombrement sur Oscar, une librairie de résolution de problèmes par contraintes créée pour résoudre les problèmes combinatoires. Nous définirons alors un algorithme pour obtenir les supports et un algorithme pour réaliser une heuristique de recherche utilisant les informations précédentes. Tous ces algorithmes ont un but commun, mettre en place une recherche basée sur le dénombrement. Nous allons expliquer les modifications faites à Oscar et les heuristiques de recherche que nous avons créées dans Oscar. Finalement, nous présenterons nos résultats sur différents exemplaires de problèmes et nous analyserons les résultats comparés à l'état de l'art pour en déduire les améliorations apportées. Nous utiliserons pour cela les algorithmes suivants: dom et dom/deg. L'expérience montrera que notre recherche basée sur le dénombrement est compétitive pour les exemplaires complexes mais qu'elle coûte plus de temps dans certains cas, même si nous avons moins d'échecs.

Abstract

In this thesis, we work on constraint programming, an efficient approach to solve combinatorial problems. We consider problems using table constraints and in particular the compact table implementation. Reversible sparse bit sets have been used for the compact table implementation recently, and it improves its efficiency. We contribute by making the heuristic search more efficient for such problems by using counting-based search. Counting-based search uses the supports information from the reversible sparse bit set data structure (used to maintain supports in the table constraints). We implement and evaluate our contribution in Oscar, a constraint programming solver to solve combinatorial problems. We explain the modifications we made in Oscar and the heuristic searches we created in Oscar. We define an algorithm to get the supports from table constraints, a variable ordering heuristic search, and a value ordering heuristic search. All of these algorithms work toward the same goal, counting-based search. Finally, we present our results on different instances of problems and analyze the results and improvements. We compare our methods with dom and dom/deg. The experiment shows counting-based search is competitive if the instances are hard and it costs more time in some instances even if we have fewer failures.