N attribue par la bibliotheque

-

Documents
163 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Publié le 01 avril 2007
Nombre de visites sur la page 78
Langue Français
Signaler un problème

–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 solution autour d’un planning initial . . . . . . . . . . 117
7.3.3 R¶esolution du proble?me globalpar recherche de solution autour d’un
planning initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8 Contributions 119
8.1 Am¶elioration de la mod¶elisation math¶ematique de contraintes de placement
intra-site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.2 Mod¶elisation et r¶esolution du sous-probl?eme de placement des arr^ets par
Programmation Logique par Contraintes . . . . . . . . . . . . . . . . . . . 122
8.2.1 Programmation Logique par Contraintes . . . . . . . . . . . . . . . 122
8.2.2 Mod¶elisation du probl?eme . . . . . . . . . . . . . . . . . . . . . . . 123
8.3 R¶esolution du problem? e global hors criter? e de cout^ . . . . . . . . . . . . . . 127
8.3.1 Propagation des contraintes de production . . . . . . . . . . . . . . 127
8.4 R¶esolution du probl?eme global avec prise en compte d’un criter? e de cout^ . 131
8.4.1 Recherche de solutions minimisant un crit?ere heuristique de cou^t . . 131
8.4.2 Outil pour la Satisfaction et l’Optimisation du Proble?me des Arr^ets
Nucl¶eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.5 Exp¶erimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.5.1 R¶esolution du proble?me global hors crit?ere de cou^t . . . . . . . . . . 136
8.5.2 Optimisation du crit?ere heuristique de cout^ . . . . . . . . . . . . . . 137
8.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9 Conclusion et perspectives 141
Table des flgures 145
Bibliographie 147
viiChapitre 1
Introduction
La Programmation Par Contraintes (PPC) et la Programmation Math¶ematique (PM) sont
deux paradigmes utilis¶es pour la satisfaction ou l’optimisation de syst?emes de contraintes. Ils
renfermentdestechniquesquipeuvent^etrecombin¶eespour¶elaborerdesm¶ethodesder¶esolution
de ces proble?mes.
Dans le cadre de la satisfaction, un syst?eme de contraintes est d¶eflni par un ensemble de
variables ayant chacune un domaine de valeurs possibles et par un ensemble de contraintes.
Chaque contrainte est d¶eflnie sur un sous-ensemble de variables. Elle exprime une condition
que ces variables doivent satisfaire. Une solution du syste?me est une afiectation des variables
qui satisfait la conjonction de toutes les contraintes. Le probl?eme de satisfaction de contraintes
(ouCSPpourConstraintSatisfactionProblem)quiconsistea?chercherunetellesolutionestun
proble?me central de la Programmation Par Contraintes (PPC). Son formalisme ofire un outil
de mod¶elisation simple et g¶en¶eral, utilis¶e dans de nombreux domaines : conflguration, gestion
et allocation de ressources, ordonnancement, emploi du temps,...
En PPC, la plupart des m¶ethodes e–caces de r¶esolution de CSP utilisent la technique de
propagation de contraintes qui vise a? transformer un CSP en un autre CSP ¶equivalent et plus
simple a? r¶esoudre. Pour cela, elles rel^achent la consistance globale qui impose de satisfaire la
conjonction de toutes les contraintes du syst?eme et s’int¶eressent a? des consistances locales de
contraintespourextrairerapidementdesinformationsvalidesetutilespourlar¶esolutionglobale
du problem? e. Les informations extraites sont souvent de type "telle afiectation (souvent d’une
seule variable) ne peut pas ^etre contenue dans une solution du problem? e". Il s’agit du flltrage
ou de la r¶eduction du probl?eme.
Dans beaucoup d’applications r¶eelles, comme c’est le cas pour le probl?eme de placement
¶des arr^ets et de la production des r¶eacteurs nucl¶eaires d’Electricit¶e de France (EDF) que nous
abordons dans cette th?ese, le but n’est pas seulement de trouver une solution qui satisfait
un syst?eme de contraintes mais une solution qui soit de plus de bonne qualit¶e. La qualit¶e
d’unesolutionestd¶etermin¶eeparuneapplication,appel¶eefonctionobjectif,quiassociea? toute
1CHAPITRE 1. INTRODUCTION
solution une valuation. Ces probl?emes sont des probl?emes de satisfaction de contraintes et
d’optimisation (ou CSOP pour Constraint Satisfaction and Optimisation Problem).
Dans d’autres applications, les contraintes peuvent ^etre antagonistes dans le sens ou? la
satisfaction de certaines d’entre elles ne peut se faire qu’au d¶etriment de la violation d’autres. Ce
sont des CSP qui ne posse?dent pas de solutions. Dans ce cas, il devient int¶eressant
d’associer
desvaluationsauxcontraintespourexprimerleursimportancesetchercherunesolutionquiminimiselasommedesvaluationsdescontraintesnonsatisfaites.C’estleprobl?emedesatisfaction
de contraintes valu¶ees (ou VCSP pour Valued Constraint Satisfaction Problem).
L’algorithmeleplusutilis¶epourl’optimisationdesyst?emesdecontraintes(CSOPouVCSP)
est l’algorithme de s¶eparation et ¶evaluation (branch and bound, B&B). C’est un algorithme
?exact qui garantit de construire une meilleure solution. A chaque ¶etape de la construction, il
essaye d’¶etendre une afiectation d’un sous-ensemble des variables (initialement vide) vers une
afiectation de toutes les variables. L’e–cacit¶e du B&B d¶epend grandement de la qualit¶e de la
borne inf¶erieure calcul¶ee en chaque¶etape de la construction. Cette borne inf¶erieure est calcul¶ee
pour estimer le cou^t d’une meilleure solution qu’on peut obtenir si on ¶etend une afiectation
d’un sous-ensemble de variables vers une afiectation de toutes les variables.
En PPC, la plupart des m¶ethodes e–caces de calcul de bornes inf¶erieures se basent sur la
notion de consistance locale. La principale di–cult¶e a? laquelle se heurtent ces m¶ethodes est la
priseencomptedemani?ereglobaledetouteslescontraintes.EnPM,d’autresbornesinf¶erieures
sont utilis¶ees comme les bornes obtenues par la relaxation continue ou la relaxation
Lagran( )gienne Geofirion, 1974 . Dans le calcul de ces bornes, les contraintes sont prises en compte
de mani?ere globale. Dans le cas de la relaxation continue c’est l’int¶egralit¶e des variables qui
est rel^ach¶ee. Dans le cas de la relaxation Lagrangienne, les contraintes relac^ h¶ees sont inject¶ees
dans l’objectif pour qu’elles soient satisfaites au mieux. Les relaxations Lagrangienne et
continue sont souvent aussi exploit¶ees dans le cadre de recherche d’in¶egalit¶es valides permettant de
( ) ( )"st¶eriliser"des n uds du B&B Aardal et van Hoesel, 1996 Aardal et van Hoesel, 1999 .
Plusieurs travaux ont montr¶e l’int¶er^et de faire coop¶erer les approches de la PPC et de la
( ) ( ) ( ) (PM Darby-Dowman et al., 1997 Hooker et Osorio, 1999 Hooker et al., 2000 Sellmann,
) ( ) ( ) ( )2004 Focacci et al., 1999 Benoist et al., 2002 Demassey et al., 2005 . Une des mani?eres
int¶eressante de b¶en¶eflcier des avantages des deux techniques est l’utilisation des contraintes
( )globales d’optimisation Focacci et al., 2002 . Ce sont des contraintes qui servent a? formuler
de mani?ere concise certaines parties d’un probl?eme et aux quelles sont associ¶es des algorithmes
de flltrage e–caces. Ces algorithmes sont souvent issus de la PM et exploitent les structures
particuli?eres des contraintes et de la fonction objectif. Cependant, reconna^‡tre des
structures
int¶eressantesdansunsyst?emedecontraintesn’estpastoujoursunet^ache¶evidenteetiln’existe
pasdetechniqueuniverselleetautomatiquepourlefaire.Ilappara^‡talorsint¶eressantdeproposerdestechniquesg¶en¶eriquesquib¶en¶eflcientlepluspossibledesavantagesdesoutilsdelaPPC
et de ceux de la PM. La compr¶ehension des liens existant entre les deux domaines faciliterait
2