Abstract
This paper introduces tight upper bounds for the daily photograph scheduling problem of earth observation satellites. These bounds, which were unavailable until now, allow us to assess the quality of the heuristic solutions obtained previously. These bounds are obtained with a partition-based approach following the “divide and pas conquer” principle. Dynamic programming and tabu search are conjointly used in this approach. We present also simplex-based linear programming relaxation and a relaxed knapsack approach for the problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Battiti and A.A. Bertossi, “Greedy, prohibition, and reactive heuristics for graph partitioning,” IEEE Transactions on Computers, vol. 48, no. 4, pp. 361-385, 1999.
R. Bellman and D. Stuart, Applied Dynamic Programming, Princeton University Press, 1962.
E. Bensana, M. Lemaître, and G. Verfaillie, “Earth observation satellite management,” Constraints, vol. 4, no. 3, pp. 293-299, 1999.
E. Bensana, G. Verfaillie, J.C. Agnse, N. Bataille, and D. Blumstein, “Exact and inexact methods for the daily management of an earth observation satellite,” in Proc. 4th Intl. Symposium on Space Mission Operations and Ground Data Systems, Münich, Germany, 1996.
D. Fayard and G. Plateau, “An algorithm for the solution of the 0-1 knapsack problem,” Computing, vol. 28, pp. 269-287, 1982.
C. Friden, A. Hertz, and D. de Werra, “Stabulus: A technique for finding stable sets in large graphs with tabu search,” Computing, vol. 42, pp. 35-44, 1989.
V. Gabrel, “Improved linear programming bounds via column generation procedure for the daily scheduling of earth observation satellite,” Research Report 99-01, IPN, Paris XIII University, Jan. 1999.
M. Garey and D. Johnson, Computers & Intractability: A Guide to the Theory of NP-Completeness,W.H. Freeman and Company, 1979.
M. Gondran and M. Minoux, Graphes & Algorithmes, Eyrolles, 1985.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, JohnWiley: New York, 1990.
R.M. Nauss, “An efficient algorithm for 0-1 knapsack problem,” Management Science, vol. 23, ppp.27-31, 1976.
W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C, Cambridge University Press: Cambridge, 1992.
E. Rolland, H.P. Pirkul, and F. Glover, “Tabu search for graph partitioning,” Annals of Operations Research, vol. 63, pp. 209-232, 1996.
D.K. Smith, Dynamic Programming: A Practical Introduction, Ellis Horwood, 1990.
M. Vasquez and J.K. Hao, “A logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite,” Journal of Computational Optimization and Applications, vol. 20, pp. 137-157, 2001.
G. Verfaillie, M. Lemaître, and T. Schiex, “Russian doll search for solving constraint optimization problems,” in Proc. 13th National Conference on Artificial Intelligence, Portland, USA, 1996, pp. 182-187.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Vasquez, M., Hao, JK. Upper Bounds for the SPOT 5 Daily Photograph Scheduling Problem. Journal of Combinatorial Optimization 7, 87–103 (2003). https://doi.org/10.1023/A:1021950608048
Issue Date:
DOI: https://doi.org/10.1023/A:1021950608048