# Modélisation par contraintes et exploitation d'une gamme automobile : nouveaux problèmes, nouvelles requêtes, nouveaux besoins en programmation par contraintes

Jeam-Marc Astesana, Laurent Cosserat, Hélène Fargier

► To cite this version:

Jeam-Marc Astesana, Laurent Cosserat, Hélène Fargier. Modélisation par contraintes et exploitation d'une gamme automobile : nouveaux problèmes, nouvelles requêtes, nouveaux besoins en programmation par contraintes. 6èmes Journées Francophones de Programmation par Contraintes (JFPC 2010), Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC), Jun 2010, Caen, France. pp.33-42. inria-00520306

HAL Id: inria-00520306

https://inria.hal.science/inria-00520306v1

Submitted on 22 Sep 2010

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Modélisation par contraintes et exploitation d'une gamme automobile : nouveaux problèmes, nouvelles requêtes, nouveaux besoins en programmation par contraintes

Jean Marc Astesana¹ Laurent Cosserat¹ Hélène Fargier²

¹ Renault SA, 13 avenue Paul Langevin 92359 Plessis Robinson

² IRIT-CNRS, 118 route de Narbonne 31062 Toulouse Cedex 9

{jean-marc.astesana,laurent.cosserat}@renault.com fargier@irit.fr

## Abstract

La mise au point et l'exploitation de la gamme commerciale d'un constructeur automobile présentent de multiples problèmes métier qui peuvent se modéliser comme des problèmes CSP : détection et analyse d'incohérence dans la spécification de la gamme, configuration véhicule, configuration de la prévision. Ces problèmes mettent en jeu des données de taille importante, et leur résolution en situation réelle doit être effectuée dans un temps de calcul limité. Cet article présente, formalise et étudie la complexité de plusieurs de ces problèmes. Au-delà de l'étude d'une application réelle, son objectif est de proposer à la communauté CSP non pas de nouvelles approches de résolution, mais de nouvelles requêtes, de nouveaux problèmes, voire de nouveaux besoins.

## 1 Introduction

