Méthodes d’agrégation et désagrégation de programmes linéaires en nombres entiers

Abstract

Dans cette thèse, nous nous intéressons à des problèmes pouvant se formuler sous la forme d’un programme dynamique et de contraintes linéaires additionnelles. Pour résoudre ces problèmes, des méthodes itératives d’agrégation de l’espace d’états ont été utilisées dans la littérature. Nous proposons un formalisme générique pour ces méthodes. Nous avons identifié une structure commune aux différentes méthodes, et mis en avant leurs ingrédients principaux. Le but de ce formalisme est d’unifier ces méthodes et de montrer les points clés pour que ces méthodes puissent être développées plus facilement pour de nouveaux problèmes. Pour permettre à ces méthodes d’être compétitives, plusieurs problématiques doivent être résolues : quelle relaxation choisir, quel espace d’état, comment raffiner la relaxation à chaque itération, quelle méthode de résolution choisir pour les relaxations, ... La difficulté de ces problématiques réside dans le fait que ces choix dépendent fortement du problème. Nous proposons des éléments qui peuvent être utilisés de manière générique, et d’autres spécifiques aux problèmes étudiés. Pour valider notre approche, nous avons appliqué l’une d’elles sur le problème de sac-à- dos temporel. La méthode Successive Sublimation Dynamic Programming a montré des résultats compétitifs avec la littérature, notamment grâce à un choix de dimension basé sur l’évolution du réseau, une énumération partielle des décisions possibles à chaque état et différents tests de dominances et de faisabilités. Nous comparons dans un deuxième temps les performances de notre implémentation générique avec une implémentation spécialisée sur ces problèmes. Enfin, ces méthodes ont été confrontées à un problème industriel moins classique : un problème d’utilisation de traitements phytosanitaires sur des vignes dans lequel les sous-problèmes peuvent être formulés comme des programmes dynamiques de grande taille.