Thèse : Apprendre, Analyser et Comprendre les Heuristiques de Branchement en Ordonnancement

Résumé

Cette thèse de doctorat étudie comment les solveurs d’ordonnancement s'appuyant sur la programmation par contraintes (PPC) peuvent prendre de meilleures décisions au cours de la recherche — plus précisément, quelles branches explorer et dans quel ordre. Elle se concentre sur la manière de définir et de mesurer la qualité des heuristiques de manière rigoureuse, ainsi que sur la façon dont les méthodes d’apprentissage peuvent être utilisées pour améliorer ces choix. Elle apporte trois contributions principales.

La première contribution concerne l’utilisation des réseaux neuronaux sur graphes (GNN) pour les heuristiques d’ordonnancement. La thèse développe tout d’abord une méthode GNN constructive pour l’ordonnancement sous contraintes de ressources, obtenant des résultats à la pointe de la technologie et prenant en charge des extensions en situation d’incertitude. Elle explore ensuite l’utilisation d’un GNN comme heuristique de sélection de valeur au sein d’un solveur PPC, où elle met en évidence d’importantes limites.

La deuxième contribution est un cadre d’analyse des heuristiques de sélection de valeur. La thèse introduit la notion de précision en ligne de l’heuristique en classant les décisions de branchement prises au cours de la recherche comme correctes ou incorrectes. Elle montre que les heuristiques plus précises commettent des erreurs plus coûteuses, et que la performance globale converge vers celle d’un choix aléatoire à mesure que l’on s’approche de la solution optimale. Cela explique pourquoi la sélection de valeur basée sur l’apprentissage peut rencontrer des difficultés lorsque des solutions quasi-optimales sont requises, même si elle peut encore s’avérer utile lorsque de bonnes solutions suffisent.

La troisième contribution concerne la sélection de variables. Plutôt que d’inventer directement une nouvelle heuristique, la thèse propose un critère mesurable d’efficacité basé sur la taille de l’arbre de réfutation lors de la démonstration de l’insatisfiabilité. La thèse présente un algorithme permettant de calculer des arbres de réfutation de taille minimale – fournissant ainsi des bornes inférieures sur l’effort de recherche – et explore l’utilisation directe des arbres de réfutation comme heuristique de sélection de variables, avec des améliorations prometteuses et des orientations claires pour les futurs travaux basés sur l’apprentissage.

Abstract

This PhD thesis studies how constraint programming (CP) scheduling solvers can make better decisions during search—specifically, which branches to explore and in what order. It focuses on how to define and measure heuristic quality in a principled way, and how learning methods can be used to improve these choices. The contributions are threefold.

The first contribution concerns the use of graph neural networks (GNNs) for scheduling heuristics. The thesis first develops a constructive GNN method for resource-constrained scheduling, achieving state-of-the-art results and supporting extensions under uncertainty. It then explores the use of a GNN as a value-selection heuristic inside a CP solver, where it uncovers important limitations.

The second contribution is a framework for analyzing value-selection heuristics. The thesis introduces the heuristic online accuracy by classifying branching decisions during search as correct or incorrect. It shows that more accurate heuristics make more expensive mistakes, and overall performance converges toward that of random choice when approaching the optimal solution. This explains why learning-based value selection can struggle when near-optimal solutions are required, though it may still help when good solutions are sufficient.

The third contribution concerns variable selection. Instead of inventing a new heuristic from scratch, the thesis proposes a measurable criterion for effectiveness based on refutation tree size for proving unsatisfiability. The thesis introduces an algorithm to compute minimum-sized refutation trees - providing lower bounds on search effort - and explores using refutation trees directly as a variable-selection heuristic, with promising improvements and clear directions for future learning-based work.