Aggregation techniques for solving large-scale dynamic programming formulations

Dans cette thèse, nous nous intéressons aux problèmes qui peuvent être formulés comme une séquence de décisions, où la programmation dynamique est un paradigme de modélisation adapté. Pour résoudre des problèmes de grande taille, nous étudions les méthodes d’agrégation et de désagrégation qui nous permettent de construire des relaxations du problème, qui sont résolues pour obtenir des solutions optimistes pour ces problèmes. Des algorithmes itératifs sont ensuite conçus à partir de ces relaxations, où les relaxations fournissent des solutions de moins en moins optimistes à mesure que le nombre d’itérations augmente. Dans cette thèse, nous faisons d’abord une revue de la littérature sur les méthodes d’agrégation et de désagrégation dans le contexte de programmes dynamiques. Ensuite, nous proposons un problème de modélisation de l’agrégation de sommets dans les graphes de décision des programmes dynamiques pour construire des relaxations et montrons que de nombreuses méthodes d’agrégation de la littérature sont des cas particuliers de ce problème. Nous étudions ensuite une application des formulations de flot dans un hypergraphe de décision, et étendons certaines méthodes d’agrégation à ce cas. Pour valider nos approches, nous présentons des résultats expérimentaux sur un ensemble de problèmes différents et les comparons avec des approches similaires de la littérature. Nous concluons cette thèse par une discussion sur les résultats obtenus et proposons des perspectives pour des travaux futurs.