Heuristiques de branchement basées sur le dénombrement pour la résolution de problèmes d'arbres de recouvrement contraints

This Master's thesis focuses on Constraint Programming (CP), a powerful approach to solve combinational problems. Our work revolves around one of the main components of CP : branching heuristics. This component defines how the search space must be explored, which areas should be visited first in order to quickly find a solution to the problem. Advances on this topic are critical, since CP lacks a generic effective search approach. Counting-based branching heuristics such as maxSD were shown to be effective on a variety of constraint satisfaction problems. These heuristics require that we equip each family of constraints with a dedicated algorithm to compute the local solution density of variable assignments, much as what has been done with filtering algorithms to apply local inference. However, many constraints still lack such an algorithm. In our work, we derive an exact polytime algorithm to compute solution densities for a spanning tree constraint, starting from a known result about the number of spanning trees in an undirected graph. We then extend the algorithm for directed graphs, which allows us to compute solution densities for a reverse arborescence constraint, also in polytime. We then empirically compare branching heuristics based on those results with other generic heuristics. First, we use the degree contrained spanning tree, on undirected graphs, to demonstrate the effectiveness of our approach. Then, for the directed graphs, we use the k-arborescence problem. Counting-based branching heuristics prove to be very effective for both the undirected and directed case, finding solutions quickly and without many backtracks.

Résumé

Ce mémoire se concentre sur la programmation par contraintes (CP), une approche puissante pour résoudre des problèmes combinatoires. Notre travail tourne autour de l'un des concepts clés de la CP : les heuristiques de branchement. Cette composante définit comment l'espace de recherche doit être exploré, quelles régions devraient être visitées en premier pour trouver une solution rapidement. Le progrès sur ce sujet est important, étant donné que la CP n'admet toujours pas d'approche générique efficace pour la recherche. Les heuristiques de branchement basées sur le dénombrement comme maxSD se sont montrées efficaces pour une variété de problèmes de satisfaction de contraintes. Ces heuristiques ont besoin d'un algorithme dédié qui calcule la densité de solution locale pour chaque paire de variable-valeur, pour chaque contrainte, de façon semblable à ce qui a été fait pour les algorithmes de filtrage, pour appliquer l'inférence locale. Cependant, plusieurs contraintes n'ont toujours pas de tel algorithme. Dans notre travail, nous dérivons un algorithme exact qui, en temps polynomial, calcule la densité de solution pour la contrainte d'arbre de recouvrement, à partir d'un résultat connu sur le nombre d'arbres de recouvrement dans un graphe non orienté. Nous étendons ensuite cet algorithme pour les graphes orientés, ce qui nous permet de calculer la densité de solution pour une contrainte d'anti-arborescence, également en temps polynomial. Ensuite, nous comparons empiriquement les heuristiques de branchement basées sur ces résultats avec d'autres approches génériques. Tout d'abord, nous utilisons le problème d'arbres de recouvrement de degré contraint, sur des graphes non orientés pour démontrer l'efficacité de notre approche. Ensuite, pour les graphes orientés, nous utilisons le problème de la k-arborescence.Les heuristiques de branchement basées sur le dénombrement se montrent comme des approches très efficaces, autant pour le cas non orienté que pour le cas orienté, trouvant rapidement des solutions avec un minimum de retours en arrière.