[PDF] Méthodes doptimisation combinatoire en programmation

View - Download Méthodes doptimisation combinatoire en programmation

Previous PDF

Next PDF

THÈSE

THÈSE

En vue de l"obtention du

DOCTORAT DE L"UNIVERSITÉ DE TOULOUSE

Délivré par :l"Université Toulouse 3 Paul Sabatier (UT3 Paul Sabatier)Présentée et soutenue le23/09/2019par :

???? ??????Méthodes d"optimisation combinatoire en programmation mathématique. Application à la conception des systèmes de verger-maraîcherJURY Marie-Jo HuguetProfesseure des universités Présidente Philippe VISMARAProfesseur des universités Rapporteur Van-Dat CUNGProfesseur des universités Rapporteur Lakhdar SAISProfesseur des universités Examinateur Marc TCHAMITCHIANDirecteur de recherche Membre invité Gauthier QUESNELChargé de recherche Co-directeur de thèse

Simon DE GIVRYChargé de recherche HDR Directeur de thèseÉcole doctorale et spécialité :

MITT : Domaine STIC : Intelligence Artificielle

Unité de Recherche :

Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT - INRA

Toulouse)

Directeur(s) de Thèse :

Simon DE GIVRY,Gauthier QUESNELetMarc TCHAMITCHIAN

Rapporteurs :

Philippe VISMARAetVan-Dat CUNG

À mes parents, mon mari et ma fille Inès.

2

Remerciements

Je voudrais tout d"abord remercier grandement mon directeur de thèse Simon DE GIVRY d"avoir dirigé ma thèse avec une forte implication et une grande disponibilité. Je lui re- mercie également pour ses qualités humaines d"écoute et de compréhension. Je remercie aussi mes co-directeurs de thèse Gauthier QUESNEL et Marc TCHAMIT- CHIAN pour leurs aides précieux, leurs conseils pertinents et leurs suggestions toujours avisées. Mes remerciements vont également aux rapporteurs Philippe VISMARA et Van-Dat CUNG de m"avoir fait l"honneur d"une lecture détaillée et rigoureuse de mon manuscrit de thèse. leurs remarques, commentaires et propositions d"améliorations m"ont permis de prendre du recul sur mon travail. J"exprime aussi ma profonde reconnaissance à Marie-Jo HUGUET, présidente du jury

de thèse, et Lakhdar SAIS pour l"intérêt qu"ils ont porté à mes travaux en examinant mon

manuscrit de thèse. Merci également à Robert FAIVRE et Victor PICHENY pour leur aide sur la partie de l"analyse de sensibilité. Merci à tout le personnel de l"unité MIAT : le directeur pour sa flexibilité et son bon sens de l"humour, les gestionnaires administratifs (Fabienne, Nathalie et Alain) pour leur grande serviabilité, mes collègues de bureau (Charlotte, Alyssa et Léonard) pour leur sou- tien aux moments difficiles, et toutes autres personnes dont les permanents, les CDD, les anciens et futurs docteurs ainsi que les stagiaires pour les échanges amicaux et le partage des savoirs scientifiques tout au long de ces formidables années de thèse. Je tiens à remercier le MINISTÈRE DE L"ENSEIGNEMENT SUPÉRIEUR ET DE LA RECHERCHE qui a financé cette thèse en m"accordant un poste de Doctorant Contractuel Chargé d"Enseignement, puis d"Attachée Temporaire d"Enseignement et de la Recherche. Je tiens également à remercier mes amis et mes collègues à l"UT2J qui m"ont apporté leur soutien moral pendant la phase dure de la rédaction du manuscrit. Mes remerciements les plus chaleureux vont aussi à ma famille, en particulier à mes parents, toujours présents pour soutenir mes ambitions et m"aider à réaliser mon rêve de décerner le grade de Docteur. Je remercie également mon cher époux pour son soutien quotidien, ses encouragements et sa patience. Gérer deux projets scientifiques en tant que thésards avec la naissance de notre fille Inès n"était pas facile pour nous. 3 4 Sans oublier Ghizlane, qui s"est déplacée plusieurs fois en France pour m"aider à garder ma petite lors de la rédaction du manuscrit. Je lui adresse toute ma gratitude.

Table des matières

Table des matières

9

Introduction Générale

21

Contexte

21

Problématique de recherche

21

Contributions majeures de la thèse

22

Organisation du manuscrit

22

I État de l"art

25

1 Méthodes d"optimisation combinatoire en programmation mathématique

27

1.1 Introduction

28

1.2 Programmation linéaire en variables 0-1

28

1.3 Programmation linéaire mixte

29

1.4 Programmation quadratique en variables 0-1

29

1.5 Linéarisation en variables 0-1

29

1.6 Dualité

30

1.7 Relaxation Lagrangienne

32

1.7.1 Résolution du problème dual Lagrangien

33

