No d'ordre

Jean - Pierre Nadeau

Description

Niveau: Supérieur, Doctorat, Bac+8
No d'ordre : 2397 2006 Thèse présentée en vue de l'obtention du grade de docteur de L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE École Doctorale : Systèmes Spécialité : Systèmes Industriels 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 Soutenue le 15 novembre 2006, devant le jury composé de : Jean-Pierre NADEAU Examinateur (Président du jury) Laurent GRANVILLIERS Rapporteur Philippe LUTZ Rapporteur Michel ALDANONDO Examinateur (Directeur de thèse) Paul GABORIT Examinateur (Encadrant) Élise VAREILLES Examinateur (Encadrant) Matthieu VERON Examinateur (Invité) Thèse préparée au Centre Génie Industriel de l'École des Mines d'Albi-Carmaux

• salari- sation des doctorants


• industriel de l'école des mines d'albi-carmaux


• faculté des sciences de nantes


• oudenhove de saint géry


• statistique de la contrainte


• jean paul

Sujets

• Institut national polytechnique de Toulouse
• Lamport
• Nadeau
• Vareilles

Informations

• Publié par: profil-feym-2012
• Nombre de lectures: 40
• Poids de l'ouvrage: 1 Mo

Extrait

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 . . . . . . . . . . . . .