23 sept 2019 · 1 7 1 Résolution du problème dual Lagrangien L'optimisation combinatoire ( ou discrète) est une branche très importante en re- cherche
Previous PDF | Next PDF |
[PDF] Optimisation Combinatoire : Programmation Linéaire et - LIP6
29 sept 2015 · 3 3 Problèmes classiques en optimisation combinatoire 27 du problème En effet , il y a une variable par sommet du graphe et une inégalité par
[PDF] Résolution de problèmes combinatoires et optimisation par - CNRS
Cette méta-heuristique a permis de résoudre différents problèmes d'optimisation combinatoire, comme par exemple le problème du voyageur de commerce [
[PDF] Optimisation combinatoire Concepts fondamentaux - LAMSADE
blèmes d'optimisation combinatoire Celle-ci consiste à ramener un tel problème à la résolution d'un programme linéaire en décrivant l'enveloppe convexe de
[PDF] RECHERCHE OPÉRATIONNELLE : Optimisation Combinatoire
On verra dans le cours que le problème du voyageur de commerce est probablement de complexité exponentielle (il est NP-difficile) Toutefois, il y a des
[PDF] Méthodes doptimisation combinatoire en - MIAT INRA
23 sept 2019 · 1 7 1 Résolution du problème dual Lagrangien L'optimisation combinatoire ( ou discrète) est une branche très importante en re- cherche
[PDF] Optimisation Combinatoire (Méthodes approchées)
Polynomial Vs Exponential Page 17 P = NP ? ○ Classe P: problèmes de décision pour lesquels on connaît des algorithmes polynomiaux
[PDF] Equipe : Optimisation Combinatoire - Cedric-Cnam
pour le problème général de la programmation linéaire en nombres entiers De nombreux problèmes d'optimisation combinatoire peuvent se formuler comme
[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
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èseSimon 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 - INRAToulouse)
Directeur(s) de Thèse :
Simon DE GIVRY,Gauthier QUESNELetMarc TCHAMITCHIANRapporteurs :
Philippe VISMARAetVan-Dat CUNG
À mes parents, mon mari et ma fille Inès.
2Remerciements
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 juryde 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
9Introduction Générale
21Contexte
21Problématique de recherche
21Contributions majeures de la thèse
22Organisation du manuscrit
22I État de l"art
251 Méthodes d"optimisation combinatoire en programmation mathématique
271.1 Introduction
281.2 Programmation linéaire en variables 0-1
281.3 Programmation linéaire mixte
291.4 Programmation quadratique en variables 0-1
291.5 Linéarisation en variables 0-1
291.6 Dualité
301.7 Relaxation Lagrangienne
321.7.1 Résolution du problème dual Lagrangien
331.7.2 Exemple [
Fisher, 1985
351.7.3 Relaxation Lagrangienne vs. relaxation linéaire
371.7.4 Applications de la relaxation Lagrangienne
381.8 Méthodes de résolution
391.8.1 Méthodes exactes
391.8.2 Méthodes approchées
411.8.3 Logiciels d"optimisation
431.9 Conclusion du chapitre
442 Problèmes classiques de partitionnement
472.1 Introduction
482.2 Problèmes de partitionnement
482.2.1 Problème de Set Packing (SSP)
482.2.2 Problème de Set Covering (SCP)
492.2.3 Problème de Set Partitioning (SPP)
492.2.4 Problème de Set Partitioning étendu
502.2.5 Cas particulier : problème des n-reines pondérées
512.3 Méthodes de résolution des problèmes de partitionnement
522.4 Conclusion du chapitre
535
6TABLE DES MATIÈRES
3 Réglage automatique des paramètres des méthodes d"optimisation
553.1 Introduction
563.2 Analyse de sensibilité
573.2.1 Méthode de sensibilité locale : méthode One-At-a-Time (OAT)
583.2.2 Méthode de sensibilité globale qualitative : méthode de Morris
593.2.3 Méthode de sensibilité globale quantitative : méthode de Sobol
603.2.4 Grille de sélection d"une méthode d"analyse de sensibilité
633.3 Réglage automatique des paramètres
663.3.1 Stratégies basées sur des méthodes statistiques
673.3.2 Stratégies basées sur des heuristiques
683.3.3 Récapitulatif des méthodes
693.4 Conclusion du chapitre
71II Algorithme de Wedelin et réglage automatique de ses paramètres 73
4 Algorithme de Wedelin
754.1 Introduction
764.2 Algorithme de Wedelin
764.2.1 Problème
764.2.2 Idée de base : Relaxation Lagrangienne
774.2.3 Étapes de l"algorithme
794.3 Amélioration de l"algorithme de Wedelin
844.4 Difficulté du choix des paramètres
854.5 Généralisation de l"algorithme de Wedelin
874.5.1 Inégalités
874.5.2 Coefficients en-1/0/1. . . . . . . . . . . . . . . . . . . . . . . . . .88
4.6 Conclusion du chapitre
895 Réglage automatique de l"algorithme de Wedelin et ses extensions
915.1 Introduction
925.2 Extensions de l"algorithme
925.2.1 Ordre des contraintes et des variables
925.2.2 (Ré)initialisation de solution
985.2.3 Dépendance du paramètrelavec les coûts réduits. . . . . . . . . . . 102
5.2.4 Traitement des cas particuliers
1055.3 Réglage automatique des paramètres
1065.3.1 Synthèse des paramètres
1065.3.2 Choix des méthodes de réglage
1065.3.3 Protocole de réglage des paramètres
1085.4 Expérimentations
1105.4.1 Instances
1105.4.2 Protocole expérimental du réglage des paramètres
1125.4.3 Comparaison debaryonyxavec d"autres logiciels d"optimisation. . 120
5.5 Conclusion du chapitre
124III Application : Conception des systèmes de verger-maraîcher 125