1.7.2 Exemple [

Fisher, 1985

35

1.7.3 Relaxation Lagrangienne vs. relaxation linéaire

37

1.7.4 Applications de la relaxation Lagrangienne

38

1.8 Méthodes de résolution

39

1.8.1 Méthodes exactes

39

1.8.2 Méthodes approchées

41

1.8.3 Logiciels d"optimisation

43

1.9 Conclusion du chapitre

44

2 Problèmes classiques de partitionnement

47

2.1 Introduction

48

2.2 Problèmes de partitionnement

48

2.2.1 Problème de Set Packing (SSP)

48

2.2.2 Problème de Set Covering (SCP)

49

2.2.3 Problème de Set Partitioning (SPP)

49

2.2.4 Problème de Set Partitioning étendu

50

2.2.5 Cas particulier : problème des n-reines pondérées

51

2.3 Méthodes de résolution des problèmes de partitionnement

52

2.4 Conclusion du chapitre

53
5

6TABLE DES MATIÈRES

3 Réglage automatique des paramètres des méthodes d"optimisation

55

3.1 Introduction

56

3.2 Analyse de sensibilité

57

3.2.1 Méthode de sensibilité locale : méthode One-At-a-Time (OAT)

58

3.2.2 Méthode de sensibilité globale qualitative : méthode de Morris

59

3.2.3 Méthode de sensibilité globale quantitative : méthode de Sobol

60

3.2.4 Grille de sélection d"une méthode d"analyse de sensibilité

63

3.3 Réglage automatique des paramètres

66

3.3.1 Stratégies basées sur des méthodes statistiques

67

3.3.2 Stratégies basées sur des heuristiques

68

3.3.3 Récapitulatif des méthodes

69

3.4 Conclusion du chapitre

71
II Algorithme de Wedelin et réglage automatique de ses paramètres 73

4 Algorithme de Wedelin

75

4.1 Introduction

76

4.2 Algorithme de Wedelin

76

4.2.1 Problème

76

4.2.2 Idée de base : Relaxation Lagrangienne

77

4.2.3 Étapes de l"algorithme

79

4.3 Amélioration de l"algorithme de Wedelin

84

4.4 Difficulté du choix des paramètres

85

4.5 Généralisation de l"algorithme de Wedelin

87

4.5.1 Inégalités

87

4.5.2 Coefficients en-1/0/1. . . . . . . . . . . . . . . . . . . . . . . . . .88

4.6 Conclusion du chapitre

89

5 Réglage automatique de l"algorithme de Wedelin et ses extensions

91

5.1 Introduction

92

5.2 Extensions de l"algorithme

92

5.2.1 Ordre des contraintes et des variables

92

5.2.2 (Ré)initialisation de solution

98

5.2.3 Dépendance du paramètrelavec les coûts réduits. . . . . . . . . . . 102

5.2.4 Traitement des cas particuliers

105

5.3 Réglage automatique des paramètres

106

5.3.1 Synthèse des paramètres

106

5.3.2 Choix des méthodes de réglage

106

5.3.3 Protocole de réglage des paramètres

108

5.4 Expérimentations

110

5.4.1 Instances

110

5.4.2 Protocole expérimental du réglage des paramètres

112

5.4.3 Comparaison debaryonyxavec d"autres logiciels d"optimisation. . 120

5.5 Conclusion du chapitre

124
III Application : Conception des systèmes de verger-maraîcher 125

6 Concepts généraux sur la conception des systèmes de vergers-maraîchers

127

6.1 Introduction

128

6.2 Propriétés des systèmes agroforestiers

130

TABLE DES MATIÈRES7

6.2.1 Interactions écologiques entre arbres et cultures

130

6.2.2 Productivité des systèmes agroforestiers

134

6.2.3 Organisation du travail

136

6.2.4 Rotation des cultures

137

6.3 Méthodes de recherche opérationnelle pour la planification des cultures

139

6.4 Conclusion du chapitre

141

7 Modélisation et résolution du problème de verger-maraîcher

143

7.1 Introduction

144

7.2 Modélisation du problème

144

7.2.1 Choix et caractéristiques des arbres fruitiers

144

7.2.2 Choix et caractéristiques des cultures maraîchères

149

7.3 Formulation mathématique

152

7.3.1 Modèle quadratique en variables binaires (BQP)

152

7.3.2 Modèle linéaire en variables mixtes (MIP)

156

7.3.3 Modèle linéaire en variables binaires

161

7.4 Résultats et discussions

164

7.4.1 Choix des instances du problème de conception de verger-maraîcher

164

7.4.2 Protocole expérimental

165

7.4.3 Discussion et visualisation des solutions

170

7.5 Conclusion du chapitre

173

Conclusion Générale et perspectives

175

Annexe

177

8TABLE DES MATIÈRES

Liste des figures

1.1 La forme de la fonctionL(λ)pour m=1 et T=4. (Exemple tiré de [Fisher, 2004])34

1.2 La fonctionL(λ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

1.3 Classification des méthodes d"optimisation

39

1.4 Illustration d"une itération de l"algorithme de décomposition de Benders.

42

1.5 Schéma général d"un algorithme génétique.

44

2.1 Illustration d"une combinaison de 8 reines non menacées.

52

3.1 Exemple de trajectoires de Morris pour deux variables d"entrée continues

définies sur[0,1]2, avec une discrétisation enQ= 8niveaux. Un total de r= 6trajectoires passant par les noeuds d"une grille régulière superposée sur le carré. Le pas de déplacement estδ= 1/7. La direction de la flèche indique le sens du déplacement [

Faivre et al., 2013

59

3.2 Exemple du graphique de Morris obtenu avec 130 simulations pour 12 va-

riables d"entrée [quotesdbs_dbs13.pdfusesText_19

[PDF] tony buzan booster sa mémoire pdf

[PDF] ouverture numérique d'une fibre optique demonstration

[PDF] avc echelle fast

[PDF] vite avc

[PDF] question a poser pour detecter un avc

[PDF] fast avc

[PDF] référentiel de certification de la visite médicale

[PDF] leem

[PDF] nouvelle charte visite medicale 2017

[PDF] mathématique appliquée ? la finance pdf

[PDF] theoreme de bezout methode

[PDF] faire fonctionner un algorithme a la main

[PDF] ecrire un algorithme a la main

[PDF] expliquer les pourcentages en cm2

[PDF] les besoins nutritionnels de l'homme cours