A “Logic-Constrained” Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite
Open accessThe DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Glover, F., & Laguna, M. (1997) · Cited by 5,679
Knapsack Problems: Algorithms and Computer Implementations
Connolly, D., Martello, S., & Toth, P. (1991) · Journal of the Operational Research Society · doi:10.2307/2583458 · Cited by 3,120
Glover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001 · cited 4×
“Two other important ingredients of TS are intensification and diversification [Glover & Laguna 97].”
BackgroundMethodResultInfluentialA Genetic Algorithm for the Multidimensional Knapsack Problem
Chu, P. C., & Beasley, J. E. (1998) · Journal of Heuristics · doi:10.1023/a:1009642405419 · Cited by 828
Critical Event Tabu Search for Multidimensional Knapsack Problems
Glover, F., & Kochenberger, G. A. (1996) · Springer eBooks · doi:10.1007/978-1-4613-1361-8_25 · Cited by 189
An efficient tabu search approach for the 0–1 multidimensional knapsack problem
Hanafi, S., & Fréville, A. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00296-8 · Cited by 186
Russian doll search for solving constraint optimization problems
Verfaillie, G., Lemaître, M., & Schiex, T. (1996) · HAL · Cited by 171
A heuristic solution procedure for the multiconstraint zero-one knapsack problem
Pirkul, H. (1987) · Naval Research Logistics (NRL) · doi:10.1002/1520-6750(198704)34:2<161::aid-nav3220340203>3.0.co;2-a · Cited by 166 · cited 2×
“Note that since we have only one knapsack constraint, the relaxation handling is much simpler compared with the techniques used for the MKP [Pirkul 87, Glover & Kochenberger 96, Hanafi et al. 96, Hanafi & Fréville 98].”
MethodEarth Observation Satellite Management
Bensana, E., Lemaitre, M., & Verfaillie, G. (1999) · Constraints · doi:10.1023/a:1026488509554 · Cited by 161
Solving zero-one mixed integer programming problems using tabu search
Løkketangen, A., & Glover, F. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00295-6 · Cited by 137
Research works printed but not linked: 2
- E. Bensana, G. Verfaillie, J.C. Agnèse, N. Bataille, and D. Blumstein, “Exact and approximate methods for the daily management of an earth observation satellite, ” in Proc. of the 4th Intl. Symposium on Space Mission Operations and Ground Data Systems (SpaceOps-96), Munich, Germany, 1996. ftp://ftp.cert.fr/pub/verfaillie/spaceops96.ps.
- M. Lemaître and G. Verfaillie, “Daily management of an earth observation satellite: comparison of Ilog solver with dedicated algorithms for valued constraint satisfaction problems, ” in Proc. of the 3rd Ilog Intl. Users Meeting, Paris, France, 1997. ftp://ftp.cert.fr/pub/verfaillie/ilog97.ps.
Cited by
Items 201–239 of 239
Task Scheduling for Single Satellite Observation Based on Meta-Reinforcement Learning
Li, Z., Li, Z., & Bai, Y. (2025) · Journal of Aerospace Information Systems · doi:10.2514/1.i011619 · Cited by 1
Research on Multi satellite Collaborative Task Planning Technology
Wang, J., Qin, W. T., Ran, D., Wu, P., Wang, K., & Liu, Y. (2025) · Journal of Physics Conference Series · doi:10.1088/1742-6596/3022/1/012011 · Cited by 1
Planning and Scheduling of an Agile EOS Combining On-ground and On-board Decisions
Li, J., & Yan, C. (2018) · IOP Conference Series Materials Science and Engineering · doi:10.1088/1757-899x/382/3/032023 · Cited by 2
A New Method of Mission Planning for Area Target Scanning by Multiple Earth Observing Satellites
Han, P., Deng, Q., Li, C., & Zhu, H. (2019) · Chinese Automation Congress · doi:10.1109/cac48633.2019.8997375 · Cited by 1
Satellite Mission Instruction Sequence Generation Algorithm Using a Flexible Weighted Directed Graph
Zhang, Y., Zhang, J., Yang, M., Peiyao, Y., & Song, X. (2021) · International Journal of Aerospace Engineering · doi:10.1155/2021/4109118 · Cited by 1
“use a Joseph-Louis Lagrange relaxation technique and tabu search algorithm to solve the imaging scheduling problem [7].”
MethodMéndez-Gómez, J.-E., Cheng, A. M. K., & Muñoz-Giraldo, S. (2023) · ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS) · doi:10.1145/3576841.3589616 · Cited by 1
“modeled as a common problem, such as a knapsack problem [4][5], a packing problem [6], a single-machine scheduling problem [7], or a network problem [8].”
BackgroundScheduling an Agile Multipayload Earth-Observing Satellite
Zhang, W., & Zheng, G. (2023) · Journal of Spacecraft and Rockets · doi:10.2514/1.a35726 · Cited by 2
Minimum Weighted Vertex Cover Approach to Task Allocation of Multiple Satellites
Sun, C., Zhang, X., Zhou, Q., & Qiu, H. (2024) · Chinese Control Conference (CCC) · doi:10.23919/ccc63176.2024.10662544 · Cited by 2
“In [17–19], models of 0-1 knapsack were presented for satellite task scheduling with limited constraints.”
MethodCooperative Parallel SAT Local Search with Path Relinking
Jarvis, P., & Arbeláez, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-43680-3_6 · Cited by 1
Liu, X., 国防科学技术大学信息系统与管理学院, Gao, P., 陈盈果, & 陈英武 (2010) · National Remote Sensing Bulletin · doi:10.11834/jrs.20100514 · Cited by 2
An Extensive Comparison of 0–1 Linear Programs for the Daily Satellite Mission Planning
Gabrel, V. (2008) · Wiley eBooks · doi:10.1002/9780470611098.ch12 · Cited by 1
“In [ 8 ], the daily mission planning problem is seen as a knapsack problem with a huge number of additional logic constraints on variables.”
InfluentialModelisation et resolution de problemes d'optimisation combinatoire issus d'applications spatiales
Mancel, C. (2004) · HAL · Cited by 13
Solving the Course-timetabling Problem of Cairo University Using Max-SATPreprint
Halaby, M. E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.05027 · Cited by 1
“Many theoretical and practical problems can be encoded into SAT and MaxSAT such as debugging [13], circuits design and scheduling of how an observation satellite captures photos of Earth [15], course timetabling [2, 10, 9, 7], software package upgrades [6], routing [16, 11], reasoning [14] and protein structure alignm…”
BackgroundMission schedule of agile satellites based on Proximal Policy Optimization AlgorithmPreprint
Liu, X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.02352 · Cited by 1
“Vasquez and Hao(2001) [5] come up with Tabu search with knapsack formulation.”
BackgroundNew Heuristics For The 0-1 Multi-dimensional Knapsack Problems
Akin, M. H. (2009) · Journal of International Crisis and Risk Communication Research
Mission Planning for Observation Satellites
Gabrel, V., Murat, C., & Paschos, V. T. (2008) · Wiley eBooks · doi:10.1002/9780470611753.ch8
Formalizing and Solving Information Collection Problems with Autonomous Sensor Systems
Godichaud, M., Chanthery, É., Buffet, O., & Contat, M. (2011) · IFAC Proceedings Volumes · doi:10.3182/20110828-6-it-1002.01825 · Cited by 1
“Satellites can also collect information and models have been developed in this way to select and schedule goals during a mission (Vasquez and Hao (2001), Lemaître et al. (2002)).”
BackgroundGenerating optimised satellite payload operation schedules with Evolutionary Algorithms
Weber, A., Fasoulas, S., & Wolf, K. (2009) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2009.4983231
An Hybrid Approach to Real Complex System Optimization
Grandchamp, E. (2005) · Springer eBooks · doi:10.1007/0-387-24049-7_10
Yoda, K. (2013) · doi:10.7282/t3s180js
“[22]), daily management of a satellite (see Vasquez and Hao [73]), and combinatorial auctions (see de Vries and Vohra [16] and Rothkopf et al.”
BackgroundA Stochastic knapsack problem with mixed distributional capacity
Etuk, E. H. (2011) · American Journal of Scientific and Industrial Research · doi:10.5251/ajsir.2011.2.1.24.32
Study the problem of performance evaluation of Earth observation satellite mission planning
Wang, H., Guo, L., Xie, Q., Zhou, B. B., & Qu, Y. (2014) · SpaceOps Conference (SpaceOps) · doi:10.2514/6.2014-1641
Multilevel techniques and learning automata for the Maximum Satisfiability (MAXSAT) problem
Brådland, Ø., & Oseland, M. G. L. (2012) · NORA - Norwegian Open Research Archives
An Exact Algorithm for Optimal Areal Positioning Problem with Rectangular Targets and Requests
Bansal, M. (2011) · OakTrust (Texas A&M University Libraries)
Autonomous Decision-making for Satellites Surveillance
Yu, K., Liu, F., Liu, Y., & Li, G. (2019) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc.2019.8832717
CCEHC-Plus: Reemphasis on Soft Clauses in WPMS Problem based on CCEHC
Liu, W., Shang, J., Li, Z., & Zhang, Y. (2019) · IEEE International Conference on Power, Intelligent Computing and Systems (ICPICS) · doi:10.1109/icpics47731.2019.8942577
An Earth Observation Satellite Mission Planning Method Based on Deep Q-Learning
Chen, T., Wang, H., Liu, H., & Wu, P. (2021) · International Symposium on Computer and Information Processing Technology (ISCIPT) · doi:10.1109/iscipt53667.2021.00161
Query-guided maximum satisfiability
Zhang, X., Mangal, R., Nori, A. V., & Naik, M. (2016) · ACM SIGPLAN Notices · doi:10.1145/2914770.2837658
A Novel Hybrid Mission Planning Method Based on Multilevel Icosahedral Mesh Partitioning
Liu, W., Zhang, B., Li, J., Liu, J., Zhang, D., & Shao, X. (2023) · China International SAR Symposium (CISS) · doi:10.1109/ciss60136.2023.10380047
“There are many algorithms proposed to solve the afore-mentioned optimization problem, such as the Tabu Search Algorithm [7], [8], the Greedy Algorithm [9], [10], the Ant Colony Algorithm [11], the Particle Swarm Algorithm [12], the Genetic Algorithm [13], the Evolutionary Algorithm [14], the…”
MethodLiu, W., Zhang, D., Tian, Y., & Shao, X. (2025) · Aerospace Systems · doi:10.1007/s42401-025-00354-0
“Several algorithms have been proposed to solve the optimization problem, including the Tabu Search Algorithm [10 , 11], the Greedy Algorithm [12 , 13], the Ant Colony Algorithm [14 – 16], the Genetic Algorithm [17 , 18], the Evolutionary Algorithm [19 – 21], the Particle Swarm Algorithm [22 – 24],…”
A Hybrid Approach for Satellite Scheduling: Local Search Augmented by Deep Reinforcement Learning
Xia, Y., & Sun, M. (2025) · Signals and communication technology · doi:10.1007/978-3-031-94973-9_23
Zhang, Y., Liang, B., Chen, J., Song, K., & Chen, Y. (2026) · Communications in computer and information science · doi:10.1007/978-981-95-4788-3_21
Zhou, F., Wang, G., Wen, G., Wang, T., Li, X., Jiao, Z., Zhang, J., Huang, S., & Sun, J. (2026) · Remote Sensing · doi:10.3390/rs18132109
Balancing power with logic: Exact satisfiability-based methods for energy-aware assembly lines
Zheng, Z., Cherif, M. S., Py, M., Shibasaki, R. S., Li, C.-M., Deroussi, L., & Grangeon, N. (2026) · Computers & Operations Research · doi:10.1016/j.cor.2026.107635
Warekuromor, T. (2026) · International Journal of Modern Science and Research Technology · doi:10.67317/ijmsrt26aug175
Li, B., Li, X., Wang, H., & Meng, J. (2012) · Communications in computer and information science · doi:10.1007/978-3-642-31837-5_50
(2005) · Cited by 38
Metadata
- Authors
- Vasquez, M., & Hao, J.-K.
- Affiliations
- IMT Mines Alès (FR)
- Université d'Angers (FR)
- Venue
- Computational Optimization and Applications
- Published
- 2001-11
- Volume
- 20
- Issue
- 2
- Pages
- 137-157
- ISSN
- 0926-6003 (ISSN-L)
- 1573-2894
- OpenAlex
- W2123757087
- Cited by
- 239
- References
- 14
- Citations by year
- 2026: 4 · 2025: 9 · 2024: 7 · 2023: 11 · 2022: 6 · 2021: 10 · 2020: 14 · 2019: 21 · 2018: 16 · 2017: 9 · 2016: 11 · 2015: 8 · 2014: 14 · 2013: 14 · 2012: 8
- FWCI
- 39.06
- Type
- journal article
- Language
- en
- Open access
- green
- hal.science
- Licence
- other-oa
- www.springernature.com/gp/researchers/text-and-data-mining (tdm)
- www.springernature.com/gp/researchers/text-and-data-mining (vor)
- Locations
- Computational Optimization and Applications (publishedVersion)
- HAL (submittedVersion, other-oa)
- Topics
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Optimization and Packing Problems
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Constraint Satisfaction and Optimization
- Keywords
- knapsack problem, tabu search, constraint handling, stereoscopic photography, SPOT-5, profit maximization, neighborhood search, intensification and diversification
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.