Décision et Optimisation
Responsable: Dimitri PEAUCELLE
Résumé de l’activité du département
Le département "Décision et Optimisation" mène des activités de recherche théoriques et méthodologiques pour la conception de lois mathématiques et de techniques algorithmiques servant à la commande et à la décision. Les quatre équipes composant le département couvrent une variété de champs disciplinaires de l’automatique, de l’informatique et des mathématiques appliquées. Elles ont en commun d'associer intimement les questions de décision et d'optimisation. Pour POP et ROC l'optimisation (polynomiale et combinatoire respectivement) est la thématique centrale et se décline en méthodes pour la décision. Pour DISCO et MAC la décision (diagnostic et commande respectivement) est la thématique centrale et s'appuie le plus souvent sur des outils d'optimisation. Si les recherches sont principalement théoriques et méthodologiques, le département s'fforce de les illustrer sur des exemples d’applications fournis par des partenaires extérieurs qui dans l’échange alimentent les équipes en problématiques nouvelles.
![]() |
Mots-clés (issus des sections du Comité national)
S06 Recherche opérationnelle et science de la décision : Optimisation discrète, programmation mathématique, satisfaction de contraintes ; Ordonnancement, logistique ; Choix social computationnel, théorie algorithmique des jeux, systèmes multi-agents
S06 Intelligence artificielle et sciences des données : Gestion des données complexes : données (semi-)structurées, graphes, réseaux sociaux ; Apprentissage automatique, fouille de données ; Ingénierie des connaissances, web sémantique, recherche d'information ; Représentation des connaissances, raisonnement
S06 Algorithmique et structures discrètes : Algorithmique, algorithmes d’approximation, algorithmes probabilistes ; Algorithmique distribuée ; Complexité ; Combinatoire, théorie des graphes
S06 Calcul : Arithmétique des ordinateurs ; Calcul formel ; Calcul à haute performance
S07 Automatique : Modélisation, identification, observation, commande, optimisation ; Diagnostic, sûreté et sécurité des systèmes ; Systèmes dynamiques dont les systèmes cyber-physiques, les systèmes en réseau et les systèmes multi-agents
S07 Intelligence artificielle et sciences des données : Apprentissage automatique et statistique ; Optimisation ; IA en interaction avec les signaux et les systèmes ; Données : physiques, perceptuelles, multimodales, structurées, en grande dimension
S41 Géométrie algébrique ; Systèmes dynamiques et équations différentielles ordinaires, équations aux dérivées partielles ; Théorie du contrôle et optimisation, théorie des jeux.
Equipes constituant le département
DISCO - Diagnostic, supervision et conduite Méthodes pour la décision de type diagnostic, supervision et pronostic En ayant recours à l'optimisation sous forme d'apprentissage, d'optimisation combinatoire et d'optimisation convexe Applications dans les secteurs de l'industrie du futur, de la santé, de l'énergie, en aérospatial, en agriculture | ROC - Recherche opérationnelle, optimisation combinatoire et contraintes Méthodes pour l'optimisation combinatoire, sous contraintes, dont méthodes hybrides Les méthodes permettent des prises de décisions de type ordonnancement, planification, apprentissage Applications dans les secteurs du transport, de l'industrie du futur, du spatial, de l'énergie |
MAC - Méthodes et algorithmes en commande Méthodes pour la décision de type commande en boucle fermée, observation des systèmes et contrôle optimal En ayant recours à l'optimisation convexe, aux LMIs, résultats sous formes de hiérarchies et recherche de certificats Applications dans les secteurs de l'aérospatial, des convertisseurs électriques, pour des robots, en santé et biotechnologies |
Méthodes pour l'optimisation convexe, polynomiale, sur les moments et sous forme de hiérarchies Les méthodes permettent des prises de décisions de type contrôle, apprentissage, commande, certification Applications dans les secteurs es réseaux électriques, des phénomènes quantiques et pour les réseaux de neurones |
Méthodologies
Les points forts et communs aux quatre équipes sont d'ordre méthodologique. Cinq thématiques identifiées à l'occasion du bilan fait en 2019 illustrent à nos yeux la démarche scientifique que nous avons en commun :
Elles décrivent un continuum allant des résultats théoriques jusqu'aux produits sous forme de codes informatiques. La plupart des contributions scientifiques de DO émargent à plus d'une de ces cinq thématiques. Nous visons en effet à associer systématiquement des outils algorithmiques ou numériques efficaces pour les problèmes abordés dans leur grande généralité. Et inversement, les résultats théoriques sont formulés de telle sorte que des outils, principalement d'optimisation, puissent y être associés. La théorie est envisagée dans la mesure où elle conduit à des solutions pratiques pour des applications issues de collaborations avec des partenaires, industriels ou autres.
Dans la suite on donne quelques références qui sont à titre d'illustration. Elles ne reflètent qu'une petite partie des publications du département.
Certificats
Dans les processus de prise de décision et d'optimisation, l'objectif principal réside dans la capacité à garantir des propriétés (stabilité, performance, robustesse, sécurité, tolérance, convergence d'algorithme, borne minimisée sur les erreurs de calculs ...) qui sont difficiles, voire impossible à satisfaire directement ou analytiquement. La démarche scientifique dans le périmètre du département DO consiste à développer des moyens indirects qui vont permettre de garantir la propriété souhaitée ou au moins un avatar de celle-ci suffisamment représentatif. Ces moyens peuvent se regrouper sous la terminologie certificat : outil mathématique ou algorithmique pour garantir une propriété ou une borne sur une propriété. On distingue ainsi dans les travaux menés par DO et suivant les propriétés à certifier : des certificats de solutions (existence/caractérisation) ; des certificats de propriétés asymptotiques (stabilité et autres) ; des certificats de satisfaction de contraintes ; des certificats de complexité. Parmi les résultats significatifs en ce sens dans les dernières années on trouve :
- Diagnosticabilité fonctionnelle et liens avec l'identifiabilité, hal-01198408, hal-01701564
- Diagnosticabilité et le diagnostic de motifs de fautes, hal-01847155, hal-01574475
- Stabilité asymptotique via une fonction de Lyapunov hybride, hal-01526331, hal-01700168, hal-01474407
- Stabilité pour la dimension infinie, hal-01109796, hal-01448483, hal-01643321
- S-variables, un certificat utile en analyse robuste et pour la synthèse, hal-01760625, hal-01851202
- Synchronisation et consensus, hal-01324150, hal-00932841, hal-01576615
- Commande optimale: application au guidage pour le rendez-vous spatial, hal-01078528, hal-01484764
- Caractérisation de domaines d'attraction, hal-01818954, hal-02025286, hal-01995607
- Complexité de problèmes combinatoires, hal-01529299, hal-01023267, hal-01974431
- Certificat polynomial pour les Problèmes de Satisfaction de Contraintes (CSP) conservatifs, hal-01413124, hal-01230681
- "Kernelization" pour la propagation de contraintes, hal-01873503, hal-01670318
- Garanties d'approximation, hal-01354589, hal-02074379
Hiérarchies
Afin d'évaluer la performance (stabilité, bornes sur des énergies) de systèmes d'ingénierie, on se confronte souvent à des problèmes de décision (inégalités à satisfaire, optimisation) difficiles (dans des espaces de dimension infinie et/ou présentant des non-linéarités et/ou non-convexités). On peut alors concevoir des hiérarchies de problèmes plus simples (dans des espaces de dimension finie et/ou linéaires et/ou convexes) dont les solutions peuvent converger dans un certain sens vers la solution du problème original. Par hiérarchie convergente ou hiérarchie complète, on entend une famille de problèmes dont la taille (nombre de variables) croit de manière contrôlée, en fonction d'un indice (un nombre entier croissant, par exemple le degré d'un polynôme), et dont les solutions deviennent arbitrairement proches de la performance évaluée lorsque l'indice tend vers l'infini. Quand on ne dispose pas de preuve de convergence, mais uniquement d'une amélioration de performance prouvée ou observée expérimentalement, on parle de hiérarchie incomplète.
Parmi les résultats significatifs en termes de hiérarchies dans les dernières années on trouve :
- Placement de faisceaux pour les satellites, hal-02066101, hal-01231332
- Fonctions de conversion d'énergie, hal-01444317
- Etudes polyédrales de problèmes d'ordonnancement cumulatifs, hal-01461447, hal-01977452
- Formulations étendues en optimisation combinatoire, hal-01163925, hal-01816861
- Approximation par polynômes homogènes, hal-00785158
- Plan d'expérience optimal, hal-01483490
- Régions d'attraction, hal-00723019
- Systèmes à retards, couplage EDO-EDP, hal-01548256, hal-01566455
- Diagnosticabilité des systèmes hybrides, hal-01676931
- Solutions rigoureuses d'EDO, hal-01526272
Gestion des incertitudes
Dans le département DO, la prise en compte des incertitudes est essentiellement orientée vers (a) la commande, (b) l'estimation de paramètres et le diagnostic de systèmes dynamiques et (c) l'optimisation continue et combinatoire. L'ensemble des valeurs possibles des paramètres incertains (l'ensemble d'incertitudes) est généralement défini par un ou plusieurs modèles mathématiques. L'enjeu est alors de proposer des méthodes de résolution du problème prenant en compte ces modèles d'incertitude. Il faut noter que dans tous les problèmes posés, les incertitudes sont présentes en entrée dans les données (paramètres incertains) mais se trouvent également parfois en sortie dans la solution avec possiblement différents modèles d'incertitudes : en commande robuste, des paramètres peuvent être à incertitudes ellipsoïdales alors que l'on cherche en sortie à évaluer ou minimiser la norme H-infini du système ; en estimation ensembliste, on peut ainsi avoir des incertitudes sous la forme d'intervalles sur les erreurs de mesure en entrée, et une estimation des paramètres en sortie plus fine, par exemple sous la forme de zonotopes ; en optimisation, une erreur de mesure sur un paramètre d'entrée peut être à norme infinie bornée alors que la solution peut être encadrée par un polytope avec un objectif visant à minimiser sa taille.
Parmi les résultats significatifs en termes de gestion des incertitudes dans les dernières années on trouve :
- Incertitudes en commande des systèmes dynamiques, hal-01109796, hal-01760567, hal-01851202, hal-01713146, hal-01509787, hal-01096851
- Incertitudes en estimation et diagnostic des systèmes dynamiques, hal-01970882, hal-01132149, hal-01966316, hal-01930370, hal-01739540, hal-01229083
- Incertitudes en optimisation continue et combinatoire, hal-01487006, hal-01078508, hal-01875889, hal-01635856, hal-01974431, hal-01954509
Méthodes computationnelles
La conception de méthodes algorithmiques efficaces et effectives est un objectif commun du département. Les algorithmes issus des recherches menées dans le département ont permis des progrès significatif dans de nombreux domaines de l'Automatique, de l'Intelligence Artificielle et de la Recherche Opérationnelle. En particulier, des approches computationnelles ont été proposées dans trois grandes catégories de problèmes : les problèmes d'optimisation ; de diagnostic et de commande ; d'apprentissage.
Parmi les résultats significatifs en termes de méthodes computationnelles dans les dernières années on trouve :
- Calcul de bornes primales et duales en optimisation combinatoire, hal-01163925, hal-01614391, hal-01880025
- Renforcement de l'inférence déductive de solveurs de programmation par contraintes, hal-01579781, hal-01546131, hal-01023267
- Hybridation entre la PLNE et la PPC, hal-01234466 et entre la PPC et la satisfiabilité booléenne, hal-01229050, hal-01873500
- Reformulation d'une instance du problème de programmation linéaire ou quadratique en variables 0-1 instance du problème MAX-CUT, hal-01154698 et de jeux combinatoires tels les jeux octaux, hal-01418153
- Méthodes heuristiques en diagnostic actif, hal-02056090 ou pour la synthèse de correcteurs par retour de sortie, hal-01970884
- Architectures décentralisée/distribuées, hal-01760482, hal-01579467
- Estimation de paramètres dans les EDP, hal-01352772
- Algorithme de diagnostic de décalages événementiels et temporels pour les systèmes d'événements temporisés, hal-01534552
- Diagnostic incrémental qui détermine la séquence de tests et de mesures pour localiser le défaut, hal-01400360
- Algorithme pour le rendez-vous spatial, hal-01484764
- Classification non supervisée, hal-01998674, hal-02004417
- Apprentissage supervisé, hal-01998620, hal-01726292
- Arithmétique en nombres flottants, hal-01351529, hal-01111551, hal-00957379
Codes et applications
Le département DO dispose d'une grande variété de productions logicielles. Les outils logiciels résolvent des problèmes génériques : ils sont distribués librement ou font l'objet de projet de maturation (notamment avec Toulouse Tech Transfer (TTT)). Le département produit également des développements dédiés à des applications : la recherche au sein de DO étant orientée sur des classes de modèles, des problèmes génériques, le spectre des applications étudiées est très large et implique différents types d'industries ou de sociétés de services.
Bilan / Prospectives 2019
Pour en savoir plus sur le département DO, vous pouvez consulter le document de Bilan et prospectives élaboré pour l'évaluation du laboratoire en 2019.