Contraintes globales de partitionnement de graphe par des arbres
Xavier Lorca
Hermes Science
Lavoisier
Première partie. Programmation par contraintes et bases de la théorie des graphes9
Chapitre 1. Introduction à la programmation par contraintes13
1.1. Qu'est-ce qu'une variable ?14
1.2. Qu'est-ce qu'une contrainte ?15
1.3. Qu'est-ce qu'une contrainte globale ?16
1.4. Qu'est-ce qu'un algorithme de propagation ?17
1.5. Qu'est-ce qu'un niveau de consistance ?19
1.6. Qu'est-ce qu'un solveur de contraintes ?19
1.7. Utilisation d'un solveur de contraintes21
1.7.1. De l'importance de la modélisation21
1.7.2. De l'importance des heuristiques guidant la recherche23
1.7.3. De l'importance de l'utilisation des contraintes globales24
1.8. Organisation de l'ouvrage25
Chapitre 2. Théorie des graphes et programmation par contraintes27
2.1. Modéliser des graphes avec la programmation par contraintes28
2.1.1. Représenter une famille de graphes28
2.1.2. Définitions et propriétés de graphes utiles30
2.1.3. Implémentation des graphes et complexité34
2.2. La théorie des graphes au service de la programmation par contraintes35
2.3. La programmation par contraintes au service de la théorie des graphes37
Chapitre 3. Partitionnement de graphe par des arbres39
3.1. Dans les graphes non orientés39
3.2. Dans les graphes orientés41
Deuxième partie. Caractérisation des contraintes de partitionnement de graphe par des arbres45
Chapitre 4. Contraintes d'arbre dans les graphes non orientés47
4.1. Décomposition47
4.2. Définition des contraintes49
4.3. Algorithme de filtrage pour la contrainte proper-forest52
4.3.1. Existence d'une solution pour la contrainte proper-forest53
4.3.2. Consistance-hybride pour la contrainte proper-forest54
4.3.3. Correction et complétude55
4.3.4. Complexité58
4.4. Algorithme de filtrage pour la contrainte resource-forest62
4.4.1. Existence d'une solution pour la contrainte resource-forest62
4.4.2. Consistance-hybride pour la contrainte resource-forest64
4.4.3. Correction et complétude64
4.4.4. Complexité68
4.5. Synthèse sur les contraintes d'arbres dans le cas non orienté69
Chapitre 5. Contraintes d'arbre dans les graphes orientés71
5.1. Décomposition71
5.2. Définition des contraintes73
5.3. Algorithme de filtrage pour la contrainte tree75
5.3.1. Existence d'une solution pour une contrainte tree75
5.3.2. Arc-consistance généralisée pour la contrainte tree77
5.3.3. Correction et complétude78
5.3.4. Complexité80
5.4. Algorithme de filtrage pour la contrainte proper-tree81
5.4.1. Bornes sur le nombre d'arbres propres83
5.4.2. Existence d'une solution pour la contrainte proper-tree86
5.4.3. Algorithme de filtrage pour la contrainte proper-tree86
5.4.4. Correction90
5.4.5. Complexité92
5.5. Synthèse sur les contraintes d'arbre dans les cas orientés et non orientés92
Chapitre 6. Contraintes additionnelles liées au partitionnement de graphe95
6.1. Définition des restrictions96
6.2. Zoo de la complexité100
6.2.1. Les arbres propres100
6.2.2. Les contraintes de précédence100
6.2.3. Les contraintes de précédence conditionnelle102
6.2.4. Les contraintes sur le demi-degré intérieur des sommets103
6.2.5. Les contraintes d'incomparabilité103
6.3. Interaction entre le nombre d'arbres et le nombre d'arbres propres104
6.4. Relation de précédence entre les sommets du graphe105
6.4.1. Limitations du nombre maximum d'arbres105
6.4.2. Filtrage lié à un ensemble de contrainte de précédence106
6.4.3. Algorithme de filtrage et complexité107
6.5. Relation de précédence conditionnelle110
6.5.1. Filtrage lié à un ensemble de précédence conditionnelle110
6.5.2. Algorithmique et complexité111
6.6. Relation d'incomparabilité entre les sommets du graphe112
6.6.1. Filtrage lié aux contraintes d'incomparabilité112
6.6.2. Algorithme de filtrage et complexité113
6.7. Interactions entre contraintes de précédence et d'incomparabilité113
6.7.1. Amélioration du filtrage via les interactions114
6.7.2. Déduction de nouvelles contraintes de précédence116
6.8. Contraindre le demi-degré intérieur de chaque sommet117
6.9. Synthèse119
Chapitre 7. Le cas des chemins disjoints121
7.1. Nombre minimum de chemins dans les graphes orientés acycliques123
7.2. Nombre minimum de chemins dans les graphes orientés quelconques127
7.2.1. Estimer le nombre de chemins partitionnant une CFC129
7.2.2. Estimer le nombre de chemins entre deux CFC131
7.3. Une contrainte de partitionnement par des chemins133
7.4. Synthèse135
Chapitre 8. Implémentation d'une contrainte d'arbre137
8.1. Implémentation originale138
8.1.1. La contrainte tree138
8.1.2. La contrainte extended-tree140
8.1.3. Les limites de l'approche : illustration avec la contrainte tree141
8.2. Vers une implémentation « portable »142
8.2.1. Mise en oeuvre143
8.2.2. Expérimentations144
8.2.2.1. Implémentation historique versus implémentation adaptable144
8.2.2.2. Evaluation de la portabilité147
8.3. Conclusion148
Troisième partie. Mise en oeuvre : la planification de mission151
Chapitre 9. Premier modèle en programmation par contraintes155
9.1. Modélisation de la cohérence des déplacements dans l'espace155
9.2. Modélisation de la consommation de ressources156
9.3. Modélisation des fenêtres de temps156
9.4. Modéliser les contraintes de coordination entre les unités157
9.5. Limite du modèle proposé158
Chapitre 10. Modèle avancé en programmation par contraintes159
10.1. Modélisation de la cohérence des déplacements dans l'espace159
10.2. Modélisation de la consommation de ressources161
10.3. Intégration des aspects temporels dans la contrainte extended-tree162
10.4. Propager l'information relative aux fenêtres de temps165
10.4.1. Interaction avec le graphe à partitionner165
10.4.2. Interaction avec le graphe de précédence167
10.4.3. Dériver des chemins impossibles169
10.4.4. Interaction avec la contrainte d'arbre originale170
10.4.5. Complexité170
10.4.6. Intégration dans le modèle de planification de missions172
Quatrième partie. Conclusion et perspectives175
Chapitre 11. Conclusion177
Chapitre 12. Perspectives et interrogations179
Bibliographie181
Index185