Contraintes globales de partitionnement de graphe par des arbres

Auteur(s) :

Lorca, Xavier Découvrir l'auteur

Résumé

Analyse des problèmes de satisfaction de contraintes dans les partitionnements de graphe par des arbres mettant en jeu un certain nombre de restrictions sur la topologie des partitions. L'étude se focalise sur la compréhension des propriétés structurelles inhérentes aux contraintes de partitionnement par des arbres et sur les interactions entre le partitionnement et les restrictions classiques.

Éditeur(s)
- Hermès science publications-Lavoisier
Date
- impr. 2011
Notes
- Bibliogr. p. 181-184. Index
Langues
- Français
Description matérielle
- 1 vol. (186 p.) : ill. ; 24 cm
Collections
- Collection Programmation par contraintes
Sujet(s)
- Programmation par contraintes
- Graphes de lien
ISBN
- 978-2-7462-3129-0
Indice
- 681.2 Programmation (généralités)
Quatrième de couverture
- Les problèmes combinatoires basés sur le partitionnement de graphe permettent de modéliser un grand nombre d'applications pratiques dans des domaines aussi variés que la planification de missions ou la construction de tournées de véhicules en logistique. Ces applications peuvent toutes être considérées comme un problème de partitionnement de graphe par des patrons tels que des cycles, des chemins ou des arbres.
  Cependant, les problèmes pratiques se résument rarement à des problèmes « purs ». Ils combinent bien souvent le problème de partitionnement avec un ensemble de restrictions sur la topologie des sommets et des arcs. La diversité des contraintes opérationnelles constitue alors une limite à leur résolution par des approches séparant le partitionnement des restrictions supplémentaires.
  Cet ouvrage analyse les problèmes de satisfaction de contraintes dans les partitionnements de graphe par des arbres mettant en jeu un certain nombre de restrictions sur la topologie des partitions. L'étude se focalise d'une part sur la compréhension des propriétés structurelles inhérentes aux contraintes de partitionnement par des arbres et d'autre part sur les interactions entre le partitionnement et les restrictions classiques telles que les relations de précédences ou d'incomparabilités.
Tables des matières
- - 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
Origine de la notice:
- FR-751131015