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 trois équipes composant le département couvrent une variété de champs disciplinaires de l’automatique et de l’informatique. Elles partagent certaines particularités comme : être centrées sur des classes de modèles représentant des réalités physiques, fonctionnelles ou organisationnelles que l’on souhaite piloter ; proposer des outils théoriques pour l’analyse des propriétés et performances atteignables ou atteintes ; adosser ces résultats à des méthodes de conception de lois de commandes, de diagnostic ou d’optimisation ; illustrer les résultats 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)
S6 Intelligence artificielle : Représentation des connaissances, formalisation des raisonnements ; Acquisition des connaissances, apprentissage ; Systèmes multi-agents
S6 Calcul arithmétique et formel, codage et cryptologie : Arithmétique des ordinateurs, calcul formel, calcul certifié
S6 Aide à la décision et recherche opérationnelle : Optimisation, programmation mathématique, satisfaction de contraintes ; Décision, choix social, théorie algorithmique des jeux ; Ordonnancement, systèmes de production, logistique
S6 Algorithmique, combinatoire : algorithmique des graphes, théorie des graphes
S7 Automatique : modélisation, analyse, observation, identification, commande, optimisation, prédiction, diagnostic, surveillance, supervision, sûreté de fonctionnement ; systèmes dynamiques continus, discrets, hybrides, en réseau, cyber-physiques, multi-agents
S41 Théorie du contrôle et optimisation
Les membres du département s'inscrivent dans une démarche scientifique commune tout en étant dans des champs disciplinaires distincts de l'automatique et de l'informatique. Nos activités supposent qu'il y a une certaine réalité qui soit physique, logicielle ou organisationnelle, pour laquelle nos méthodes visent à produire des outils de commande ou de décision. Les approches de résolution sʼinscrivent naturellement dans le champ des sciences de lʼinformation, mais empruntent également aux mathématiques appliquées.
Equipes constituant le département
DISCO - Diagnostic, Supervision et Conduite Sa focale principale est le diagnostic. L'équipe se positionne dans le cadre du raisonnement abductif qui, à base de modèles sur les systèmes et de mesures, vise à déduire des connaissances sur les procédés, et en particulier sur les fautes et les défauts. | ![]() |
![]() | MAC - Méthodes et Algorithmes en Commande Sa focale principale est la commande en boucle fermée. L'équipe vise la conception de lois utilisant les mesures pour produire en temps réel des commandes, actions à réaliser sur les systèmes. |
ROC - Recherche Opérationnelle, Optimisation Combinatoire et Contraintes Sa focale principale est l'optimisation combinatoire. L'équipe se positionne dans le cadre du raisonnement déductif qui, supposant un modèle idéal des contraintes, produit des ensembles de décisions cohérentes à réaliser permettant de minimiser/maximiser une fonction objectif. | ![]() |
Méthodologies
Les points forts et communs aux trois équipes sont d'ordre méthodologique. Cinq thématiques 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'évalution du laboratoire en 2019.