N attribue par la bibliotheque

Idir Khemmoudj†

Description

Niveau: Supérieur, Doctorat, Bac+8
N? attribue par la bibliotheque Universite Paris-Nord THESE presentee par Mohand Ou Idir KHEMMOUDJ pour obtenir le titre de Docteur d'Universite Specialite Informatique Sujet: Modelisation et resolution de systemes de contraintes : Application au probleme de placement des arrets et de la production des reacteurs nucleaires d'EDF Soutenue publiquement le 4 Avril 2007 devant le jury compose de M. Abderrahmane AGGOUN Examinateur M. Hachemi BENNACEUR Directeur M. Christophe FOUQUERE Examinateur M. Philippe MICHELON Rapporteur M. Gerard PLATEAU President M. Marc PORCHERON Co-directeur M. Thomas SCHIEX Rapporteur

• application au probleme de placement des arrets


• docteur de l'universite specialite


• backjumping de gaschnig


• optimisation des systemes de contraintes


• algorithme de resolution par separation


• algorithme de retour arriere de base pour la resolution de csp

Sujets

• Abd al-Rahm?n
• Plateau
• Hachemí

Informations

• Publié par: mijec
• Publié le: 01 avril 2007
• Nombre de lectures: 78
• Langue: Français

Extrait

–N attribu¶e par la biblioth?eque
Universit¶e Paris-Nord
THESE
pr¶esent¶ee par
Mohand Ou Idir KHEMMOUDJ
pour obtenir le titre de
Docteur d’Universit¶e
Sp¶ecialit¶e Informatique
Sujet:
Mod¶elisation et r¶esolution de system? es de contraintes :
Application au probleme? de placement des arr^ets et de la
production des r¶eacteurs nucl¶eaires d’EDF
Soutenue publiquement le 4 Avril 2007
devant le jury compos¶e de
M. Abderrahmane AGGOUN Examinateur
M. Hachemi BENNACEUR Directeur
¶M. Christophe FOUQUERE Examinateur
M. Philippe MICHELON Rapporteur
M. Gerard PLATEAU Pr¶esident
M. Marc PORCHERON Co-directeur
M. Thomas SCHIEX RapporteurRemerciements
Messieurs Hachemi Bennaceur et Marc Porcheron ont co-dirig¶e ma the?se. Ils sont d’une
gentillesse exemplaire. Ils ont toujours ¶et¶e disponibles et leur conseils ont ¶et¶e pr¶ecieux pour
moi. Ils m’ont beaucoup appris et ce travail n’aurait pas pu avoir le jour sans les discussions
fructueuses que nous avons eues tout au long de la p¶eriode du DEA et de la the?se. Je les
remercie beaucoup.
Je remercie M. Philippe Michelon et M. Thomas Schiex pour avoir accept¶e d’^etre
rapporteurs de ma th?ese. Je leur suis reconnaissant pour l’int¶er^et qu’ils ont port¶e a? mon travail.
Je tiens aussi a? exprimer mes sincer? es remerciements a? M. Abderrahmane Aggoun, a? M.
Christophe Fouquer¶e et a? M. Gerard Plateau pour m’avoir honor¶e en acceptant de juger mon
travail et participer au jury.
Je remercie mes parents, mes grand parents, tous mes fr?eres et s urs et tous les autres
membres de ma famille qui m’ont beaucoup soutenu.
Je remercie tous mes amis pour leur gentillesse et pour tous les moments que nous avons
pass¶e ensemble.
Je remercie tous les membres du LIPN et du d¶epartement OSIRIS de la division R&D
d’EDF pour leur sympathie et leur accueil chaleureux.Table des matier? es
1 Introduction 1
I System? es de contraintes : formalismes et m¶ethodes de r¶esolution 7
2 Satisfaction des systemes? de contraintes 9
2.1 Le formalisme CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Algorithme de retour arri?ere de base pour la r¶esolution de CSP . . . . . . . 13
2.3 Retours arri?ere intelligents . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Backjumping de Gaschnig . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Graph-based backjumping . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Con it-directed backjumping . . . . . . . . . . . . . . . . . . . . . . 16
2.3.4 Le dynamic backtracking . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 M¶ethodes de propagation de contraintes . . . . . . . . . . . . . . . . . . . . 17
2.4.1 Le principe g¶en¶eral . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Consistances locales . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.3 Contraintes Globales . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Heuristiques de prise de d¶ecision . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Optimisation des systeme? s de contraintes 25
3.1 Formalisme VCSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Formalisme CSOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Algorithme de r¶esolution par s¶eparation et ¶evaluation . . . . . . . . . . . . 29
3.4 Programmation math¶ematique . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4.1 Programmation Lin¶eaire . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.2 Relaxation Lagrangienne . . . . . . . . . . . . . . . . . . . . . . . . 33
iv?CHAPITRE 0. TABLE DES MATIERES
3.5 Recherche Locale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5.1 Principe g¶en¶eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5.2 Quelques m¶etaheuristiques . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
II Contributionsa?lar¶esolutiondesproblem? esCSP,Max-CSPetWCSP 41
¶4 Etat de l’art 43
4.1 Filtrage de CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.1 Consistance d’arc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.2 k-consistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1.3 Algorithmes de r¶esolution int¶egrant le flltrage . . . . . . . . . . . . 45
4.2 Bornes inf¶erieures pour les Max-CSP . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Partial Forward Checking . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 Partial Forward Checking et consistance d’arc orient¶ee . . . . . . . 47
4.2.3 Partial Forward Checking et consistance d’arc pond¶er¶ee . . . . . . . 47
4.2.4 Partial Forward Checking et consistance d’arc orient¶ee r¶eversible . . 48
4.3 Bornes inf¶erieures pour les WCSP . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.1 D¶eflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.2 Quelques consistances locales pour les WCSP. . . . . . . . . . . . . 51
4.4 Formulations math¶ematiques pour les WCSP . . . . . . . . . . . . . . . . . 54
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Filtrage de CSP par combinaison de la Relaxation Lagrangienne et de
l’arc-consistance 59
5.1 Une formulation agr¶eg¶ee pour les CSP binaires . . . . . . . . . . . . . . . . 59
5.2 Filtrage par Relaxation Lagrangienne . . . . . . . . . . . . . . . . . . . . . 61
5.3 Filtrage par relaxation Lagrangienne combin¶ee avec l’arc-consistance. . . . 65
5.4 Exp¶erimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
¶5.4.1 Evaluation du flltrage par relaxation Lagrangienne . . . . . . . . . . 67
¶5.4.2 EvaluationduflltrageparcombinaisondelarelaxationLagrangienne
et de l’arc-consistance . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
v?CHAPITRE 0. TABLE DES MATIERES
6 Bornesinf¶erieuresa?based’in¶egalit¶esvalidespourlesCSPsur-contraints 71
6.1 Mod?eles lin¶eaires a? base de cliques . . . . . . . . . . . . . . . . . . . . . . . 72
6.1.1 D¶eflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.1.2 Formulation lin¶eaire pour les cliques binaires . . . . . . . . . . . . . 73
6.1.3 Th¶eor?eme fondamental . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2 Un sch¶ema pour la construction de cliques maximales . . . . . . . . . . . . 75
6.3 Utilisation de cliques pour le calcul des bornes inf¶erieures a? base des
compteurs d’arc-consistance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.3.1 Calcul de la borne inf¶erieure WAC optimale . . . . . . . . . . . . . 77c
6.3.2 Utilisation de cliques pour le calcul de la borne RDAC . . . . . . . 80c
6.4 Calcul optimal de bornes inf¶erieures a? base de cliques . . . . . . . . . . . . 80
6.5 Calcul de bornes inf¶erieures a? base de cliques par recherche locale . . . . . 83
6.6 G¶en¶eralisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.6.1 Th¶eorem? e fondamental . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.6.2 Utilisation d’in¶egalit¶es valides pour le pr¶etraitement de WCSP . . . 90
6.7 Exp¶erimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.7.1 Bornes inf¶erieures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.7.2 M¶ethodes de r¶esolution . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
III Application de la Programmation Par Contraintes et de la recherche
locale au problem? e de placement des arr^ets et de la production des
r¶eacteurs nucl¶eaires d’EDF 105
7 Pr¶esentationduprobleme? etdesm¶ethodesder¶esolutionactuellementen
exploitation 107
7.1 Le probl?eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.1.1 Sous-probl?eme de placement des arr^ets . . . . . . . . . . . . . . . . 108
7.1.2 Sous-probl?eme de placement de la production . . . . . . . . . . . . 111
7.1.3 Contrainte de demande et fonction objectif . . . . . . . . . . . . . . 112
7.2 Mod¶elisation math¶ematique du proble?me . . . . . . . . . . . . . . . . . . . 112
7.2.1 Sous-probl?eme de placement des arr^ets . . . . . . . . . . . . . . . . 113
7.2.2 Sous-probl?eme de placement de la production . . . . . . . . . . . . 114
7.2.3 Contrainte de demande et fonction objectif . . . . . . . . . . . . . . 116
vi?CHAPITRE 0. TABLE DES MATIERES
7.3 M¶ethodes de r¶esolution actuellement mises en uvre . . . . . . . . . . . . . 116
7.3.1 R¶esolution du probl?eme a? planning d’arr^ets flg¶e . . . . . . . . . . . 117
7.3.2 R¶esolutionduproble?mehorscontraintesdeplacementinter-sitespar
recherche de