Résumé
Dans les problèmes de satisfaction de contraintes, l’heuristique de choix de variables occupe une place centrale en sélectionnant les variables sur lesquelles brancher pendant le processus de recherche avec retour-arrière. Comme de nombreuses heuristiques de branchement ont été proposées dans la littérature, un problème clé est d’identifier, parmi un ensemble d’heuristiques candidates, celle qui est la meilleure pour résoudre une instance de satisfaction de contraintes donnée. En se basant sur l’observation que les solveurs de contraintes modernes utilisent des séquences de redémarrage, le problème d’identification de la meilleure heuristique peut être représenté dans le contexte des bandits multi-bras comme un problème d’identification du meilleur bras non stochastique. En d’autres termes, pendant chaque run d’une séquence de redémarrage donnée, l’algorithme du bandit sélectionne une heuristique et reçoit une récompense pour cette heuristique avant de passer au run suivant. L’objectif est d’identifier la meilleure heuristique en utilisant peu de runs, et sans aucune hypothèse stochastique sur le solveur de contraintes. Dans cette étude, nous proposons une variante adaptative du Successive Halving qui exploite la suite de redémarrage universelle de Luby. Nous analysons la convergence de cet algorithme de bandit dans un cadre non stochastique, et nous démontrons son efficacité empirique sur divers benchmarks en satisfaction de contraintes.