No d'ordre

oN d’ordre:2397 2006
Thèseprésentée
envuedel’obtentiondugradede
docteurde
L’INSTITUTNATIONALPOLYTECHNIQUEDETOULOUSE
ÉcoleDoctorale:Systèmes
Spécialité:SystèmesIndustriels
par
Thomas VAN OUDENHOVE DE SAINT GÉRY
CONTRIBUTION À L’ÉLABORATION D’UN FORMALISME
GÉRANT LA PERTINENCE POUR LES PROBLÈMES D’AIDE
À LA CONCEPTION À BASE DE CONTRAINTES
Soutenuele15novembre2006,devantlejurycomposéde:
Jean PierreN ADEAU Examinateur(Présidentdujury)
LaurentGRANVILLIERS Rapporteur
PhilippeLUTZ
MichelALDANONDO Examinateur(Directeurdethèse)
PaulGABORIT(Encadrant)
ÉliseVAREILLES
MatthieuVERON Examinateur(Invité)
ThèsepréparéeauCentreGénieIndustrieldel’ÉcoledesMinesd’Albi CarmauxRemerciements
En premier lieu, je voudrais remercier mes encadrants de thèse; ce manuscrit ne serait
pasaussiaboutisansleursconseilsetleurdisponibilité:MichelALDANONDO,directeurde
thèseetPaulGABORIT,encadrant,sansoublierÉliseVAREILLES,quifûtmacollèguependant
deux ans et a rejoint l’équipe d’encadrement pour la dernière année. Merci à tous les trois
dem’avoiraccompagnétoutaulongdecestroisannées.
J’adresse également mes remerciements aux autres membres de mon jury, pour avoir
acceptédejugernostravaux:
– Laurent GRANVILLIERS, rapporteuret Professeur àla Faculté desSciences de Nantes
(Laboratoired’InformatiqueNantesAtlantique),
– PhilippeLUTZ,rapporteuretProfesseurauLaboratoired’AutomatiquedeBesançon,
– NADEAU, président du jury et Pr à l’École Nationale Supérieure des Arts &
MétiersdeBordeaux,
– MathieuVERON,examinateur,cofondateuretcodirigeantdelasociétéADELYA.
MerciàtousceuxquifontouontfaitpartieduCentreGénieIndustrielaucoursdemon
doctorat(Lionel,Matthieu,Jacques,Franck,Didier,Elyes,Hervé,Jacqueline(s),Fred,Marco
et les docteurs ou doctorants : David, Franck, Mathieu, Jihed, Jaouher, Vérane, Amadou,
Romain,Yosra,Samieh,Carmen,Nalyettousceuxquej’oublie)etplusparticulièrementIsa
belle. Merci aussi à Monsieur le sysadmin Emmanuel OTTON et Madame la sysadmin Cathy
ORTEU.
Jeremercieaussitouslesdoctorants(etlesautres)avecquinousavonsarrachélasalari
sationdesdoctorants,toutparticulièrementceuxquiyontjouéunrôleactif,ainsiquelesca
maradesDenis,Serge,Jean Claude,Jean Paul,Guy,Jean Michel,Élisabeth,Rachel,Bruno,...
J’adresseaussidespenséesparticulièresàRomainetSteph,ElPatou,Seb,James,Gillou,Fa
bien, Petit Ohu, Clémence, Jeff et Anne Cécile, Marilyn, Ana et Max, Emeline,... mais aussi
àBonrep’setAnne,HélèneetGrego,BranloetMarie,Bi,Rem,lecamaradeMoulinovitchet
lesmembresde«l’orchestre»BloomingTraczir.
Je tiens aussi à remercier toute ma famille, qui m’a soutenu pendant tout ce temps. Un
immense merci à Cédric et Julien pour notre cohabitation dans la maison des trois petits
cochons...Enfin,merciàtousceuxquiauraientuneplaceicietquej’aioublié...
Pour finir, une petite pensée pour Donald E. KNUTH et Leslie LAMPORT, sans qui ce
manuscritneseraitpascequ’ilest.
Thomas VAN OUDENHOVE DE SAINT GÉRY iii«L’histoiredel’humanitéestunestatistiquedelacontrainte.»
LéoFERRÉ(1916–1993)Tabledesmatières
Remerciements iii
Tabledesmatières vii
Tabledesfigures xi
Listedestableaux xiii
Listedesalgorithmes xv
Listedesexemples xvii
Introductiongénérale 1
Cadregénéral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Plandelecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
I Conception, configuration et approches à base de contraintes : état de l’art
etproblématique 5
1 Conceptionetconfiguration:présentationetbesoins 7
1.1 Lesdifférentstypesdeconception . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Conceptioncréative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2innovante . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Conceptionroutinière . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Exploitationdesconnaissances . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Exploitationdeimplicites . . . . . . . . . . . . . . . . . 10
1.2.2deconnaissancesexplicites . . . . . . . . . . . . . . . . . . 10
Thomas VAN OUDENHOVE DE SAINT GÉRY viiviii TABLEDESMATIÈRES
1.2.3 Discussionetraisonnementretenu . . . . . . . . . . . . . . . . . . . . . 11
1.3 Aideàlaconceptionetconfiguration . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Besoinsenconfigurationetconception . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Desélémentsdedifférentesnatures . . . . . . . . . . . . . . . . . . . . 16
1.4.2 Utilisationd’unmodèlearborescent . . . . . . . . . . . . . . . . . . . . 16
1.4.3 Priseencompted’élementsoptionnelsetnotiondepertinence . . . . . 17
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Approchesparcontraintes:les CSPdiscretsetcontinus 21
2.1 Modélisationetapprochesparcontraintes . . . . . . . . . . . . . . . . . . . . . 21
2.2 Recherchedesolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 Generate&Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 BackTracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.3 BackJumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Filtragesurdesdomainesdiscrets . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Classificationgénérale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Lacohérenced’arc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Filtragesurdesdomainescontinus . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Arithmétiquedesintervalles . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.2 2B cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.3 Box cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Diversitécompilée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6 Résolutionetfiltrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.1 Forward Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.2 Look Ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Élémentsoptionnelsethiérarchiedansles CSP 37
3.1 Les DCSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 Les CCSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 L’ajoutd’unevaleuraudomainedesvariables . . . . . . . . . . . . . . . . . . 40
3.4 Les CSPe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Les ACSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Transition 45
II Propositionsdemodélisationetimplémentationpourlarésolutiondepro
blèmesd’aideàlaconceptionouàlaconfiguration 47
4 Intégrationetprincipesdemodélisation:lesRCSP 49
4.1 Modéliseruncomposantstandardoptionnel . . . . . . . . . . . . . . . . . . . 49
4.2 Modélisationdecontraintesconditionnelles . . . . . . . . . . . . . . . . . . . . 50
4.3 Modéliseruncomposantparamétrableoptionnel . . . . . . . . . . . . . . . . . 51
4.3.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Thomas VAN OUDENHOVE DE SAINT GÉRYTABLEDESMATIÈRES ix
4.3.2 Modélisationd’uncomposantparamétrableoptionnelparl’ajoutd’une
valeuraudomaine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.3parl’ajoutd’unattributdepertinence . . . . . . . . . . . 54
4.3.4 Conclusionsurlapertinencedescomposants . . . . . . . . . . . . . . . 56
4.4 Modélisationdesous ensemblesoptionnels . . . . . . . . . . . . . . . . . . . . 56
4.4.1 Factorisationdel’attributdepertinence . . . . . . . . . . . . . . . . . . 57
4.4.2 Ajoutd’éléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4.3 Conclusionsurlamodélisationdesous ensemblesoptionnels . . . . . 63
4.5 LesRCSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5.2 Agrégationdessolutions . . . . . . . . . . . . .