Le formalisme des problèmes de satisfaction de contraintes (CSP) offre un cadre de formalisation puisant pour l'expression d'une multitude de problèmes, en particulier de nombreux problèmes académiques ou issus du monde réel (par exemple les problèmes de corloration de graphes, d'ordonnancement, d'affectation de fréquence, ...). Résoudre un CSP c'est, quasiment toujours, déterminer s'il est cohérent et/ou lui trouver une solution -dans certains cas une solution optimale- et c'est une question difficile : le problème de décision associé est NP-complet. La grande majorité des travaux de la communauté a donc porté sur ce problème, soit en l'abordant de front (proposer les algorithmes les plus efficaces possibles pour déterminer la cohérence d'un CSP), soit en cherchant comment le contourner,

par l'étude de sous-classes qui seraient polynomiales ou par la définition d'algorithmes sains mais incomplets.

Or si les CSP, ou les langages de programmation par contraintes, sont largement utilisés, ce n'est pas seulement parce qu'ils sont munis d'algorithmes de résolution efficaces. C'est aussi parce qu'ils permettent d'exprimer simplement les données des applications modélisées. Mais dans ces applications, la question n'est pas toujours de savoir si le CSP est cohérent ni même d'en trouver une solution. Les applications en configuration de produit, par exemple, définissent des CSP cohérents (pourvus de centaines de milliers de solutions) ... et la machine n'est pas utilisée pour extraire une solution, mais pour aider l'utilisateur à construire la sienne.

L'ambition de cet exposé est de proposer à la communauté non pas de nouvelles approches de résolution, mais de nouvelles requêtes, de nouveaux problèmes, voire de nouveaux besoin en modélisation, en exposant quelques problèmes métier de Renault qui ont pour point commun la nécessité d'inférer sur le système de contraintes représentant la gamme, et notamment la configuration de véhicules automobiles.

## 2 Modélisation à base de contraintes de la gamme Renault

La gamme de véhicules de Renault est très étendue. Le nombre de véhicules différents dans la gamme d'un modèle peut être énorme. Par exemple, l'ensemble des petites fourgonnettes "Trafic" comprend $10^{21}$ véhicules différents. Ce nombre rend impossible l'énumération de l'ensemble de ces véhicules dans une base
de données. Cet ensemble doit alors être représenté en intention. La gamme peut être vue comme spéciifiée par modèle, et dans la suite de cet article on entend par "gamme" l'ensemble de toutes les différentes variantes possibles d'un modèle. Les véhicules sont définis par des variables (carburant, couleur, etc.) qui prennent des valeurs dans des domaines énumérés ({{essence, diesel, gpl}, {blanc, noir, rouge}, etc.). Les choix possibles pour ces variables ne sont pas indépendants les uns des autres (typiquement, un niveau d'équipement donné n'est pas disponible sur toutes les motorisations) : des dépendances sont modélisées par un système de contraintes entre ces variables. On a ainsi tous les ingrédients d'un problème CSP, dont chaque solution définit un véhicule précis de la gamme.

Plusieurs travaux ont proposé d'utiliser des extensions des CSP pour formaliser des problèmes de configuration, traitant généralement de difficultés de représentation spécifiques à ces types de problèmes, comme par exemple le fait que l'existence d'une variable puisse dépendre la valeur affectée à une autre. L'étude des problèmes de configuration a ainsi poussé la communauté à étendre le modèle CSP de base, définissant ainsi les CSP dynamiques [8], CSP composites [10], CSP interactifs [7], CSP à hypothèses [1], etc. Dans cet article, nous négligerons la prise en compte de ces difficultés de représentation pour nous tourner plutôt vers les requêtes adressées au modèle, vers la question de l'exploitation des données. On supposera donc que la gamme est représentée par un CSP "classique".

Les notations et définitions précises nécessaires à la formalisation de l'ensemble des questions étudiées ici seront introduites en Section 4. Disons pour l'instant simplement qu'un CSP est un triplet $P = \langle X, D, C \rangle$ où $X$ est l'ensemble de ses variables, $D$ l'ensemble des domaines respectifs de ces variables et $C$ l'ensemble (supposé fini) de ses contraintes; on désignera par $Sols(P)$ l'ensemble des solutions de $P$.

Comme la plupart des instances issues de problèmes réels, les CSP représentant les modèles de la gamme Renault possèdent des spécificités particulières, en termes sémantiques (type de variables et contraintes) et syntaxiques (forme du graphe de contraintes).

La gamme de Renault est construite suivant ce qu'on appelle le "modèle version-options". Selon ce modèle, les variables se répartissent en deux catégories :

- un petit nombre de variables servant à définir les versions : appelons-les variables majeures. Soit $Maj \subset X$ leur ensemble : pour fixer les idées, on peut considérer que la restriction de $Sols(P)$ aux variables de $Maj$ définit l'ensemble des versions de la gamme. Une variable encodant précisément la version peut exister, mais ce n'est pas systématiquement le cas : dans le cas contraire, la notion

de version n'existe qu'implicitement, comme combinaison de valeurs de variables majeures.

- le reste des variables, la grande majorité, dont les valeurs possibles dépendent de la version : ce sont les variables mineures éléments de $Min$. $Maj$ et $Min$ forment une partition de $X$. Une valeur du domaine d'une variable mineure pourra ainsi être impossible sur une version, optionnelle sur une autre et obligatoire sur une troisième.

On peut regrouper comme suit les contraintes de spécification de la gamme :

- Les contraintes majeures portent sur des variables majeures qui définissent l'ensemble des versions. Typiquement, une contrainte majeure est directement définie par une Table, c'est-à-dire par l'énumération explicite des combinaisons autorisées de valeurs des variables de la contrainte.

- Les contraintes options sont des contraintes de la forme $"(x = v) \Rightarrow (y \in A)"$, $x$ étant une variable majeure, $v$ une valeur de son domaine, $y$ une variable mineure, et $A$ un sous-ensemble du domaine de $x$. Par exemple, on peut utiliser ce type de contrainte pour spécifier la liste des auto-radios disponibles sur les versions haut de gamme.

- Les contraintes packs. Il arrive qu'un lot de plusieurs options soit regroupé en une seule : un pack (ces options s'appellent alors les composants du pack). Les packs donnent lieu à de nombreuses contraintes qui complexifient le CSP. Par exemple, la contrainte de définition d'un pack exprime que le choix d'un pack *pack* implique la sélection de la totalité de ses *n* composants $opt_i$ : ($x = pack$) ⇒ $\bigwedge_{i=1}^n (x_i = opt_i)$. De plus, une même option peut être un composant de plusieurs packs, qui s'excluent alors mutuellement.

- Les contraintes quelconques. Il reste des contraintes ne faisant pas partie des catégories précédentes. Elles peuvent inclure des variables majeures et mineures.

Notons que certaine contraintes, comme les contraintes options, s'expriment par des combinaisons booléennes de conditions ($variable = valeur$) ou de conditions ($variable \in sous-domaine$); par exemple la contrainte ($carburant = diesel$) ∧ ($type_boite = boite_auto$) ⇒ ($type_chauffage = clim_regulee$). On parle alors d'expression booléenne<fnref n="1" />.

Dans les paramètres les plus dimensionnant des

<footnote n="1">¹Il est bien entendu possible de modéliser la gamme de manière entièrement booléenne et d'obtenir ainsi des formules de la logique propositionnelle; plusieurs codages sont possibles - voir par ex [13], mais pour des raisons de lisibilité, c'est souvent l'encodage direct qui est utilisé : pour chaque variable *var* qui admet les valeurs possibles *val*₁, ..., *val*ₙ on définit *n* variables booléennes *val*₁, ..., *val*ₙ. Ces variables sont classiquement liées par des contraintes d'exhaustivité et d'exclusivité.</footnote>
problèmes CSP définissant une gamme, on peut citer :

- La combinatoire des variables majeures. En confi-
guration commerciale il y a au plus une centaine
de versions, mais sur des gammes dites techniques,
la projection de Sols(P) sur les variables majeures
peut en comporter plusieurs dizaines de milliers.

- le nombre de variables mineures et majeures. On
peut supposer que $card(Min) \le 150$. Le nombre
de variables majeures est de l'ordre de 10.

La complexité est aggravée par les packs : au pire
on peut en avoir une dizaine, chacun impliquant typi-
quement de 2 à 5 options composantes.

Mais l'essentiel de la difficulté vient des contraintes quelconques. Contrairement aux contraintes options, qui relient les variables de manière essentiellement hiérarchique, ces contraintes peuvent porter sur n'importe quelles variables, et donc complexifier le graphe de contraintes. Il peut y en avoir jusqu'à une centaine : elles portent généralement sur moins de quatre variables (sur deux variables dans la moitié des cas).

3 Exploitation de la gamme

Nous décrivons maintenant les requêtes métier qui
se posent chez Renault lors des tâches d'élaboration,
la maintenance et l'exploitation d'une gamme de véhi-
cules - dit autrement, lors de la définition, la modifi-
cation ou l'exploitation de ce CSP. Leur formalisation
en termes de CSP sera abordée en Section 4.

## 3.1 Élaboration de la documentation véhicule

Les premières tâches interviennent en amont du pro-
blème de configuration client, en phase de modélisa-
tion de la gamme par un système de contraintes. On
parle d'élaboration de la "documentation véhicule". Il
s'agit de savoir si la gamme décrite par le système est
cohérente, dans un sens étendu : dans certains cas,
il ne suffit pas qu'il existe des véhicules compatibles
avec les contraintes, il faut aussi que les possibilités
spécifiées par les contraintes soient effectives. Suppo-
sons par exemple qu'une contrainte signifie "Les véhi-
cules ayant le moteur M3 peuvent avoir comme type
de chauffage : climatisation manuelle ou climatisation
régulée." Si d'autres contraintes rendent incompatible
le moteur M3 et la climatisation manuelle, la docu-
mentation véhicule est considérée comme incohérente.
Autrement dit, certaines contraintes de la documen-
tation véhicule ont une double sémantique : négative
(elles interdisent des combinaisons de valeurs), et po-
sitive (les combinaisons autorisées par une contrainte
doivent être effectivement possibles) : nous appelons
cette propriété cohérence positive. C'est le cas des
contraintes majeures et des contraintes options. Les

questions qui se posent sont :

* Cohérence (contextuelle) de la gamme : Y a-t-il au moins un véhicule répondant à cette définition de gamme ? Étant donnée une liste de quelques variables dont on impose la valeur, y a-t-il dans la gamme au moins un véhicule compatible avec cette affectation ? Plus généralement, étant donnée une expression booléenne c portant sur des paires (variable = valeur), y a-t-il dans la gamme au moins un véhicule vérifiant c ?

Lorsque la réponse à ces questions est non, c'est que
la documentation véhicule est erronée dans son état
courant. Il faut alors analyser l'incohérence, c'est-à-
dire déterminer un jeu minimal de contraintes qui suf-
fit à expliquer l'impossibilité des véhicules prévus :

* Conflits : Trouver un ensemble de contraintes in-
cohérent, qui soit minimal pour l'inclusion.

* Conflits contextuels : Étant donnée une liste de variables dont la valeur est imposée, trouver un ensemble de contraintes incohérent avec ces affectations qui soit minimal pour l'inclusion.

* Cohérence positive Pour chaque contrainte à sé-
mantique positive, et chaque tuple qu'elle auto-
rise, existe il un véhicule de la gamme qui réalise
ce tuple. De la même façon, pour chaque variable
et chaque valeur de son domaine, existe-t-il un
véhicule qui affecte cette valeur à cette variable.

3.2 Restitution de la gamme

Lorsque la gamme a été définie de manière cohé-
rente, on cherche à en extraire des données significa-
tives techniquement en considérant des ensembles de
variables {$x_1, ..., x_k$} (généralement, $k \le 6$), et gé-
nérant automatiquement des descriptions synthétiques
des combinaisons des valeurs possibles de ces variables,
typiquement sous la forme d'expressions booléennes
sur des propositions de type *variable = valeur*.

* Validité de description synthétique : Tester si tous les véhicules de la gamme vérifient une description synthétique c donnée.

* Simplification de description synthétique : Une description synthétique c donnée est elle minimale (peut-on, sans supprimer une variable de c sans compromettre sa validité?)

* Génération de description synthétique : Étant donné un ensemble de variables, quelles sont les combinaisons de valeurs pour ces variables qui sont autorisées par la gamme (idéalement, on voudrait générer cette projection sous la forme d'une description synthétique minimale) ?

On cherche enfin à dimensionner la diversité de la
gamme, en termes de nombres de véhicules différents :

* Comptage : Combien de véhicules la gamme
compte-t-elle ? Combien de véhicules ayant un ensemble donné de valeurs imposées la gamme compte-t-elle ? Combien de combinaisons de valeurs différentes sont autorisées pour un sous-ensemble de variables Y : typiquement, on peut vouloir dimensionner la "diversité technique", c'est-à-dire le nombre de véhicules existant dans la gamme, hors considérations de teinte, appellation commerciale et pays de commercialisation.

## 3.3 Élaboration de la documentation pièces

La documentation pièces de Renault spécifie les pièces montées sur les véhicules de la gamme considérée. Elle est distincte de la documentation véhicule, dont les variables représentent des prestations perçues par les clients et non des pièces. Le lien est assuré par ce qu'on appelle le "cas d'emploi": le cas d'emploi d'une pièce $p_i$ est une expression booléenne $c_i$ portant sur des atomes *variable* = *valeur* de la documentation véhicule - cette contrainte spécifie les véhicules sur laquelle la pièce est montée. Par exemple, une pièce se monte sur les véhicules qui ont un moteur essence et une boîte automatique mais pas de toit ouvrant.

Les pièces sont regroupées en "pièces génériques". Une pièce générique, par exemple l'autoradio, est une fonction réalisée par la pièce. Pour que la documentation pièces soit cohérente, il faut que chaque véhicule ait un autoradio (propriété d'exhaustivité), qu'aucun véhicule n'en ait plusieurs (propriété de non-dualité) et que tout autoradio soit utilisé dans au moins un véhicule. On peut voir une pièce générique comme une variable supplémentaire $p$ dont les valeurs sont les pièces associées $p_1, ..., p_n$. A chaque $p_i$ correspond une expression booléenne $c_i$ définissant son cas d'emploi. Les questions qui se posent alors sont :

*Concision de la doc.* : Pour chaque pièce associée (chaque cas d'emploi), existe-t-il au moins un véhicule de la gamme qui le valide ?

*Exhaustivité de la doc.* : Existe-t-il un véhicule ne montant aucune des pièces associées à une pièce générique donnée (ne validant aucun des cas d'emploi de la pièce générique) ?

*Non-dualité des Emplois* : Existe-t-il un véhicule montant deux des pièces, ou plus, associées à une pièce générique donnée (validant au moins deux des cas d'emplois de la pièce générique) ?

Si la réponse est "oui" à l'un des deux derniers points, on veut caractériser ces véhicules ou ces pièces :

*Emplois Inconnus* : Donner une condition sur les atomes "variable = valeur" qui caractérise l'ensemble des véhicules ne montant aucune des pièces associées à une pièce générique donnée ?

*Emplois Multiples* : Quelles sont les ensembles de pièces qui peuvent être montées simultanément

sur un véhicule; pour chaque ensemble, donner une condition sur les atomes "variable = valeur" qui caractérise l'ensemble des véhicules supportant ces pièces simultanément ?

Il peut sembler relativement simple de construire ces conditions caractéristiques en formant des combinaisons logiques à partir des cas d'emplois et des contraintes du CSP, si tant est qu'elles sont exprimées par des conditions logiques. La difficulté est que chaque condition caractéristique recherchée doit être simplifiée (aucune variable ne doit pouvoir en être supprimée sans compromettre l'ensemble qu'elle définit).

## 3.4 Configuration en ligne

Les problèmes liés à la configuration en ligne ont été déjà abordés dans plusieurs articles (voir par exemple [1]). Le principe de la configuration en ligne est que l'utilisateur (un client potentiel) définit le produit qu'il désire en choisissant interactivement des valeurs pour les variables; il peut également revenir en arrière en relâchant un ou plusieurs de ses choix. Après chaque action, les domaines de valeurs possibles fournis à l'utilisateur doivent être modifiés de manière à contenir toutes les valeurs compatibles avec les choix courants, et seulement les valeurs compatibles avec ces choix. L'utilisateur peut forcer le choix d'une valeur détectée comme incompatible : le CSP devient alors incohérent. Quand l'ensemble des choix est incohérent avec les contraintes du CSP, il doit pouvoir revenir sur ses choix précédents et les relâcher.

L'utilisateur doit pouvoir également avoir une idée du prix du véhicule qu'il est en train de construire, et du délai d'obtention. Les informations prix sont décrites par des coûts associés aux valeurs de variables, ou par des fonctions de coût portant sur quelques variables. Le prix d'un véhicule est la somme des prix unitaires. Notons que certains coûts peuvent être négatifs (ce qui correspond à un retrait d'option par rapport au choix "standard"). On peut, en simplifiant, supposer que les informations délai sont portées par des conditions composées sur la gamme et définissant des intervalles de valeurs ("si le moteur choisit est hybride, alors le délai est d'au moins deux mois").

Pour aider l'utilisateur dans sa démarche, le système doit répondre aux requêtes suivantes :

*Cohérence globale* : Assurer, après chaque modification de domaine (choix de valeur ou relaxation) que les domaines correspondent exactement aux valeurs compatibles avec les choix courants.

*Estimation du prix / du délai* : Calculer le prix (ou le délai) min (ou max) des véhicules de la gamme compatibles avec les choix courants.

*Calcul de restauration* : En cas d'incohérence, identifier un ou des sous-ensembles maximaux
cohérents de restrictions utilisateur.

*Calcul de conflit:* Identifier des sous-ensembles minimaux de choix utilisateur incohérents, ou incohérents avec des choix de valeur de variable.

*Simulation des choix:* Déterminer quel serait l'état des domaines si l'utilisateur choisissait telle valeur pour telle variable (ce qui revient à la première requête, la cohérence globale).

*Complétion de la configuration:* Lorsqu'un certain nombre de variables "obligatoires" ont été renseignées, complétion automatique de la complétation courante à la demande de l'utilisateur (éventuellement sur un critère de minimisation de prix ou de délai).

## 3.5 Probabilisation de la gamme

La spécification de la gamme permet également à l'entreprise de construire des prévisions sur les ventes - typiquement, pour dimensionner sa production et celle de ses fournisseurs. Pour un modèle, ces prévisions sont équivalentes à la donnée d'un volume global et de probabilités (des taux prévisionnels) sur les valeurs de variables, conditionnées éventuellement par un contexte. ("On prévoit le choix de sièges en cuir dans 30% des véhicules vendus", "En Pologne, 25% des véhicules vendus seront diesel"). Ces probabilités individuelles sont en principe les projections d'une distribution de probabilité jointe sur la gamme. Cette démarche - construire une telle distribution à partir de taux - est appelée probabilisation de la gamme.

Cette distribution n'est pas connue, mais elle est spécifiée partiellement par la donnée de certaines de ses projections sur des variables (on parle de distributions marginales) et par la définition de la gamme. Il est possible qu'elle soit sur-spécifiée, c'est-à-dire qu'il n'existe aucune distribution de probabilité sur la gamme dont les marginales correspondent aux taux renseignés, ceci à cause des contraintes définissant la gamme. Dans le cas contraire, elle est généralement sous-spécifiée : plusieurs distributions jointes différentes peuvent produire les mêmes marginales. Dans ce cas la probabilité d'un véhicule n'est pas connue avec précision, mais l'on peut en connaître la plus petite et la plus grande valeurs possibles. De la même façon, plusieurs distributions peuvent être envisagées pour les marginales (pour les taux) non renseignées. Les requêtes en rapport avec la probabilisation de la gamme sont :

*Cohérence des taux:* Les taux sont-ils cohérents (existe-t-il une distribution de probabilité sur la gamme dont les marginales sont précisément les taux renseignés) ?

*Taux conflictuels:* Si les taux sont incohérents, en exhiber un sous-ensemble (minimal) incohérent modulo la définition de la gamme.

*Configuration des taux:* Si les taux sont cohérents, calculer une borne min et une borne max de la probabilité de l'affectation d'une valeur à une variable de véhicule. Utilisé itérativement avec la définition de taux, ce mécanisme permet de confirmer progressivement un jeu de taux qui reste cohérent à toutes les étapes de la construction.

*Extrapolation de taux:* Si les taux sont cohérents, calculer une borne min et une borne max de la probabilité d'une expression booléenne sur des affectations - typiquement, sur des cas d'emploi. Ce calcul permet notamment d'encadrer les volumes prévisionnels de pièces.

*Génération d'échantillon:* Les taux étant cohérents, générer un échantillon de $n$ véhicules conformément à la distribution de probabilité sous-jacente ; si elle est sous-spécifiée, on peut se baser sur la distribution d'entropie maximale. Cet échantillon sera utilisé comme une commande prévisionnelle par d'autres logiciels (simulation de la production, calcul de prix de revient, etc.).

## 3.6 Temps de réponse

Pour les applications interactives (typiquement, la configuration en ligne) le temps de réponse doit être (au pire) de l'ordre de la seconde. Les applications hors ligne, elles, peuvent compter leur temps de calcul en heures. Mais si elles ont un grand nombre de requêtes à effectuer, cela signifie que chaque requête devra également prendre un temps réduit (entre la milliseconde et la seconde, suivant les cas). Cependant, il reste possible de consacrer un temps beaucoup plus élevé (par exemple se comptant en minutes) pour les requêtes les plus difficiles, tant que cela ne modifie pas l'ordre de grandeur du temps de calcul total. C'est cette logique qui prévaut pour les contrôles de cohérence de la documentation véhicule et de la documentation pièces.

# 4 Formalisation des requêtes ; complexité

Nous étudions ici comment les requêtes présentées en Section 3 peuvent être formalisées en termes de CSP, et présentons nos premiers résultats quant à leur complexité théorique.

## 4.1 Notations et définitions

**CSP** Un CSP est, on l'a vu, un triplet $P =< X, D, C >$. Pour toute variable $x$ de $X$, $D(x)$ est le domaine (supposé fini) de $x$. Pour toute contrainte $c$ de $C$, on note $vars(c)$ l'ensemble des variables dont elle restreint les valeurs.

Une affectation $d$ est une fonction qui associe à chaque $x \in X$ une valeur de son domaine ou le sym-
bole *, qui indique que la variable n'a pas été affectée. *d* est complète (resp. partielle) si le symbole * n'est pas (resp. est) présent. Plus largement, on dit que *d* affecte $Y \subseteq X$ (resp. $c$) ssi pour tout $x \in Y$ (resp. pour tout $x \in \text{vars}(c)$), $d(x) \neq *$. $D(Y) = \{d, \forall x, d(x) = * \Leftrightarrow x \notin Y\}$ est l'ensemble des affectations de $Y \subseteq X$. Enfin, on note $\text{vars}(d)$ les variables affectées dans $d$, et on dit que $d'$ étend $d$ (à $\text{vars}(d')$) ssi $\text{var}(d) \subseteq \text{vars}(d')$ et $\forall x \in \text{vars}(d), d(x) = d'(x)$; ceci est noté $d' \models d$.

Une contrainte peut être vue comme une fonction $c$ de l'ensemble des affectations de $\text{vars}(c)$ dans $\{\top, \bot\}$ : $c(d) = \top$ ssi $d$ satisfait la contrainte. On ne fait pas d'hypothèse sur la manière dont sont représentées les contraintes, mais on suppose que, pour toute affectation $d$ affectant (au moins) toutes les variables de $c$, on peut tester en temps polynômial (idéalement, linéaire) si $d$ satisfait $c$ (noté $d \models c$) ou la viole (noté $d \not\models c$). Une solution d'un CSP est une affectation complète de ses variables qui satisfait toutes ses contraintes. On note $\text{Sols}(P)$ l'ensemble des solutions de $P$. Si $\text{Sols}(P) = \emptyset$, $P$ est dit incohérent, sinon, il est dit cohérent.

$\text{Sols}(P)^{\perp Y} = \{d \in D(Y) \text{ t.q. } \exists d' \in \text{Sols}(P), d' \models d\}$ dénote la projection de $\text{Sols}(P)$ sur $Y \subseteq X$.

On dit que $v$ est une valeur globalement cohérente pour $x$ ssi $v \in \text{Sols}(P)^{\perp\{x\}}$. Lorsque toute les valeurs des domaines du CSP sont globalement cohérentes pour la variable correspondante, on dit que les domaines du CSP sont globalement cohérents (ou simplement que le CSP est globalement cohérent).

**Conditions Booléennes** Un *fluent* est un couple $(x, A)$, avec $x \in X$ (et généralement, $A \subseteq D(x)$, mais pas nécessairement) ; il est élémentaire quand $A$ est un singleton - il représente alors une affectation de $x$. Une *condition booléenne* est une formule logique (utilisant les opérateurs $\lor, \land, \Rightarrow, \neg, \Leftrightarrow$ dans leur acceptation classique) dont les atomes sont des fluents. $\text{vars}(c)$ dénote l'ensemble des variables de $c$.

Une affectation $d$ telle que $x \in \text{vars}(d)$ satisfait le fluent $f = (x, A)$ si et seulement si $d(x) \in A$ (on note $f(d) = \top$). Soit $c$ une condition booléenne et $d$ une affectation de $\text{vars}(c)$. La valeur de vérité de $c$ dans $d$, notée $c(d)$ est calculée conformément à l'interprétation habituelle des opérateurs logiques. $d$ satisfait $c$ (noté $d \models c$) ssi $c(d) = \top$.

Certaines contraintes de la gamme seront représentées par des conditions booléennes - typiquement les contraintes options (c.f. section 2). Les description synthétiques utiles aux tâches de restitution de la gamme (c.f. Section 3.2) et les cas d'emplois relatifs à la documentation pièces (c.f. Section 3.3) le seront également. Dans la suite, on suppose généralement que les conditions booléennes manipulées sont intrinsèquement cohérentes ($\exists d \in D(\text{vars}(c)), c(d) = \top$) et que l'on peut

tester en temps polynômial (idéalement, linéaire) leur satisfaction par une affectation de leurs variables.

## 4.2 Résultats

Les Tables 1 à 4 décrivent comment les requêtes présentées en section 3 peuvent être formalisées, et donnent nos premiers résultats quant à leur complexité. Certaines définissent clairement des problèmes de décision au sens de la théorie de la complexité, par exemple le problème de cohérence de la gamme (il revient à déterminer si $< X, D, C >$ est cohérent). D'autres sont des problèmes de recherche souvent NP-difficiles. Dans les Tables qui suivent, nous essayons d'affiner cette information : la complexité d'un problème de recherche d'objet (ex : d'une solution d'un CSP, d'un ensemble minimal incohérent de contraintes) est en effet directement liée à celle de l'existence d'un tel objet ou à celle du test de conformité de l'objet. Il peut arriver que le test de conformité soit linéaire alors que le test d'existence est difficile (typiquement, pour l'existence / le test de solution d'un CSP) ; il peut également arriver que le test d'existence soit trivial, alors que le test de conformité est difficile (par exemple, pour l'existence / le test d'ensembles (minimaux) incohérents de contraintes). Faute de place, seules les preuves de complexité les moins évidentes seront évoquées<fnref n="2" />.

**Documentation véhicule** (voir Table 1). La requête de *Cohérence* (éventuellement contextuelle) correspond au test de cohérence, classique, d'un CSP, d'où sa NP-complétude. Sans surprise, on appellera *conflit* un ensemble incohérent de contraintes, et l'objectif est de connaître des conflits minimaux pour l'inclusion. On retrouve des notions de sous ensemble minimaux incohérents étudiées depuis la fin des années 80 en IA et plus récemment en configuration [3][4][1] [6] (voir en particulier [4][6] pour le cas contextuel). La recherche de conflits minimaux (éventuellement contextuels) est NP-difficile, puisque le simple test d'(in)cohérence de $< X, D, C' >$ appelle la résolution d'un problème de cohérence. D'après [1], la question est $\text{BH}_2$-complète.<fnref n="3" />

La question de la cohérence positive du modèle est évidement une question de cohérence globale des contraintes et des domaines. Elle est donc NP-difficile.

<footnote n="2">²Pour plus de détails voir ftp://ftp.irit.fr/IRIT/RPDMP/PapersFargier/wsecai10.pdf</footnote>

<footnote n="3">³$\text{BH}_2$ est l'ensemble des problèmes qui se ramènent à un problème de NP et un problème de CO-NP. Le problème $\text{BH}_2$-complet canonique est le problème SAT-UNSAT : il s'agit de déterminer si, étant donnée une paire $(\phi, \psi)$ de 3-CNF, la première est satisfiable et la seconde insatisfiable).</footnote>
<table><caption>TAB. 1 – Résultats : Élaboration de la documentation véhicule</caption><thead><tr><th>Nom</th><th>Donnée</th><th>Requête</th><th>Complexité</th></tr></thead><tbody><tr><td>Cohérence de la gamme</td><td>&lt; X, D, C &gt;</td><td>&lt; X, D, C &gt; admet-il une solution ?</td><td>NP-complet</td></tr><tr><td>Cohérence contextuelle</td><td>&lt; X, D, C &gt;<br>c une cond. booléenne cohérente</td><td>&lt; X, D, C &cup; {c} &gt; admet-il une solution ?</td><td>NP-complet</td></tr><tr><td>Conflits</td><td>&lt; X, D, C &gt;<br>C' &sube; C</td><td>Déterminer si<br>(i) &lt; X, D, C' &gt; incohérent et<br>(ii) &forall;C'' &sube; C', &lt; X, D, C'' &gt; cohérent</td><td>BH<sub>2</sub>-complet</td></tr><tr><td>Conflits contextuels</td><td>&lt; X, D, C &gt;<br>Cxt un ensemble de cond.<br>booléennes cohérentes,<br>C' &sube; C</td><td>Déterminer si<br>(iii) &lt; X, D, C' &cup; Cxt &gt; incohérent et<br>(iv) &forall;C'' &sube; C', &lt; X, D, C'' &cup; Cxt &gt;<br>cohérent</td><td>BH<sub>2</sub>-complet</td></tr><tr><td>problème de recherche :</td><td>trouver un /tous les C'</td><td>respectant (i) et (ii) (resp. (iii) et (iv))</td><td></td></tr><tr><td>Cohérence positive</td><td>&lt; X, D, C &gt; Cohérent<br>c &isin; C une contrainte<br>d'arité inférieure à k</td><td>Déterminer si c est globalement cohérente<br>(&forall;d &isin; D(vars(c)), d &darr; c<br>&rarr; &exist;d' &isin; Sols(P), d' &darr; d)</td><td>NP-complet<br>y compris si<br>c est unaire</td></tr></tbody></table>

<table><caption>TAB. 2 – Résultats : Restitution de la gamme</caption><thead><tr><th>Nom</th><th>Donnée</th><th>Requête</th><th>Complexité</th></tr></thead><tbody><tr><td>Validité de description</td><td>P = &lt; X, D, C &gt; cohérent,<br>c une cond. booléenne cohérente</td><td>Déterminer si c est valide<br>(i.e. si &forall;d &isin; Sols(&lt; X, D, C &gt;), d &darr; c)</td><td>CO-NP<br>complet</td></tr><tr><td>Simplification de<br>description</td><td>c une cond. booléenne cohérente</td><td>Déterminer si c est minimale<br>&forall;x &isin; vars(c), &exist;d, d' &isin; D(vars(c)) t.q.<br>(&forall;y = xd(y) &ne; d'(y)) &and; (d &darr; c)(&exist;d' &ne; c))</td><td>O(d<sup>|vars(c)|</sup>)</td></tr><tr><td>Génération de<br>description</td><td>P = &lt; X, D, C &gt; cohérent,<br>c une cond. booléenne cohérente</td><td>Déterminer si c équivaut à<br>Sols(P)<sup>|vars(c)|</sup> (si &forall;d &isin; D(vars(c)) :<br>c(d) = &top; &harr; d &isin; Sols(P)<sup>|vars(c)|</sup>)</td><td>&Pi;<sub>2</sub><sup>P</sup>-complet</td></tr><tr><td>problème de recherche :</td><td>trouver un c t.q.</td><td>vars(c) &sube; Y<br>et c équivaut à Sols(P)<sup>|vars(c)|</sup></td><td></td></tr><tr><td>Comptage</td><td>P = &lt; X, D, C &gt;, cohérent,<br>Y &sube; X</td><td>Calculer |Sols(P)<sup>|Y|</sup>|</td><td>#P-difficile</td></tr></tbody></table>

<table><caption>TAB. 3 – Résultats : élaboration de la documentation pièces</caption><thead><tr><th>Nom</th><th>Donnée</th><th>Requête</th><th>Complexité</th></tr></thead><tbody><tr><td>Concision de la doc.</td><td>P = &lt; X, D, C &gt;, cohérent<br>C' un ensemble<br>de cond. booléennes cohérentes</td><td>Déterminer si C' est concis<br>(&forall;c' &isin; C', &lt; X, D, C &cup; {c'} &gt; cohérent)</td><td>NP-complet</td></tr><tr><td>Exhaustivité de la doc.</td><td>P = &lt; X, D, C &gt;, cohérent<br>C'' un ensemble<br>de cond. booléennes cohérentes</td><td>Déterminer si C' est exhaustif<br>(si &lt; X, D, C &cup; &cup;<sub>c' &isin; C'</sub> {&not;c'} &gt;<br>est incohérent)</td><td>CO-NP<br>complet</td></tr><tr><td>problème de recherche</td><td>trouver une cond. booléenne<br>cohérente c</td><td>telle que d &darr; c &harr; (&forall;c' &isin; C', d &ne; c')</td><td>NP-difficile</td></tr><tr><td>Non-dualité des emplois</td><td>P = &lt; X, D, C &gt;, cohérent<br>C' un ensemble<br>de cond. booléennes cohérentes</td><td>Déterminer si C' comporte des cas<br>de dualité (si &exist;c' &ne; c'' &isin; C'<br>t.q. &lt; X, D, C &cup; {c', c''} &gt; cohérent)</td><td>NP-complet</td></tr><tr><td>problème de recherche</td><td>trouver une cond. booléenne<br>cohérente c</td><td>telle que étant donnés c', c'' &isin; C' :<br>&forall;d &isin; Sols(P) : (d &darr; c &harr; d &darr; c' et d &darr; c'')</td><td>NP-difficile</td></tr></tbody></table>
<table><caption>TAB. 4 – Résultats : Configuration en ligne</caption><thead><tr><th>Nom</th><th>Donnée</th><th>Requête</th><th>Complexité</th></tr></thead><tbody><tr><td>Cohérence globale</td><td>P = &lt; X, D, C &gt;, cohérent<br>x &isin; X \ vars(d), v &isin; D(x)</td><td>Existe t il d' &isin; Sols(P) t.q.<br>d'(x) = v?</td><td>NP-complet</td></tr><tr><td>Cohérence globale<br>(version incrémentale)</td><td>P = &lt; X, D, C &gt;, glb. cohérent<br>d tq. &exist; d' &isin; Sols(P), d' &ne; d<br>x &isin; X, v &isin; D(x)</td><td>Existe t il d' &isin; Sols(P)<br>d' &ne; d et d'(x) = v?</td><td>NP-complet</td></tr><tr><td>Estimation du prix</td><td>P = &lt; X, D, C &gt;, cohérent<br>S un ens. fini de fct de coût sur X<br>d une affectation (partielle)</td><td>Calculer<br>&alpha;<sub>m</sub> = min<sub>d' &isin; Sols(P), d' &ne; d</sub> &Sigma;<sub>s &isin; S</sub>s(d')<br>&alpha;<sub>m</sub> = max<sub>d' &isin; Sols(P), d' &ne; d</sub> &Sigma;<sub>s &isin; S</sub>s(d')</td><td>NP-difficile<br>NP-difficile</td></tr><tr><td>Estimation du délai</td><td>P = &lt; X, D, C &gt;, cohérent<br>x<sub>t</sub> une variable codant le délai<br>d une affectation (partielle)</td><td>Calculer<br>&alpha;<sub>m</sub> = min<sub>d' &isin; Sols(P), d' &ne; d</sub> d'(x<sub>t</sub>)<br>&alpha;<sub>m</sub> = max<sub>d' &isin; Sols(P), d' &ne; d</sub> d'(x<sub>t</sub>)</td><td>NP-difficile<br>NP-difficile</td></tr><tr><td>Calcul de restauration</td><td>P = &lt; X, D, C &gt;<br>Choix un ens. de cond. booléennes<br>R &sube; Choix</td><td>Est il vrai que &lt; X, D, C &cup; R &gt;<br>est cohérent et que &forall; R' &sube; Choix t.q.<br>R &sube; R', &lt; X, D, C &cup; R' &gt;<br>est incohérent?</td><td>BH-2 complet</td></tr><tr><td>Calcul de conflit</td><td>P = &lt; X, D, C &gt;<br>Choix un ens. de cond. booléennes<br>R &sube; Choix</td><td>Est il vrai que &lt; X, D, C &cup; R &gt;<br>est incohérent et que &forall; R' &sube; R<br>&lt; X, D, C &cup; R' &gt; est cohérent?</td><td>BH-2 complet</td></tr><tr><td>Complétion</td><td>d une affectation (partielle)<br>P = &lt; X, D, C &gt; glb. coherent pour d</td><td>Existe-t-il d' &isin; Sols(P) t.q. d' &ne; d?</td><td>trivial</td></tr><tr><td>Problème de recherche</td><td></td><td>Trouver d' &isin; Sols(P) t.q d' &ne; d</td><td>?????</td></tr><tr><td>Problème de recherche<br>version optimisation</td><td>S un ens. fini de fct de coût<br>x<sub>t</sub> une variable codant le délai</td><td>Trouver d' &isin; Sols(P) tel que d' &ne; d<br>et que &forall; d'' &isin; Sols(P) si d'' &ne; d<br>alors &Sigma;<sub>s &isin; S</sub>s(d'') &le; &Sigma;<sub>s &isin; S</sub>s(d'')</td><td>NP-Difficile</td></tr><tr><td></td><td></td><td>Trouver d' &isin; Sols(P) t.q. d' &ne; d<br>et &forall; d'' &isin; Sols(P), d'' &ne; d &rarr; d''(x<sub>t</sub>) &le; d'(x<sub>t</sub>)</td><td>NP-difficile</td></tr></tbody></table>

**Restitution de la gamme** (voir Table 2). En restitution de la gamme, on cherche à obtenir des descriptions synthétiques sur des sous-ensembles de variables - techniquement, ce sont des projections de l'ensemble des solutions du CSP sur ces sous-ensembles. Idéalement, on les voudrait les plus simples possibles, c'est-à-dire impliquant le moins de variables possible. Dans le contexte de notre application, ces description doivent être données sous la forme d'une condition booléenne cohérente (la cohérence interne des descriptions ne doit pas être une source de complexité). Techniquement, nous dirons donc qu'une description booléenne c est valide ssi $\forall d \in Sols(P), d \models c$, qu'elle est synthétique si elle coïncide avec la projection de la gamme sur ses variables ($\forall d \in D(vars(d)), c(d) = \top \Leftrightarrow d \in Sols(P)^{\lfloor vars(c) \rfloor}$) et qu'elle est minimale si il n'existe pas de $Y \subseteq vars(C)$ telle que la restriction de c à Y lui soit équivalente. Le problèmes de validité est CO-NP complet, les problèmes d'inférence clausale ou de redondance de contrainte en étant des cas particuliers.

Le test de conformité associé à la Génération de description est $\Pi_2^P$-complet<fnref n="4" />. Le principe de la démonstration de est dans notre cas : c est la condition $\bigwedge_{x \in Y}(x, D(x))$ : cette condition sélectionne un certain nombre de variables (celles de Y) sans restreindre les valeurs. Dans ce cas c équivaut à $Sols(< X, D, C >)^{\lfloor vars(c) \rfloor}$ si et seulement si, pour toute affectation de Y, il existe une affectation de $X \setminus Y$ qui satisfasse le CSP. On peut donc réduire le problème canonique de $\Pi_2^P$ ($\forall Y_1, \exists Y_2 : \Sigma, \Sigma$ étant une CNF) au problème de test de l'équivalence entre la projection sur $Y_2$ d'un CSP représentant la CNF et la condition $c = \bigwedge_{x \in Y_2}(x, \{\text{true}, \text{false}\})$. Le test d'appartenance à $\Pi_2^P$ est plus simple. L'implication $d \in Sols(< X, D, C >)^{\lfloor vars(c) \rfloor} \implies c(d) = \top$ se falsifie avec un oracle (deviner d, vérifier que d satisfait toutes les contraintes puis vérifier que $c(d) = \bot$). Pour falsifier $c(d) = \top \implies d \in Sols(< X, D, C >)^{\lfloor vars(c) \rfloor}$, il faut deviner une affectation de $vars(c)$, montrer qu'elle satisfait c, puis montrer qu'elle est inconsistante avec le CSP (ce qui est un problème de CO-NP).

Les problèmes de décision liés à la restitution de la gamme sont typiquement des problèmes d'inférence. Cela dit, la projection et la simplification sont basiquement des problèmes de recherche auxquels on peut récanonique de $\Pi_2^P$ est celui qui consiste à détermininer si une formule booléenne quantifiée de la forme $\forall Y_1 \exists Y_2 \phi$ est valide, $\phi$ étant une 3-CNF et $\{Y_1, Y_2\}$ une partition de ses variables.

<footnote n="4">⁴Rappelons qu’un problème appartient à $\Pi_2^P = NP^{CO-NP}$ si on peut résoudre son co-problème en (1) faisant appel à un NP-oracle et (2) établissant un certificat non pas de manière polymiale mais en résolvant un problème de CO-NP. Le problème</footnote>
pondre par des algorithmes d'élimination de variables - en utilisant un espace potentiellement exponentiel.

**Élaboration de la documentation pièces** (voir Table 3). L'idée est de représenter chaque cas d'emploi par une condition booléenne cohérente (la cohérence interne d'un cas d'emploi n'est pas une source de complexité), et de considérer l'ensemble $C'$ des cas d'emploi d'une pièce générique : $C'$ est exhaustif ssi $\forall d \in Sols(P), \exists c' \in C' \text{ t.q. } d \models c'$; on dit que $c', c'' \in C'$ forme une paire d'emplois duale ssi $\exists d \in Sols(P), (d \models c')$ et $(d \models c'')$. $C'$ est non exhaustif ssi $< X, D, C \cup \bigcup_{c' \in C'} \{\neg c'\} >$ est cohérent et il est non dual ssi chacun des problèmes $< X, D, C \cup \{c'\} >$, $c' \in C'$ est cohérent.

Ces trois questions demandent de tester la cohérence ou l'incohérence d'un CSP, cohérent au départ, auquel on ajoute une ou plusieurs contraintes. Les preuves de complexité associées ne présentent aucune difficulté.

Enfin, on veut caractériser par une condition booléenne $c$ les véhicules de la gamme "en erreur" par rapport à l'exigence de non-dualité ou d'exhaustivité de la pièce générique. $c$ représente les cas de non-exhaustivité ssi $\forall d \in Sols(P), d \models c \Leftrightarrow \forall c' \in C, d$ viole $c'$; il représente les cas de non dualité ssi $\forall d \in Sols(P), d \models c \Leftrightarrow \exists c', c'' \in C, d \models c'$ et $d \models c''$. Dans le premier cas, la CO-NP difficulté se prouve par réduction du problème d'inférence clausale ($C = \emptyset, c$ est la clause à inférer et les $c'$ sont les négations des clauses de la CNF). La CO-NP difficulté du second problème se prouve par réduction du même problème ($c$ est la clause à inférer et $c'$ et $c''$ représentent une partition des clauses).

**Configuration en ligne** (voir Table 4) La cohérence globale des domaines doit être assurée en amont de la configuration utilisateur, pour ne lui laisser comme choix de configuration que des valeurs d'option présentes dans au moins un véhicule de la gamme. La version incrémentale est la répétition de ce principe en cours de configuration : l'utilisateur fixe une affectation $d$, cohérente, et l'on veut, pour toute variable $x$, ne laisser que des valeurs $v$ pouvant effectivement conduire à un véhicule $d'$ tel que $d' \models d$ et $d'(x) = v$. Dans ses deux versions, le problème de la maintenance de la cohérence globale est un problème NP-difficile.

Pour la prise en compte des coûts, on utisera une modélisation proche de celle des problèmes à contraintes souples (c.f. [12, 2]) : une "fonction de coût" est une fonction $s$ sur $D(\text{vars}(s))$ prenant ses valeurs dans une échelle, ici $\mathbb{Z}$ et le "coût" d'une affectation est la somme des coûts qui lui sont associés par ces fonc-

tions. Notons que certains coûts pouvant être négatifs, il faut théoriquement relaxer l'exigence de monotonie de l'opérateur d'agrégation (ici, l'addition). Lorsque tous les coûts sont positifs, que $d$ n'instancie aucune variable et que $C = \emptyset$, le problème d'estimation du prix est un problème classique de minimisation de coûts dans un CSP souple, réputé NP-difficile.

Pour l'estimation du délai, on peut représenter le délai par une variable particulière $x_t$ et coder les connaissances par des conditions logiques du type $c \Rightarrow x_t \in I_1 \cup \dots \cup I_k$, les $I_j$ étant des intervalles (ex : $x_t \in (-\infty, 8] \cup [10, +\infty)$). L'estimation du délai min (et du délai max par ailleurs) est un problème NP-difficile : lorsque $d$ n'instancie aucune variable, et que seules des bornes inférieures sont données quant au délai, on reconnaît le problème d'optimisation dans les CSP à priorité [11] où il faut minimiser la priorité de la plus importante des contraintes violées.

La complétion de configuration est au sens d'un critère de coût ou de délai est évidement un problème NP-difficile. En revanche, on ne sait pas si il existe un algorithme polynomial permettant d'obtenir une solution à partir d'un problème globalement cohérent. Si un tel algorithme existe (ce qui est peu probable), il ne procède pas par réétablissement de la cohérence globale. Notre résultat sur la cohérence globale incrémentale montre en effect que, sous l'hypothèse $P \neq \text{NP}$, il n'existe pas d'algorithme polynomial ré-établissant la cohérence globale suite à l'affectation d'une variable.

Pour les problèmes de calcul de restauration et de conflits, voir [1].

## 4.3 Probabilisation d'un CSP

Les problèmes de gestion de taux ne peuvent pas être modélisés de manière simple sous la forme d'un CSP ou d'un CSP valué, les taux n'étant pas indépendants les uns des autres. Il faudrait pouvoir définir une notion de CSP probabilisé comme étant un quadruplet $P^* = \langle X, D, C, F \rangle$, où $\langle X, D, C \rangle$ est un CSP et $F$ est un ensemble de distributions de probabilités sur des sous-ensembles de $X$. Pour tout $p \in F$, on note $\text{vars}(p) \subseteq X$ les variables sur lesquelles porte $p$.

On dira que $P^*$ est cohérent avec $F$ si et seulement si il existe une distribution de probabilité $p^*$ sur les affectations complètes de $X$ telle que :

$$ - d \notin Sols(< X, D, C >) \implies p^*(d) = 0 $$

$$ \begin{array}{l} - \forall p \in F, d \text{ tel que } \text{vars}(d) = \text{vars}(p) : \\ p(d) = \sum_{d' \in Sols(<X, D, C>), d' \models d} p^*(d') \end{array} $$

On note $Sols(P^*)$ l'ensemble des distributions de probabilité $p^*$ vérifiant les deux conditions ci dessus. Le CSP probabilisé peut être sur-spécifié (aucune distribution n'est cohérente avec les taux de $F$) ou sous-spécifié, dans ce cas $Sols(P^*)$ contient plusieurs $p^*$.
La requête principale n'est pas le calcul explicite d'un $p^*$, qui est une distribution sur un ensemble de taille exponentielle ($Sols(< X, D, C >)$). Dans notre application, on cherche plutôt à connaître la probabilité d'affectations de $X$, de valeurs $v$ dans les domaines, ou plus généralement, d'événements. Pour toute condition booléenne $c$, on peut définir :

$$ 
\begin{aligned}
P_{inf}(c) &= Inf_{p^* \in Sols(P^*)} \sum_{d' \in Sols(<X,D,C>), d'=c} p^*(d') \\
P_{sup}(c) &= Sup_{p^* \in Sols(P^*)} \sum_{d' \in Sols(<X,D,C>), d'=c} p^*(d')
\end{aligned}
$$

Notons que $P_{inf}$ et $P_{sup}$ ne sont pas des mesures de probabilité. Elle encadrent la mesure de probabilité.

La notion de CSP probabilisé est bien différente des notions de CSP stochastique [14] ou probabiliste[5]. Dans ces deux formalismes (1) il existe deux types de variables, les variables de décision et les variables aléatoires (dans un CSP probabilisé, toutes les variables sont aléatoires) (2) les variables aléatoires sont indépendantes (il existe une unique $p^*$ et son calcul est immédiat) et (3) on ne calcule pas la probabilité d'une affectation mais la probabilité qu'une affectation satisfasse le CSP : plusieurs affectations peuvent avoir une probabilité de 1 (dans un CSP probabilisé la somme des probabilités des affectations est égale à 1).

Les CSP probabilisés seraient une généralisation des réseaux bayésiens, relachant l'hypothèse qu'il existe une unique distribution jointe dont les projections seraient les distribution $p \in F$ (les Tables du réseau bayésien), et que le réseau est acyclique. Par conséquent le simple calcul d'une affectation de probabilité inférieure maximale serait un problème NP-difficile.

Sans entrer plus dans les détails, disons simplement que l'analyse de la tâche de gestion des taux en termes de programmation par contraintes fait apparaître le besoin d'un nouveau modèle qui serait une généralisation de réseaux bayésiens. L'analyse de la complexité des requêtes associées et la définition d'algorithmes efficaces sortent du cadre de cet article.

# 5 Conclusion

La formalisation d'un certain nombre d'applications métier utilisant une modélisation à base de contraintes d'une gamme montre que la preuve de la cohérence d'un CSP est loin d'être la seule requête que doivent addresser les algorithmes de programmation par contraintes : on rencontre notamment des problèmes d'inférence, des problèmes d'optimisation, des problèmes de comptage et des problèmes de marginalisation, qui se situent souvent au dessus de NP.

Dans la plupart des cas, le CSP considéré est notamment cohérent, connu à l'avance, et commun à toute une série de requêtes. Chez Renault, l'équipe "Intelligence Artificielle Appliquée" en charge de ces applications a choisi une approche par compilation du CSP

représentant la gamme [9], approche qui permet de répondre en temps satisfaisant (de l'ordre du centième de seconde pour la configuration en ligne, par exemple) à la plupart des requêtes.

La question est maintenant de savoir (1) si les algorithmes proposés par la communauté CSP peuvent donner des résultats comparables, (2) si la communauté peut proposer des algorithmes efficaces pour les problèmes qui ne sont pas typiquement des problèmes de satisfaction (par exemple, l'établissement de la cohérence globale, le calcul de marginalisations), et (3) comment étendre le modèle CSP pour qu'il sache traiter de questions d'inférence complexes - typiquement, effectuer de l'inférence probabiliste.

# Références

[1] J. Amilhastre, H. Fargier, and P. Marquis. Consistency restoration and explanations in dynamic CSP - application to configuration. *Artificial Intelligence*, 135(1-2):199-234, 2002.

[2] M. C. Cooper and T. Schiex. Arc consistency for soft constraints. *Artificial Intelligence*, 154(1-2):199-227, 2004.

[3] Johan de Kleer. Problem solving with the atms. *Artificial Intelligence*, 28(2):197-224, 1986.

[4] J. L. de Siqueira N. and J-F Puget. Explanation-based generalisation of failures. In *ECAI*, pages 339-344, 1988.

[5] H. Fargier and J. Lang. Uncertainty in constraint satisfaction problems : a probabilistic approach. In *ECS-QARU*, pages 97-104, 1993.

[6] Alexander Felfernig, Gerhard Friedrich, Dietmar Janisch, and Markus Stumptner. Consistency-based diagnosis of configuration knowledge bases. *Artif. In-tell.*, 152(2):213-234, 2004.

[7] E. Gelle and R. Weigel. Interactive configuration using constraint satisfaction techniques. In *PACT-96*, pages 37-44, 1996.

[8] S. Mittal and B. Falkenhainer. Dynamic constraint satisfaction problems. In *AAAI*, pages 25-32, 1990.

[9] B. Pargamin. Vehicle sales configuration : the cluster tree approach. In *ECAI'02 Configuration Workshop*, 2002.

[10] D. Sabin and E. C. Freuder. Configuration as composite constraint satisfaction. In *AI and Manufacturing Research Planning Workshop*, pages 153-161, 1996.

[11] T. Schiex. Possibilistic constraint satisfaction problems or "how to handle soft constraints?". In *UAI*, pages 268-275, 1992.

[12] T. Schiex. Arc consistency for soft constraints. In *CP*, pages 411-424, 2000.

[13] T. Walsh. Sat v csp. In *CP*, pages 441-456, 2000.

[14] T. Walsh. Stochastic constraint programming. In *ECAI*, pages 111-115, 2002.