Contraintes globales de partitionnement de graphe par des arbres

Xavier Lorca

Description

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.

Sujets

• Informatique
• Théorie

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 14 février 2011
• Nombre de lectures: 12
• EAN13: 9782746241541
• Langue: Français
• Poids de l'ouvrage: 4 Mo

Extrait

Contraintes globales de partitionnement de graphe par des arbres

© LAVOISIER, 2011 LAVOISIER 11, rue Lavoisier 75008 Paris www.hermes-science.com www.lavoisier.fr ISBN 978-2-7462-3129-0 ISSN 1957- 9349 Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part, que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété intellectuelle. Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins d’identification et sont des marques de leurs détenteurs respectifs. Printed and bound in England by Antony Rowe Ltd, Chippenham, February 2011.

Contraintes globales de partitionnement de graphe par des arbres Xavier Lorca

Direction éditoriale Jean-Charles Pomerol C OLLECTION P ROGRAMMATION PAR CONTRAINTES SOUS LA DIRECTION DE N ARENDRA J USSIEN Dé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

P REMIÈRE PARTIE . P ROGRAMMATION PAR CONTRAINTES ET BASES DE LA THÉORIE DES GRAPHES . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 1. Introduction à la programmation par contraintes. . . . . . . .

1.1. Qu’estce qu’une variable ? . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Qu’estce qu’une contrainte ? . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Qu’estce qu’une contrainte globale ? . . . . . . . . . . . . . . . . . . . 1.4. Qu’estce qu’un algorithme de propagation ? . . . . . . . . . . . . . . . 1.5. Qu’estce qu’un niveau de consistance ? . . . . . . . . . . . . . . . . . . 1.6. Qu’estce qu’un solveur de contraintes ? . . . . . . . . . . . . . . . . . 1.7. Utilisation d’un solveur de contraintes . . . . . . . . . . . . . . . . . . . 1.7.1. De l’importance de la modélisation . . . . . . . . . . . . . . . . . 1.7.2. De l’importance des heuristiques guidant la recherche . . . . . . . 1.7.3. De l’importance de l’utilisation des contraintes globales . . . . . 1.8. Organisation de l’ouvrage . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . .

3.1. Dans les graphes non orientés . . . . . . . . . . . . . . . . . . . . . . . 3.2. Dans les graphes orientés . . . . . . . . . . . . . . . . . . . . . . . . . .

9

13

14 15 16 17 19 19 21 21 23 24 25

27

28 28 30 34 35 37

39

39 41

6

Partitionnement de graphe par des arbres

D EUXIÈME PARTIE . C ARACTÉRISATION DES CONTRAINTES DE PARTI  TIONNEMENT DE GRAPHE PAR DES ARBRES . . . . . . . . . . . . . . . . .

Chapitre 4. Contraintes d’arbre dans les graphes non orientés. . . . . . . 4.1. Décomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. Définition des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Algorithme de filtrage pour la contrainteproperforest. . . . . . . . . 4.3.1. Existence d’une solution pour la contrainteproperforest. . . . . 4.3.2. Consistancehybride pour la contrainteproperforest. . . . . . . 4.3.3. Correction et complétude . . . . . . . . . . . . . . . . . . . . . . . 4.3.4. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. Algorithme de filtrage pour la contrainteresourceforest. . . . . . . . 4.4.1. Existence d’une solution pour la contrainteresourceforest. . . . 4.4.2. Consistancehybride pour la contrainteresourceforest. . . . . . 4.4.3. Correction et complétude . . . . . . . . . . . . . . . . . . . . . . . 4.4.4. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5. Synthèse sur les contraintes d’arbres dans le cas non orienté . . . . . .

Chapitre 5. Contraintes d’arbre dans les graphes orientés. . . . . . . . . . 5.1. Décomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Définition des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Algorithme de filtrage pour la contraintetree. . . . . . . . . . . . . . . 5.3.1. Existence d’une solution pour une contraintetree. . . . . . . . . 5.3.2. Arcconsistance généralisée pour la contraintetree. . . . . . . . 5.3.3. Correction et complétude . . . . . . . . . . . . . . . . . . . . . . . 5.3.4. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Algorithme de filtrage pour la contraintepropertree. . . . . . . . . . 5.4.1. Bornes sur le nombre d’arbres propres . . . . . . . . . . . . . . . 5.4.2. Existence d’une solution pour la contraintepropertree. . . . . . 5.4.3. Algorithme de filtrage pour la contraintepropertree. . . . . . . 5.4.4. Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.5. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5. Synthèse sur les contraintes d’arbre dans les cas orientés et non orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapitre 6. Contraintes additionnelles liées au partitionnement de graphe . 6.1. Définition des restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Zoo de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1. Les arbres propres . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2. Les contraintes de précédence . . . . . . . . . . . . . . . . . . . . 6.2.3. Les contraintes de précédence conditionnelle . . . . . . . . . . . . 6.2.4. Les contraintes sur le demidegré intérieur des sommets . . . . . 6.2.5. Les contraintes d’incomparabilité . . . . . . . . . . . . . . . . . .

