Show simple item record

dc.contributor.authorGabrel, Virginie
dc.date.accessioned2010-05-06T08:20:27Z
dc.date.available2010-05-06T08:20:27Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4106
dc.description.abstractfrDans 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.
dc.language.isoenen
dc.subjectSatellite Mission Planningen
dc.subject.ddc003en
dc.titleAn extensive comparison of 0-1 linear programs for the daily satellite mission planningen
dc.typeChapitre d'ouvrage
dc.description.abstractenIn this paper, we compare several 0-1 linear programs for solving the satellite mission planning problem. Several heuristics have already been used to solve this difficult combinatorial problem. In order to assess the quality of the obtained approximate solutions, some 0-1 linear formulations have been proposed. Indeed, optimal solution values of linear relaxations provide upper bounds of the optimal solution value. In this paper, we consider two models and explain why one of both systematically compute lower upper bounds. Our explanation is based on stable set polytope formulations for perfect graphs. Then, we propose new upper bounds for some big size benchmark instances. Some improvements are also suggested.
dc.identifier.citationpages319-328en
dc.relation.ispartoftitleCombinatorial optimization and theorical computer science: interfaces and perspectives: 30th anniversary of the LAMSADEen
dc.relation.ispartofeditorPaschos, Vangelis
dc.relation.ispartofpublnameWileyen
dc.relation.ispartofpublcityHoboken NJen
dc.relation.ispartofdate2008
dc.relation.ispartofpages515en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00116717/en/en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-8482-1021-9en


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record