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
Dynamic tabu list management using the reverse elimination method
Dammeyer, F., & Voß, S. (1993) · Annals of Operations Research · doi:10.1007/bf02022561 · Cited by 114
An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem
Fréville, A., & Plateau, G. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)90209-7 · Cited by 113 · cited 1×
“Note that similar neighborhoods based on adding-dropping have been used in many heuristic algorithms for MKP [Dammeyer & Voss 93, Fréville & Plateau 94, 97, Glover & Kochenberger 96, Lokketangen & Glover 98, Hanafi & Fréville 98, Chu & Beasley 98].”
MethodThe 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool
Fr�ville, A., & Plateau, G. (1996) · Journal of Heuristics · doi:10.1007/bf00247210 · Cited by 43
Comparison of Heuristics for the 0–1 Multidimensional Knapsack Problem
Hanafi, S., Fréville, A., & Abdellaoui, A. (1996) · Springer eBooks · doi:10.1007/978-1-4613-1361-8_27 · Cited by 26
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
Chaff: engineering an efficient SAT solver
Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001) · Proceedings of the 38th conference on Design automation - DAC '01 · doi:10.1145/378239.379017 · Cited by 2,940
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
Zhang, L., Madigan, C. F., Moskewicz, M. H., & Malik, S. (2001) · Cited by 681
Selecting and scheduling observations of agile satellites
Lemaı̂tre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002) · Aerospace Science and Technology · doi:10.1016/s1270-9638(02)01173-2 · Cited by 472
“Local search (see for example [1]) is a well-known general technique for solving highly combinatorial problems, including EOS selection and scheduling problems [18,23].”
BackgroundMethodThe multidimensional 0–1 knapsack problem: An overview
Fréville, A. (2003) · European Journal of Operational Research · doi:10.1016/s0377-2217(03)00274-1 · Cited by 525
Three Scheduling Algorithms Applied to the Earth Observing Systems Domain
Wolfe, W. J., & Sorensen, S. E. (2000) · Management Science · doi:10.1287/mnsc.46.1.148.15134 · Cited by 313
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.