Impact de l’orientation sur la recherche d’un cycle Hamiltonien

Télécharger le fichier original (Mémoire de fin d’études)

Perspectives

Réification d’un réseau de contraintes par une variable graphe

Nous avons vu comment utiliser une variable graphe et la contrainte NCLIQUE pour réifier un réseau de contraintes d’égalités sur les entiers et assurer une propriété globale relative au nombre de classes d’équivalences ainsi formées. Notre travail peut être repris pour partition-ner (on parle de clustering) des points dans l’espace, où des contraintes de différences sont posées pour contraindre les noeuds jugés trop distants à appartenir à des clusters différents [DDV13a, DDV13b]. Cette capacité à prendre en compte des contraintes annexes connait un intérêt grandissant en fouille de données, car elle permet de renforcer les méthodes d’apprentis-sage avec des connaissances expertes [DR09, WQD14]. On notera également que, si le nombre de clusters à rechercher est généralement un paramètre fixé dans les méthodes usuelles, la pro-grammation par contraintes permet de le représenter par une variable, offrant une plus grande ri-chesse de modélisation. Il serait donc très intéressant d’utiliser la programmation par contraintes pour résoudre des applications classiques de fouilles de données.
Nous pouvons naturellement généraliser ce raisonnement à des variables ensemblistes aussi bien discrètes que continues. On peut alors directement traiter les problèmes hybrides pour lesquels les variables à partitionner sont des ensembles continus, mais la propriété globale sur le nombre de classes d’équivalences est discrète. C’est notamment le cas de la contrainte globale NVECTOR [CJL09], qui contrôle le nombre de valeurs prises par un ensemble de boites (variables continues multidimensionnelles). Cette généralisation au cas continus et multi-dimensionnel conserve le fait que, si deux noeuds sont adjacents dans une solution, alors leurs variables associées sont égales. D’ailleurs, parallèlement à nos travaux, Jaulin a redécouvert le concept de variable de graphe pour résoudre ce problème hybride dans une application fonda-mentale en robotique [Jau14].
Enfin, on peut chercher à réifier d’autres contraintes binaires. Par exemple, il est possible de
98 CHAPITRE 7 : Cliques et allocation de ressources
passer d’un ensemble de contraintes d’égalités (e.g., xi = xj ) à un ensemble de contraintes de distances (e.g., |xi − xj | ≤ ǫ, avec ǫ ∈ R+). De même, on peut réifier un ensemble d’inégalités strictes, dont le réseau forme un graphe acyclique.
Utilisation de l’aléatoire dans les algorithmes de filtrage
Nous avons également vu une manière simple de faire appel à l’aléatoire pour améliorer un al-gorithme de filtrage et tendre vers un plus haut niveau de cohérence. On peut chercher à étendre ce type d’usages vers d’autres contraintes. Par exemple, il est possible d’atteindre facilement un compromis entre BC et GAC pour la contrainte ALLDIFFERENT en appliquant plusieurs fois l’algorithme de BC et en renumérotant aléatoirement les valeurs entre chaque appel. On obtient ainsi des intervalles différents, donc potentiellement plus de filtrage. De manière plus géné-rale, l’aléatoire ayant démontré sa force pour l’exploration de l’espace de recherche, il serait intéressant d’investiguer davantage son intérêt pour le filtrage.
Des heuristiques audacieuses, basées sur la réification de contraintes
Notre approche heuristique basée sur la réification de la contrainte MAX(X ) = N (section 7.4.1) est assez simple. En effet, seule une contrainte est réifiée, donc sa variable associée peut être créée dès la pose du modèle. Cependant, on pourrait tout à fait la généraliser à un nouveau concept d’heuristique qui, à chaque décision, introduit une nouvelle contrainte, la réifie avec une nouvelle variable binaire et branche sur cette dernière pour propager la contrainte ainsi créée et réduire un ensemble de domaines d’un coup. On aboutirait alors sur de nouvelles gé-nérations d’heuristiques, aussi bien dédiées que génériques. Concevoir une telle stratégie qui fonctionne comme une boite-noire et qui soit compétitive avec les heuristiques génériques ac-tuelles [BHLS04, MH12, Ref04] sur de nombreux problèmes semble très ambitieux. Notons tout de même que certains travaux en détection de symétries [FPS+09], en apprentissage de contraintes [BS11] et en exploitation de la réification pour la recherche [MFMS14] ont sûrement déjà apporté quelques pierres fondatrices à ce beau défi d’intelligence artificielle. En outre, de très récents travaux portant sur les cohérences fortes pour les contraintes de tables [MDL14] forment une première porte d’entrée vers de telles recherches. Pour chaque contrainte de table, ils introduisent une variable où chaque valeur représente un tuple : en branchant sur ces va-riables, on obtient naturellement une heuristique audacieuse. Enfin, si l’on ne cherche pas à développer de méthode générique, alors, sur certaines classes d’instances, il est déjà possible de réaliser des stratégies audacieuses dédiées qui soient très efficaces. En fait, cela a déjà été fait, d’une certaine manière, avec l’introduction d’algorithmes gloutons dans des contraintes globales [ABC+09, LCB13].
En travaillant sur des contraintes de placement géométrique et d’ordonnancement de tâches, Ågren et al. [ABC+09] et Letort et al. [LCB13] ont introduit des fonctionnements gloutons dans certaines contraintes globales. Le fonctionnement d’une contrainte en mode glouton est le suivant : l’algorithme glouton va chercher un support validant la contrainte. S’il y parvient alors le propagateur va fixer toutes ses variables selon le support qu’il a trouvé. Sinon, il applique normalement son filtrage et tentera à nouveau sa chance lors de la prochaine propagation. Cette technique offre des gains drastiques en termes de passage à l’échelle sur les problèmes simples. Cependant, l’algorithme glouton ne peut pas être appliqué comme n’importe quel algorithme de filtrage, durant la phase de propagation des contraintes, car on perdrait alors le caractère compositionnel et la correction du modèle. Par exemple, il est possible que la contrainte glou-tonne trouve un support valide dès le noeud racine et fixe ainsi toutes ses variables, mais rien ne garantit que ce tuple satisfasse toutes les autres contraintes du modèle. Si une contrainte
est violée, alors le solveur répondra que le problème n’admet pas de solution, ce qui est po-tentiellement faux. Au fait de cet inconvénient, les auteurs suggèrent d’appliquer l’algorithme glouton dans une procédure dédiée qui succède la phase de propagation des contraintes : une fois les contraintes propagées (sans algorithme glouton), la contrainte gloutonne crée un nou-veau noeud dans l’arbre de recherche, applique son algorithme glouton et propage l’ensemble des contraintes du modèle. Si une solution est trouvée, alors le programme s’arrête. Sinon, les variables étant fixées, un échec est créé pour déclencher un bracktrack. On se retrouve alors dans l’état précédant l’application de l’algorithme glouton et le processus de recherche peut continuer. Cette approche préserve donc la correction du modèle.
Nous émettons néanmoins quelques critiques à cette approche : premièrement, modifier l’arbre de recherche devrait être du ressort des heuristiques de recherche et non des contraintes. D’ailleurs, il peut arriver que plusieurs contraintes proposent des algorithmes gloutons, auquel cas il serait bon de développer différentes stratégies de sélection, rappelant encore une fois la notion d’heuristique de recherche. Deuxièmement, en cas d’échec de l’algorithme glouton, au-cune information n’est gagnée. Enfin, la mise en place d’un tel schéma dépend beaucoup de l’architecture même du solveur utilisé et peut s’avérer complexe, voire intrusive. Néanmoins, ceci relève peut-être du détail et ce schéma reste proche de la notion d’heuristique audacieuse. L’approche par heuristique audacieuse, plus générique, consiste à décaler l’application de l’al-gorithme glouton dans l’heuristique. Considérons un appel à une heuristique de branchement, plutôt que de simplement choisir une variable de décision et une valeur à lui affecter, notre heuristique va appliquer un algorithme glouton sur une sous-partie de notre modèle pour ainsi trouver un tuple probablement valide (à interpréter au sens large). L’algorithme glouton peut être soit donné par l’utilisateur, soit donné par les contraintes du modèle. Si plusieurs résultats (tuples) sont fournis, alors on pourra établir des critères (e.g., taille, coût) pour les ordonner. Une fois le tuple sélectionné, l’heuristique va créer une contrainte de table avec cet unique tuple, créer une variable binaire réifiant cette contrainte et enfin brancher sur cette variable en la fixant à 1. La propagation de contraintes va répercuter l’instanciation à ce tuple sur le reste du modèle. Si tout va bien, une solution sera très vite trouvée. Sinon, si la propagation mène
à un échec, un backtrack permettra de réfuter le tuple (on a ainsi un gain en information, bien que relativement faible) et relancer l’heuristique pour calculer un autre glouton, respectant si possible cette fois les autres contraintes du modèle.
Enfin, nous précisons que l’adjectif « audacieuse » est volontairement choisit pour véhiculer le principe d’effectuer des paris osés, c’est-à-dire ayant une perspective de gain élevée mais une faible probabilité de succès, durant la phase de branchement. On pourra ensuite parler de branchement basé sur la génération de tuples, l’ajout de contraintes, des algorithmes ad hoc, etc. selon l’approche mise en place techniquement.
Mis-à-part le travail portant sur les heuristiques, que l’on peut réutiliser sur des problèmes très différents, nous avons jusqu’à présent essentiellement exploité des notions de graphe pour améliorer le filtrage de contraintes globales particulières. En ce sens, ce travail était relativement dédié. Nous allons maintenant étudier comment utiliser des structures de graphes dans le but d’accélérer la propagation d’une grande famille de contraintes globales : les contraintes auto-décomposables.

