CM4 B

Question 1

Quelles idées peut-on appliquer pour optimiser la résolution des CSP ?

Answer 1

• Les CSPs dynamiques
• Le maxCSP
• Les soft CSPs ou COPs
• Les réseaux à fonction de coût

Question 2

Qu’est-ce qu’un CSP dynamique ?

Answer 2

Un CSP dans lequel on partitionne les contraintes en C_H les contraintes dures et C_S les contraintres molles, et on construit une suite de réseaux N₁, N₂, … récursivement avec N₀ = C_H et N_i>0 = N_i-1 + {c ∈ C_S\N_i-1 qu’on résout au fur et à mesure jusqu’à trouver le premier réseau insatisfiable, pour renvoyer la solution précédente

Question 3

Qu’est-ce qu’un maxCSP ?

Answer 3

• Instance : N = (X, D, C) un réseau
• Problème : Trouver l’instanciation I qui satisfait le nombre maximum de contraintes (indépendamment de leur nature molle ou dure)

Question 4

Qu’est-ce qu’un soft CSP (ou COP) ?

Answer 4

Un CSP dans lequel, pour chaque contrainte molle c_j(X₁, …, X_k), on remplace celle-ci par soft-c_j(X₁, …, X_k, Y_j) où Y_j est le coût de pénalisation associé à l’affectation (X₁, …, X_k) (plutôt que respecter les contraintes molles, on peut les pénaliser)

Question 5

Comment résoudre un soft CSP (ou COP) ?

Answer 5

Les soft CSPs peuvent être résolus avec les solveurs CSPs classiques, il suffit pour cela de leur rajouter la contrainte supplémentaire suivant : (Σ_j y_j) < UB, c’est à dire que les coûts de pénalité ne doivent pas dépasser une certaine valeur

Question 6

Qu’est-ce qu’un réseau à fonction de coût ?

Answer 6

• Instance : Un réseau (X, D, F, k) tel que ∀ f ∈ F, f est définie sur portée(f) → 0..k et calcule le coût de pénalité associé aux affectations des variables de sa portée
• Problème : Trouver une affectation I des variables de X tel que ⊕_{f ∈ F} f(I[portée(f)]) est minimal et strictement inférieur à k, où a ⊕ b = min(a + b, k)

Question 7

Qu’est-ce qu’un modèle dual ?

Answer 7

Un modèle dans lequel les variables ne représentent pas qu’un type d’information : on peut avoir des contraintes pour un type X (étudiant) et pout un type Y (projet), et il suffit de rajouter de contraintes de “channeling” pour faire corresponre les valeurs données (un étuiant est assigné à un projet si et seulement si le projet est attribué à l’étudiant)