Optimisation sous Incertitudes

Au-delà de l’optimisation déterministe, l’équipe a obtenu des résultats en optimisation sous incertitude et en particulier en optimisation robuste en deux étapes, principalement pour des problèmes d’ordonnancement avec durées incertaines avec un critère minmax. Des méthodes de Benders adversariable et de génération de colonnes et de contraintes ont été conçues et appliquées avec succès pour la première fois à des problèmes d’ordonnancement cyclique et l’apport de la programmation par contraintes dans la méthode de Benders a été démontrée. En plus de ces apports algorithmiques, de nouvelles structures plus flexibles ont été proposées pour la représentation des décisions de la première étape (décisions dite « here-and-now ») : les séquences de groupes de tâches permutables permettent d’améliorer significativement les méthodes d’optimisation robuste et stochastique traditionnelles et une méthode qui exploite les arbres de décision robustes, une structure qui propose en première étape une famille d’ordonnancement, se compare favorablement aux approches réactives standard. Nous avons aussi montré l’intérêt de l’apprentissage par réseaux de neurones en graphes pour l’ordonnancement stochastique et, réciproquement, l’intérêt de l’optimisation robuste pour l’apprentissage automatique équitable. L’optimisation robuste par scénarios a été appliquée avec succès à la conception de microréseaux d’énergie Un autre axe d’étude porte sur l’optimisation des trajectoires pour des systèmes dynamiques soumis aux contraintes déterministes et stochastiques dont un exemple caractéristique est celui de la gestion du risque de collision, en orbite basse, des satellites avec des débris spatiaux. Il s'agit de problèmes d'optimisation sous contraintes probabilistes (Chance Constrained en anglais), dont la résolution requiert des algorithmes rapides et fiables, essentiels à la sécurité des missions. Sous certaines hypothèses simplificatrices, un problème de programmation quadratique non convexe, connu pour être NP-difficile, a été proposé. Des relaxations par programmation semi-définie (randomisation, hiérarchies de Lasserre) ainsi que des méthodes de type Branch & Bound ont été conçues et comparées en termes de performances sur des exemples académiques et réalistes. Une classe plus générale de rencontres à long terme a été étudiée via une approche par scénarios et une nouvelle méthode de relaxation directe, optimisant les manoeuvres d’évitement sous contraintes de probabilité cumulée de collision. Ces approches ont été comparées à une méthode de sélection du risque, plus conservatrice mais numériquement efficace grâce à sa convexité

---