Table des matières

1 Remerciements
2 Introduction
I Etat de l’art
3 Théorie des Graphes
3.1 Définitions et notations de base.
3.2 Concepts avancés
4 Programmation par contraintes
4.1 Filtrage.
4.2 Exploration
4.3 Utilisation de graphes en programmation par contraintes
4.3.1 Etude et décomposition de CSP
4.3.2 Filtrage de contraintes globales
4.4 Modélisation d’un graphe par des variables
4.4.1 Un modèle basé sur des variables entières
4.4.2 Un modèle booléen
4.4.3 Un modèle ensembliste.
4.4.4 Un modèle dédié.
II Des contraintes sur les graphes
5 Filtrage des contraintes d’arbres et de chemins orientés
5.1 Définition des contraintes de graphe.
5.1.1 La contrainte TREE
5.1.2 La contrainte ANTIARBO
5.1.3 La contrainte ARBO
5.1.4 La contrainte PATH
5.1.5 Relations entre ces contraintes
5.2 Filtrage structurel
5.2.1 Amélioration de la contrainte TREE
5.2.2 Filtrage de la contrainte ARBO
5.2.3 Filtrage de la contrainte PATH
5.3 Du chemin au circuit
5.3.1 La contrainte CIRCUIT.
5.3.2 Filtrer la contrainte CIRCUIT à partir de la contrainte PATH
5.4 Evaluation empirique
5.4.1 Passage à l’échelle pour la contrainte tree
5.4.2 Recherche d’un circuit Hamiltonien
5.5 Conclusion du chapitre
6 Résolution du problème du voyageur de commerce en contraintes
6.1 Modélisation
6.1.1 Modèle mathématique
6.1.2 Justification d’une approche non-orientée
6.1.3 Modèle en contraintes
6.1.4 Description du propagateur Lagrangien
6.2 Etude du branchement.
6.2.1 Quelques heuristiques génériques sur les graphes .
6.2.2 Adaptation de Last Conflict à une variable graphe .
6.3 Etude expérimentale
6.3.1 Impact de l’orientation sur la recherche d’un cycle Hamiltonien
6.3.2 Evaluation empirique des heuristiques de branchement.
6.4 Conclusion du chapitre.
III Des graphes pour les contraintes
7 Cliques et allocation de ressources
7.1 Description formelle du problème.
7.1.1 Un modèle mathématique.
7.1.2 Un modèle en contraintes
7.2 Reformulation par la contrainte de graphe NCLIQUE
7.2.1 Filtrage de la contrainte NCLIQUE
7.2.2 Prise en compte naturelle des contraintes de différences.
7.2.3 Inconvénient de la méthode
7.3 Utilisation d’un graphe pour filtrer ATMOSTNVALUE
7.3.1 Diversification du filtrage
7.3.2 Intégration d’inégalités
7.4 Etude expérimentale sur un problème de planification de personnel
7.4.1 Un branchement basé sur la réification de contraintes globales
7.4.2 Description des instances étudiées
7.4.3 Analyse empirique du modèle
7.4.4 Comparaison aux approches existantes
7.5 Conclusion du chapitre.
7.5.1 Perspectives
8 Auto-décomposition de contraintes globales
8.1 Fondements théoriques.
8.1.1 f-monotonie de contrainte.
8.1.2 f-décomposition de contrainte
8.1.3 f-préservation de cohérence
8.1.4 Quatre exemples génériques d’auto-décomposition
8.2 Implémentation générique d’une f∩
vn-décomposition
8.2.1 Grandes lignes.
8.2.2 Aspects avancés
8.3 Etude de la contrainte CUMULATIVE
8.3.1 f∩
vn-décomposition de la contrainte
8.3.2 Autres auto-décompositions de la contrainte.
8.3.3 Intérêt pratique.
8.4 Conclusion du chapitre.
9 Conclusion