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 liés au partitionnement 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. PROGRAMMATION PAR CONTRAINTES ET BASES DE LA THÉORIE DES GRAPHES. Chapitre 1. Introduction à la programmation par contraintes. Chapitre 2. Théorie des graphes et programmation par contraintes. Chapitre 3. Partitionnement de graphe par des arbres. CARACTÉRISATION DES CONTRAINTES DE PARTITIONNEMENT DE GRAPHE PAR DES ARBRES. Chapitre 4. Contraintes d'arbre dans les graphes non orientés. Chapitre 5. Contraintes d'arbre dans les graphes orientés. Chapitre 6. Contraintes additionnelles liées au partitionnement de graphe. Chapitre 7. Le cas des chemins disjoints. Chapitre 8. Implémentation d'une contrainte d'arbre. MISE EN ŒUVRE : LA PLANIFICATION DE MISSION. Chapitre 9. Premier modèle en programmation par contraintes. Chapitre 10. Modèle avancé en programmation par contraintes. CONCLUSION ET PERSPECTIVES. Chapitre 11. Conclusion. Chapitre 12. Perspectives et interrogations. Bibliographie. Index.
Contraintes globales de partitionnement de graphe par des arbres Xavier Lorca
Direction éditoriale Jean-Charles Pomerol COLLECTIONPROGRAMMATION PAR CONTRAINTESSOUS LA DIRECTION DENARENDRAJUSSIENDécompositions combinatoires et applications industrielles,Thierry Benoist, 2007. Problème SAT : progrès et défis, Lakhdar Saïs, 2008. Optimisation par colonies de fourmis,Christine Solnon, 2008
Table des matières
PREMIÈRE PARTIE. PROGRAMMATION PAR CONTRAINTES ET BASES DE LA THÉORIE DES GRAPHES. . . . . . . . . . . . . . . . . . . . . . . . . .
Chapitre 1. Introduction à la programmation par contraintes. . . . . . . .
Chapitre 2. Théorie des graphes et programmation par contraintes
. . . .
2.1. Modéliser des graphes avec la programmation par contraintes . . . . . 2.1.1. Représenter une famille de graphes . . . . . . . . . . . . . . . . . 2.1.2. Définitions et propriétés de graphes utiles . . . . . . . . . . . . . . 2.1.3. Implémentation des graphes et complexité . . . . . . . . . . . . . 2.2. La théorie des graphes au service de la programmation par contraintes. 2.3. La programmation par contraintes au service de la théorie des graphes.
Chapitre 3. Partitionnement de graphe par des arbres
TROISIÈME PARTIE. MISE EN ŒUVRE:LA PLANIFICATION DE MISSION.
Chapitre 9. Premier modèle en programmation par contraintes. . . . . . 9.1. Modélisation de la cohérence des déplacements dans l’espace . . . . . 9.2. Modélisation de la consommation de ressources . . . . . . . . . . . . .