1 A Logic-Constrained Knapsack Formulation and a Tabu Algorithm for the Daily Photograph S.pdf

1A Logic-Constrained Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite Michel Vasquez and Jin-Kao Hao * (Submitted to Journal of Computational Optimization and Applications ) Abstract: The daily photograph scheduling problem of earth observation satellites like Spot 5 consists in scheduling a subset of mono or stereo photographs from a set of candidates to different cameras. The scheduling must optimize a cost function while satisfying a large number of constraints. In this paper, we first present a formulation of the problem as a generalized version of the well-known knapsack model, which includes large numbers of logical constraints that bound the sums of pairs and triples of variables. We then develop a tabu search algorithm which integrates some important features. Extensive experiments on a set of large and realistic benchmark instances show the high effectiveness of this approach. Key words: tabu search, heuristics, satellite photograph scheduling, multidimensional knapsack, constrained combinatorial optimization 1. Introduction The daily photograph scheduling problem (DPSP) is one of the key applications for an earth observation satellite like Spot 5. The main purpose of the DPSP is to schedule a subset of photographs from a set of candidate photographs which will be effectively achieved by the satellite. The resulting subset of photographs must satisfy a large number of imperative constraints of different types and at the same time maximize a given cost function. The cost function reflects several criteria like client importance, demand urgency, meteorological forecasts and so on. The constraints include both physical constraints such as the recording capacity on board and logic constraints such as non overlapping trials and minimal transition time between two successive trials on the same camera. This problem is also important and interesting from a complexity point of view. Indeed it can be mode