Abstract (FR)

Dans ce papier, nous comparons plusieurs programmes linéaires en variables 0-1 pour résoudre le problème de la planification quotidienne des prises de vue à réaliser par un système d'observation de la Terre par satellite. Plusieurs heuristiques ont déjà été proposées pour résoudre ce problème combinatoire difficile. Afin d'évaluer la qualité des solutions approchées trouvées, il est utile de formuler le problème sous la forme d'un programme linéaire en variables 0-1. En effet, les valeurs des solutions optimales des relaxations continues fournissent des bornes supérieures de la valeur du problème. Dans ce papier, nous considérons deux modèles et nous expliquons pourquoi l'un des deux fournit nécessairement une meilleure borne. Notre démonstration se base sur les représentations du polytope de stable pour les graphes parfaits. Puis, nous calculons ces bornes sur des instances réalistes. Des améliorations encore possibles sont suggérées.