!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> ADRIA/CSPconfig

Deux benchmarks pour les problemes de configuration



Vous trouverez ici deux problemes de configuration "Megane" et "Master" fournis par Renault DICS/SICG.

Ils sont exprimes sous differentes formes

Le problème de la Mégane contient 101 variables de domaines de taille 2 a 43 et 856 contraintes. Le problème du Master contient 158 variables de domaines de taille 2 à plus d'une centaine de valeurs, et 195 contraintes. En configuration,le probleme n'est pas de resoudre automatiquement CSP, qui possede generalement de tres nombreuses solutions, mais d'aider l'utilisateur à le resoudre, par exemple en proposer des mecanismes de propagation assurant efficacement une bonne approximation de la consistance globale. Une description détaillée du benmark "Master" se trouve ici

CSP avec contraintes a tupples:

Syntaxe:

Exemple:Voici une contrainte entre les variables 5 et 82

Remarque: Le fichier ou sont decrites les 856 contraintes originales etant beaucoup trop volumineux si la description est une enumeration de tuples autorises, nous presentons ici un probleme equivalent ou les contraintes portant sur les meme varaibles ou sur des ensembles de variables inclus les uns dans les autres ont ete fusionnees, ce qui ramene a 112 contraintes.

CSP exprimes par des fonctions c.

Syntaxe: les domaines sont decrits par des type enumeres C. Les 856 contraintes sont ensuite decrites par des fonctions c a valeur dans {0,1} : elle rendent 1 si la contrainte est satisfaite par les arguments de la fonction, 0 sinon.

Exemple:

enum DX5 {FRAN, NORV, FIN, DANE, ALLE, JAPO, SUED};

enum DX72 {ODIN, FUJI, KANG, SSEDNC};

int funcCRIT1(Enum DX5 i5, Enum DX72 i72) {

return ((i72 == ODIN) == ( ( i5 == FIN) | (i5 == NORV) | (i5 == DANE) | (i5 == SUED)));

}

Deux domaines sont declares, DX5 (pour la variable 5 du CSP) et DX72 (pour la variable 72 du CSP).

La fonction funcCRIT1 code la contrainte CRIT1 entre les variables 5 et 72. Elle prend donc en argument un element de DX5 et un element de DX72. Elle rend la valeur 1 si CRIT1 est satisfaite, 0 sinon; par exemple, elle rend 1 pour le couple (ODIN, NORV) et 0 pour le couple (ODIN, FRAN).

Logique propositionnelle

Syntaxe: C'est une syntaxe de type logique propositionnelle, une formule etant construite:

Le fichier commence par 101 formules particulieres nommees lex1 a lex101 qui indiquent chacune une liste de literaux dont un seul doit prendre la valeur true (ce sont des clauses d'exclusivite). Ces 101 formules codent en fait la definition des domaines des variables de configuration.

Suivent les 856 formules (GMP1, CRIT1 a CRIT825, VT1, CTR1 a CTR 29). Toutes ces contraintes doivent etre satisfaites, ainsi que les contraintes LEXi.

Bibliographie

[Amilhatre 99] Jerome Amilhastre. Representation par automate d'ensemble de solution de probleme de satisfaction de contraintes. These de Doctorat, Universite  Montpellier II, LIRMM, Janvier 1999.

[Amilhastre et al 2000] Jerome Amilhastre, Helene Fargier, Pierre Marquis. Explications et aide a la restauration de la coherence dans les CSP interactifs: application a la configuration. Dans les actes de JNPC'00, Marseille, 28-30 juin 2000, pp 43-56.

[Vempaty 92] Nageshwara Rao Vempaty. Solving Constraint Satisfaction Problems Using Finite State Automata. Proceedings of the 10th National Conference on Artificial Intelligence, pp. 453-458, MIT Press, July 1992.

Contacter Helene Fargier: fargier@irit.fr ou 05 61 55 82 97

118, Route de Narbonne, 31062 Toulouse Cedex , France