A "logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite

The daily photograph scheduling problem of earth observation satellites suc h as Spot 5 consists of scheduling a subset of mono or stereo photographs f rom a given set of candidates to different cameras. The scheduling must max imize a profit 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 b inary and ternary "logical" constraints. We then develop a tabu search algo rithm which integrates some important features including an efficient neigh borhood, a dynamic tabu tenure mechanism, techniques for constraint handlin g, intensification and diversification. Extensive experiments on a set of l arge and realistic benchmark instances show the effectiveness of this appro ach.