CM3 B

Question 1

Qu’est-ce qu’une contrainte globale ?

Answer 1

Une classe de contraintes définie par une fonction booléenne qui prend un nombre non-borné de variables

Question 2

À quoi servent les contraintes globales ?

Answer 2

À exprimer de façon compacte certaines propriétés d’un problème

Question 3

Peut-on utiliser l’algorithme classique d’arc-cohérence sur un réseau avec des contraintes globables ?

Answer 3

Oui, mais leur complexité est O(dⁿ) avec n = |X| et d = max(|D(x_i)|

Question 4

Comment faire de la propagation sur les contraintes globables de façon efficace ?

Answer 4

En utilisant des propagateurs ad hoc spécifiques aux contraintes

Question 5

Quel problème pose l’idée d’utiliser des propagateurs ad hoc ?

Answer 5

Il y a plus de 400 contraintes globales, donc on ne peut pas faire un propagateur pour chacune d’elles

Question 6

Pourquoi faire de la décomposition sur les contraintes globales ?

Answer 6

Pour éviter de faire un propagateur ad hoc par contrainte

Question 7

Qu’est-ce qu’une décomposition simple ?

Answer 7

Soit G une contrainte globable et c(X) = (X, D_X, {c}) une instance de celle-ci, la décomposition simple de G est δ_G(c) = (X, D_X, C) où C = {c₁, c₂, …} et tout c_i de C porte sur un nombre limité de variables, et sol(c) = sol(δ_G(c))

Question 8

Qu’est-ce qu’une décomposition ?

Answer 8

Soit G une contrainte globable et c(X) = (X, D_X, {c}) une instance de celle-ci, la décomposition de G est δ_G(c) = (X ∪ Y, D_X + D_Y, C) où
- C = {c₁, c₂, …} et tout c_i de C porte sur un nombre limité de variables
- sol(c) = sol(δ_G(c))[X]
- |Y| + |D_Y| est molynomial en |X| + |D_X|

Question 9

Quand est-ce qu’une décomposition préserve l’arc-cohérence ?

Answer 9

δ_G préserve l’arc-cohérence si et seulement si pour toute instance c(X) = (X, D_X, {c}) de G et tout domaine D’_X ⊆ D_X, D’_AC(c) = D’_AC(δ_G(c))[X]

Question 10

Qu’est-ce qu’une contrainte globable AC-décomposable ?

Answer 10

Une contrainte globable qui a une décomposition qui préserve l’arc-cohérence

Question 11

Exemple de contrainte AC-décomposable

Answer 11

At-Least-p-v(X₁, …, X_n)

Question 12

Exemple de contrainte non AC-décomposable

Answer 12

AllDiff(X₁, …, X_n)

Question 13

Définition du problème checker_G

Answer 13

Soit G une contrainte globale, alors :
- Instance : (X(c), D, {c}) où c est une instance de G
- Question : Est-ce qu’il existe un tuple τ ∈ D^X(c) tel que c(τ) ?

Question 14

Lien entre le problème checker_G et l’arc-cohérence

Answer 14

Si checker_G est NPC, l’arc-cohérence est NP-dure pour G

Question 15

Lien entre le problème checker_G et l’AC-décomposabilité

Answer 15

Si checker_G est NPC, il n’existe pas d’AC-décomposition pour G

Question 16

Que faire pour les contraines non AC-décomposables ?

Answer 16

On peut leur appliquer une cohénrence plus faible : la bound-cohérence

Question 17

Comment obtenir la définition de la boun-cohérence à partir de celle de l’arc-cohérence ?

Answer 17

En relaxant la définition d’un tuple support : dans la BC, un tuple support est τ tel que τ ∈ c(X) ∧ ∀ x_i ∈ X, min(x_i) ≤ τ[x_i] ≤ max(x_i)

Question 18

Qu’est-ce qu’un graphe d’incidence ?

Answer 18

Pour (X, D, C) un réseau, le graphe d’incidence est G_N = (X ∪ C, E) avec E = {(x, c) | c ∈ C, x ∈ portée(c)}

Question 19

Qu’est-ce qu’un réseau Berge-acyclique ?

Answer 19

Un réseau dont le graphe d’incidence est acyclique

Question 20

Que sait-on d’un réseau si celui-ci est Berge-acyclique ?

Answer 20

Toutes les valeurs de son AC-décomposition appartiennent à une solution

Question 21

Lien entre l’AC-décomposabilité et la Berge-acyclicité

Answer 21

Si une décomposition d’une contrainte globable est Berge-acyclique, alors c’est une AC-décomposition

Question 22

Lien entre l’AC-décomposabilité et l’existence d’un circuit monotone booléen

Answer 22

S’il n’existe pas de circuit booléen monotone de taille polynomiale pour une fonction booléenne G, alors il n’existe aucune décomposition en formule normale clausifiée qui calcule l’AC et il n’existe aucune AC-décomposition pour G

Question 23

Qu’est-ce qu’un circuit booléen monotone ?

Answer 23

Un circuit booléen qui n’utilise que des opérateurs ∨et ∧

Question 24

Quels sont les trois cas possibles pour les contraintes globables vis-à-vis de l’AC-décomposition ?

Answer 24

• L’AC peut être NP-dure sur la contrainte, il faut alors appliquer une cohérence plus faible (BC)
• L’AC peut être AC-décomposable, il faut alors décomposer
• Si la contrainte n’est dans aucun des deux cas (il est polynomial d’appliquer AC, mais il n’y a pas d’AC-décomposition), il faut construire un algorithme ad hoc

Question 25

Comment appliquer l’AC sur AllDifferent (NPC) ?

Answer 25

• Tracer le graphe des valeurs avec une source qui domine les variables et un puits qui domine les valeurs
• Calculer le flow max
• Calculer le graphe résiduel
• Calculer les composantes fortement connexes des deux graphes superposés
• Supprimer les arêtes isolées et les valeurs associées dans les domaines

Question 26

Quand est-ce que les solveurs SAT ne peuvent pas simuler les solveurs CP ?

Answer 26

Lorsqu’il y a des contraintes non-décomposables