45

47 47 49 52 53 54 55 58 62 62 64 64 68 69

71 71 73 75 75 77 78 80 81 83 86 86 90 92

92 95 96 100 100 100 102 103 103

Table des matières

6.3. Interaction entre le nombre d’arbres et le nombre d’arbres propres . . . 6.4. Relation de précédence entre les sommets du graphe . . . . . . . . . . 6.4.1. Limitations du nombre maximum d’arbres . . . . . . . . . . . . . 6.4.2. Filtrage lié à un ensemble de contrainte de précédence . . . . . . 6.4.3. Algorithme de filtrage et complexité . . . . . . . . . . . . . . . . . 6.5. Relation de précédence conditionnelle . . . . . . . . . . . . . . . . . . . 6.5.1. Filtrage lié à un ensemble de précédence conditionnelle . . . . . . 6.5.2. Algorithmique et complexité . . . . . . . . . . . . . . . . . . . . . 6.6. Relation d’incomparabilité entre les sommets du graphe . . . . . . . . 6.6.1. Filtrage lié aux contraintes d’incomparabilité . . . . . . . . . . . . 6.6.2. Algorithme de filtrage et complexité . . . . . . . . . . . . . . . . . 6.7. Interactions entre contraintes de précédence et d’incomparabilité . . . 6.7.1. Amélioration du filtragevia. . . . . . . . . . . .les interactions 6.7.2. Déduction de nouvelles contraintes de précédence . . . . . . . . . 6.8. Contraindre le demidegré intérieur de chaque sommet . . . . . . . . . 6.9. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 7. Le cas des chemins disjoints. . . . . . . . . . . . . . . . . . . . . 7.1. Nombre minimum de chemins dans les graphes orientés acycliques . . 7.2. Nombre minimum de chemins dans les graphes orientés quelconques . 7.2.1. Estimer le nombre de chemins partitionnant uneCFC. . . . . . . 7.2.2. Estimer le nombre de chemins entre deuxCFC. . . . . . . . . . . 7.3. Une contrainte de partitionnement par des chemins . . . . . . . . . . . 7.4. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 8. Implémentation d’une contrainte d’arbre. . . . . . . . . . . . 8.1. Implémentation originale . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1. La contraintetree. . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.2. La contrainteextendedtree. . . . . . . . . . . . . . . . . . . . . . 8.1.3. Les limites de l’approche : illustration avec la contraintetree. . . 8.2. Vers une implémentation « portable » . . . . . . . . . . . . . . . . . . . 8.2.1. Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2. Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2.1. Implémentation historiqueversusimplémentation adaptable. 8.2.2.2. Evaluation de la portabilité . . . . . . . . . . . . . . . . . . . 8.3. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

T ROISIÈME PARTIE . M ISE 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 . . . . . . . . . . . . .

7

104 105 105 106 107 110 110 111 112 112 113 113 114 116 117 119

121 123 127 129 131 133 135

137 138 138 140 141 142 143 144 144 147 148

151

155 155 156

159 159 161 162 165 165 167 169 170 170 172

Chapitre 10. Modèle avancé en programmation par contraintes. . . . . . 10.1. Modélisation de la cohérence des déplacements dans l’espace . . . . 10.2. Modélisation de la consommation de ressources . . . . . . . . . . . . 10.3. Intégration des aspects temporels dans la contrainteextendedtree. . 10.4. Propager l’information relative aux fenêtres de temps . . . . . . . . . 10.4.1. Interaction avec le graphe à partitionner . . . . . . . . . . . . . . 10.4.2. Interaction avec le graphe de précédence . . . . . . . . . . . . . 10.4.3. Dériver des chemins impossibles . . . . . . . . . . . . . . . . . . 10.4.4. Interaction avec la contrainte d’arbre originale . . . . . . . . . . 10.4.5. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.4.6. Intégration dans le modèle de planification de missions . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapitre 11. Conclusion

Chapitre 12. Perspectives et interrogations

177

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Bibliographie

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Partitionnement de graphe par des arbres

181

185

9.3. Modélisation des fenêtres de temps . . . . . . . . . . . . . . . . . . . . 9.4. Modéliser les contraintes de coordination entre les unités . . . . . . . . 9.5. Limite du modèle proposé . . . . . . . . . . . . . . . . . . . . . . . . .

179

. . . . . . . . . . . . . . . . . . .

175

. . . . . . . . . . .

Q UATRIÈME PARTIE . C ONCLUSION ET PERSPECTIVES

156 157 158