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
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
Bianchessi, N., Cordeau, J.-F., Desrosiers, J., Laporte, G., & Raymond, V. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.12.026 · Cited by 252
“Vasquez and Hao (2001, 2003) have presented a tabu search algorithm together with a “logic-constrained” knapsack formulation, as well as some upper bounds for this problem.”
MethodAdaptive Tabu Search for course timetabling
Lü, Z., & Hao, J. (2008) · European Journal of Operational Research · doi:10.1016/j.ejor.2008.12.007 · Cited by 232
Self-citationA tabu search method guided by shifting bottleneck for the job shop scheduling problem
Pezzella, F., & Merelli, E. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00158-7 · Cited by 211
Wang, P., Reinelt, G., Gao, P., & Tan, Y. (2011) · Computers & Industrial Engineering · doi:10.1016/j.cie.2011.02.015 · Cited by 195
“Bensana, Verfaillie, Agnese, Bataille, and Blumstein (1996, 1999) and Vasquez and Hao (2001) studied the daily observation scheduling problem for Spot satellite of France.”
BackgroundGraph colouring approaches for a satellite range scheduling problem
Zufferey, N., Amstutz, P., & Giaccari, P. (2008) · Journal of Scheduling · doi:10.1007/s10951-008-0066-8 · Cited by 177
“…on satellite range scheduling problems (e.g., Bensana et al. 1999; Harrison et al. 1999; Pemberton 2000; Wolfe and Sorensen 2000; Verfaillie and Lemaitre 2001; Frank et al. 2001; Lemaitre et al. 2002; Gabrel and Murat 2003; Vasquez and Hao 2003; Globus et al. 2003, 2004; Cordeau and Laporte 2005).”
BackgroundDaily imaging scheduling of an earth observation satellite
Lin, W.-C., Liao, D.-Y., Liu, C.-Y., & Lee, Y.-Y. (2005) · IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans · doi:10.1109/tsmca.2005.843380 · Cited by 173
“In order to demonstrate the efficiency and effectiveness of the approach, in this section, a Tabu search algorithm is implemented and modified from the one in [ 14 ].”
BackgroundMethodInfluentialIterative and core-guided MaxSAT solving: A survey and assessment
Morgado, A., Heras, F., Liffiton, M. H., Planes, J., & Marques-Silva, J. P. (2013) · Constraints · doi:10.1007/s10601-013-9146-2 · Cited by 224
“Concrete examples include the following domains: Routing problems [127]; different problems of BioInformatics, such as Protein Alignment [120], Haplotyping with Pedigrees [56], Reasoning over Biological Networks[58]; Hardware Debugging, both on Design Debugging [111], as well as on Circuit Debugging [34, 81]; Software…”
InfluentialA mixed integer linear programming model for multi-satellite scheduling
Chen, X., Reinelt, G., Dai, G., & Spitz, A. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.11.058 · Cited by 162
“Alternatively, formulations as generalized knapsack problems can be solved with a tabu search algorithm (Vasquez & Hao, 2001) or a genetic algorithm (Mansour & Dessouky, 2010).”
MethodXu, R., Chen, H., Liang, X., & Wang, H. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.12.039 · Cited by 165
Ansótegui, C., Bonet, M. L., & Levy, J. (2013) · Artificial Intelligence · doi:10.1016/j.artint.2013.01.002 · Cited by 154
“The weighted partial MaxSAT problem is a natural combinatorial problem, and it can be used in several domains, such as: scheduling [40] and timetabling [9] problems, FPGA routing [41], software package installation [7], design debugging [36], bioinformatics [39], probabilistic reasoning [34], etc.”
BackgroundMaximizing the value of an Earth observation satellite orbit
Cordeau, J.-F., & Laporte, G. (2005) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601926 · Cited by 150
Wu, G., Jin, L., Ma, M., & Qiu, D. (2013) · Computers & Operations Research · doi:10.1016/j.cor.2013.02.009 · Cited by 155
“We also compared the ACO–LS algorithm with the traditional ACO, Tabu Search (TS) [6], genetic algorithm (GA) [10], simulated annealing (SA) [18] and a highest priority first schedule (HPFS) algorithm.”
BackgroundMethodInfluentialPlanning and scheduling algorithms for the COSMO-SkyMed constellation
Bianchessi, N., & Righini, G. (2008) · Aerospace Science and Technology · doi:10.1016/j.ast.2008.01.001 · Cited by 148
Gabrel, V., & Vanderpooten, D. (2002) · European Journal of Operational Research · doi:10.1016/s0377-2217(01)00188-6 · Cited by 124
“A large variety of approaches have been considered: • neural networks (Gaspin, 1989), • specialized heuristics (Hall and Magazine, 1994) and metaheuristics (Vasquez and Hao, 2001), • integer linear programming (Bensanna et al.”
BackgroundMaximum Satisfiability Using Core-Guided MaxSAT Resolution
Narodytska, N., & Fahiem Bacchus, A. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.9124 · Cited by 123
“Many industrial applications can be naturally encoded in M AX S AT , and successful application areas include bioinformatics (Strick-land, Barnes, and Sokol 2005; Grac¸a et al. 2012), planning (Cooper et al. 2006; Zhang and Bacchus 2012), and scheduling (Vasquez and Hao 2001).”
BackgroundOptimization-Based Scheduling for the Single-Satellite, Multi-Ground Station Communication Problem
Spangelo, S., Cutler, J., Gilson, K., & Cohn, A. (2015) · Computers & Operations Research · doi:10.1016/j.cor.2014.11.004 · Cited by 120
Memetic Algorithms in Discrete Optimization
Hao, J. (2011) · Studies in computational intelligence · doi:10.1007/978-3-642-23247-3_6 · Cited by 127
“Among various constraint relaxation techniques, a common practice is to integrate the relaxed constraints into the evaluation function as a (weighted) component or as a part of a multi-component evaluation function (see examples in [22, 65, 66]).”
BackgroundSelf-citationHabet, D., Vasquez, M., & Vimont, Y. (2008) · Computational Optimization and Applications · doi:10.1007/s10589-008-9220-7 · Cited by 121
“The selection and scheduling problem for a non-agile satellite, like SPOT5, is stated in [3] and various methods have been used to solve it. The best results are obtained in [ 20 ]b y using a tabu search algorithm and very good upper bounds are calculated by an original partition method [21].”
MethodSelf-citationCCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
Luo, C. W., Cai, S., Wu, W., Jie, Z., & Su, K. (2014) · IEEE Transactions on Computers · doi:10.1109/tc.2014.2346196 · Cited by 108
“problems in a broad range of application areas such as physical design of very-large-scale integration (VLSI) circuits [2], internet search [3], routing [4], bioinformatics [5], scheduling [6] and probabilistic reasoning [7] can be modeled as weighted MAX-SAT.”
BackgroundChih, M., Lin, C.-J., Chern, M., & Ou, T.-Y. (2013) · Applied Mathematical Modelling · doi:10.1016/j.apm.2013.08.009 · Cited by 108
“Numerous real-world applications are modeled as knapsack problems, such as capital budgeting [2], project selection [3], and loading problems [4], in a variety of areas [5,6].”
BackgroundNiu, X., Tang, H., & Wu, L. (2018) · International Journal of Disaster Risk Reduction · doi:10.1016/j.ijdrr.2018.02.013 · Cited by 101
Optimization-Based Scheduling Method for Agile Earth-Observing Satellite Constellation
Cho, D.-H., Kim, J.-H., Choi, H.-L., & Ahn, J. (2018) · Journal of Aerospace Information Systems · doi:10.2514/1.i010620 · Cited by 98
An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem
Meng, T., & Pan, Q.-K. (2016) · Applied Soft Computing · doi:10.1016/j.asoc.2016.11.023 · Cited by 102
LocalSolver 1.x: a black-box local-search solver for 0-1 programming
Benoist, T., Estellon, B., Gardi, F., Megel, R., & Karim Nouioua, A. (2011) · 4OR · doi:10.1007/s10288-011-0165-9 · Cited by 93
“The state of the art corresponds to Vasquez-Hao’s tabu heuristic (Vasquez and Hao 2001); moreover, these authors have proven that their results are nearly optimal (gap lower than 1%).”
BackgroundInfluentialA logical approach to efficient Max-SAT solving
Larrosa, J., Heras, F., & de Givry, S. (2007) · Artificial Intelligence · doi:10.1016/j.artint.2007.05.006 · Cited by 93
“They include academic problems such as Max-Cut or Max-Clique, as well as real problems in domains like routing [3], bioinformatics [4], scheduling [5], probabilistic reasoning [6] and electronic markets [7].”
Wang, J., Demeulemeester, E. L., & Qiu, D. (2016) · Computers & Operations Research · doi:10.1016/j.cor.2016.04.014 · Cited by 104
“Metaheuristics: A large number of metaheuristics were proposed for EOS scheduling, which primarily contain tabu search algorithms [4, 8, 10, 34, 36, 46, 57], genetic algorithms [29, 44, 45, 55], ant colony algorithms [30, 50, 56], local search algorithms [27, 28, 48] and simulated annealing algorithms [17, 18].”
Wu, G., Wang, H., Pedrycz, W., Li, H., & Wang, L. (2017) · Computers & Industrial Engineering · doi:10.1016/j.cie.2017.09.050 · Cited by 98
“…& Dessouky, 2010; Yuan et al., 2014) , particle swarm optimization (D. Zhang et al., 2013), differential evolution (J. Wu et al., 2015), tabu search (Nicola Bianchessi et al., 2007; Vasquez & Hao, 2001) and ant colony optimization (G. Wu et al., 2013; G. Wu et al., 2012; Z. Zhang et al., 2014).”
BackgroundMethodInfluentialThe case for strategic oscillation
Glover, F., & Hao, J. (2009) · Annals of Operations Research · doi:10.1007/s10479-009-0597-1 · Cited by 94
“…oscillation has notably also been used in settings for transitioning between multiple neighborhoods, decision rules and search regions (Glover, 1977; Freville and Plateau, 1986; Kelly, Golden and Assad, 1993; Osman, 1993; Vasquez and Hao, 2001a, 2001b; Hvattum, Lokketangen and Glover, 2005 ).”
MethodSelf-citationScheduling algorithms for rapid imaging using agile Cubesat constellations
Nag, S., Li, A. S., & Merrick, J. H. (2018) · Advances in Space Research · doi:10.1016/j.asr.2017.11.010 · Cited by 87
Enhancing Earth Observation Throughput Using Inter-Satellite Communication
Wang, P., Li, H., Chen, B., & Zhang, S. (2022) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2022.3163389 · Cited by 94
“Instead, they focus on the efficient use of the observation resources and time windows, either for a single satellite setting [14]– [17] or over multiple satellites [18]–[23].”
BackgroundA survey of effective heuristics and their application to a variety of knapsack problems
Wilbaut, C., Hanafi, S., & Salhi, S. (2007) · IMA Journal of Management Mathematics · doi:10.1093/imaman/dpn004 · Cited by 93
“Keywords: knapsack; heuristics; 0–1 variables.”
MethodUnderstanding the power of clause learning
Beanie, P., Kautz, H., & Sabharwal, A. (2003) · International Joint Conference on Artificial Intelligence · Cited by 91
Satellite downlink scheduling problem: A case study
Karapetyan, D., Mitrovic Minic, S., Malladi, K. T., & Punnen, A. P. (2015) · Omega · doi:10.1016/j.omega.2015.01.001 · Cited by 75
“Most of the literature on satellite mission planning (image acquisition and downlinking) is divided into two categories: optical satellites [25, 27] and Synthetic Aperture Radar (SAR) satellites [4, 5, 7, 10].”
BackgroundA binary grey wolf optimizer for the multidimensional knapsack problem
Luo, K., & Zhao, Q. (2019) · Applied Soft Computing · doi:10.1016/j.asoc.2019.105645 · Cited by 75
The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects
Fréville, A., & Hanafi, S. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-3448-8 · Cited by 89
Scheduling for single agile satellite, redundant targets problem using complex networks theory
Wang, X., Chen, Z., & Han, C. S. (2015) · Chaos Solitons & Fractals · doi:10.1016/j.chaos.2015.12.003 · Cited by 81
Priority-based and conflict-avoidance heuristics for multi-satellite scheduling
Chen, X., Reinelt, G., Dai, G., & Wang, M. (2018) · Applied Soft Computing · doi:10.1016/j.asoc.2018.04.021 · Cited by 74
Upper Bounds for the SPOT 5 Daily Photograph Scheduling Problem
Vasquez, M., & Hao, J.-K. (2003) · Journal of Combinatorial Optimization · doi:10.1023/a:1021950608048 · Cited by 73
“These heuristics include, among others, greedy procedures, algorithms based on simulated annealing and tabu search (Bensana et al., 1996; Vasquez and Hao, 2001).”
BackgroundMethodInfluentialSelf-citationMansour, M., & Dessouky, M. M. (2009) · Computers & Industrial Engineering · doi:10.1016/j.cie.2009.11.012 · Cited by 79
“Verfaillie et al. (1996) introduced the Russian Doll Search (RDS) algorithm and used it to find the optimal solution for eight single orbit moderately-sized SPOT5 problems.”
MethodMission scheduling optimization of SAR satellite constellation for minimizing system response time
Kim, H., & Chang, Y.-K. (2014) · Aerospace Science and Technology · doi:10.1016/j.ast.2014.10.006 · Cited by 81
Dynamic Scheduling for Emergency Tasks on Distributed Imaging Satellites with Task Merging
Wang, J., Zhu, X., Qiu, D., & Yang, L. T. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.156 · Cited by 72
Robust earth observation satellite scheduling with uncertainty of cloud coverage
Wang, X., Song, G., Leus, R., & Han, C. (2020) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2019.2947978 · Cited by 70
“In order to address the scheduling problem described with the use of these models, genetic algorithms are widely utilized [12]–[16], and other heuristic techniques have been developed [4], [12], [17].”
BackgroundMethodImaging Order Scheduling of an Earth Observation Satellite
Liao, D.-Y., & Yang, Y.-T. (2007) · IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) · doi:10.1109/tsmcc.2007.900668 · Cited by 71
“Vasquez and Hao [17] formulate the daily photograph scheduling problem of SPOT [22] as a generalized version of the knapsack problem, and solve it by a dedicated Tabu search algorithm.”
Wu, G., Ma, M., Zhu, J., & Qiu, D. (2012) · Journal of Systems Engineering and Electronics · doi:10.1109/jsee.2012.00089 · Cited by 69
A two-phase genetic annealing method for integrated Earth observation satellite scheduling problems
Zhu, W., Hu, X., Xia, W., & Jin, P. (2017) · Soft Computing · doi:10.1007/s00500-017-2889-8 · Cited by 72
“Vasquez and Hao (2001) modeled EOSS as a well-known knapsack model with logical constraints.”
BackgroundMathematical Programming for Earth Observation Satellite Mission Planning
Gabrel, V., & Murat, C. (2003) · Applied optimization · doi:10.1007/978-1-4757-3752-3_7 · Cited by 75
Sarkheyli, A., Bagheri, A., Vaghei, B. G., & Moghadam, R. A. (2013) · Aerospace Science and Technology · doi:10.1016/j.ast.2013.04.001 · Cited by 65
E., Z., Shi, R., Gan, L., Baoyin, H., & Li, J. (2021) · Acta Astronautica · doi:10.1016/j.actaastro.2020.08.041 · Cited by 54
Zhao, X., Wang, Z., & Zheng, G. (2020) · Journal of Aerospace Information Systems · doi:10.2514/1.i010754 · Cited by 53
Wang, J., Demeulemeester, E., Hu, X., Qiu, D., & Liu, J. (2019) · IEEE Systems Journal · doi:10.1109/jsyst.2018.2874223 · Cited by 56
A KNN quantum cuckoo search algorithm applied to the multidimensional knapsack problem
García, J., & Maureira, C. (2021) · Applied Soft Computing · doi:10.1016/j.asoc.2020.107077 · Cited by 53
Cui, J., & Zhang, X. (2019) · Sensors · doi:10.3390/s19061430 · Cited by 52
Augenstein, S., Estanislao, A., Guere, E., & Blaes, S. (2016) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v26i1.13784 · Cited by 62
Wu, K., Zhang, D., Chen, Z., Chen, J., & Shao, X. (2019) · Advances in Space Research · doi:10.1016/j.asr.2019.01.006 · Cited by 48
Xiao, Y., Zhang, S., Yang, P., You, M., & Huang, J. (2019) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2019.03.016 · Cited by 46
A new hybrid genetic algorithm for the collection scheduling problem for a satellite constellation
Barkaoui, M., & Berger, J. (2019) · Journal of the Operational Research Society · doi:10.1080/01605682.2019.1609891 · Cited by 54
García, J., Lalla‐Ruiz, E., Voß, S., & Droguett, E. L. (2020) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-020-01085-8 · Cited by 44
Satellite Scheduling Problems: A survey of applications in Earth and outer space observation
Ferrari, B., Cordeau, J., Delorme, M., Iori, M., & Orosei, R. (2024) · Computers & Operations Research · doi:10.1016/j.cor.2024.106875 · Cited by 62
“Luo (2020) extended the model of Vasquez and Hao (2001) for the Spot5 scheduling problem to cover cases with N on-board cameras, and proposed a hybrid artificial bee colony algorithm to solve the problem.”
BackgroundMethodWPM3: An (in)complete algorithm for weighted partial MaxSAT
Ansótegui, C., & Gabàs, J. (2017) · Artificial Intelligence · doi:10.1016/j.artint.2017.05.003 · Cited by 42
Robust Satellite Scheduling Approach for Dynamic Emergency Tasks
Zhai, X., Niu, X., Tang, H., Wu, L., & Shen, Y. (2015) · Mathematical Problems in Engineering · doi:10.1155/2015/482923 · Cited by 39
“Vasquez and Hao formulated the satellite observation scheduling problem into a generalized version of the wellknown knapsack model and used the Tabu search method to solve the problem [16].”
MethodAutonomous Task Planning Method for Multi-Satellite System Based on a Hybrid Genetic Algorithm
Long, J., Wu, S., Han, X., Wang, Y., & Liu, L. (2023) · Aerospace · doi:10.3390/aerospace10010070 · Cited by 39
Deng, M., Liu, B., Li, S., Du, R., Wu, G., Li, H., & Wang, L. (2020) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2962205 · Cited by 40
“problem optimization [4], workshop scheduling [5], integer optimization [6], task clustering [7], [8], etc.”
BackgroundVerfaillie, G., & Lemaı̂tre, M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45578-7_55 · Cited by 39
“Various methods, able to solve it either optimally or approximately, have been proposed and compared [4,3,14].”
MethodQUEST – A new quadratic decision model for the multi-satellite scheduling problem
Berger, J., Lo, N., & Barkaoui, M. (2020) · Computers & Operations Research · doi:10.1016/j.cor.2019.104822 · Cited by 37
New inference rules for efficient Max-SAT solving
Heras, F., & Larrosa, J. (2006) · Cited by 38
Relaxation Search: A Simple Way of Managing Optional Clauses
Bacchus, F., Davies, J., Tsimpoukelli, M., & Katsirelos, G. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8849 · Cited by 42
“As a result, MAXSAT solvers have been successfully applied in various areas including bioinformatics (Strickland, Barnes, and Sokol 2005; Graça et al. 2012), planning (Cooper et al. 2006; Zhang and Bacchus 2012), and scheduling (Vasquez and Hao 2001).”
BackgroundExploiting inference rules to compute lower bounds for MAX-SAT solving
Lin, H., & Su, K. (2007) · Griffith Research Online · Cited by 36
Damiani, S., Verfaillie, G., & Charmeau, M. (2005) · Adaptive Agents and Multi-Agents Systems · doi:10.1145/1082473.1082543 · Cited by 43
Strengthened 0-1 linear formulation for the daily satellite mission planning
Gabrel, V. (2006) · Journal of Combinatorial Optimization · doi:10.1007/s10878-006-7912-4 · Cited by 35
Area targets observation mission planning of agile satellite considering the drift angle constraint
(2018) · Journal of Astronomical Telescopes, Instruments, and Systems · doi:10.1117/1.jatis.4.4.047002 · Cited by 33
Local Search on SAT-encoded Colouring Problems
Prestwich, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24605-3_9 · Cited by 39
Wang, X., Han, C. S., Zhang, R., & Gu, Y. (2019) · IEEE Access · doi:10.1109/access.2019.2925704 · Cited by 38
“[8] 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,” Comput Optim Appl, vol. 20, no. 2, pp. 137–157, 2001.”
BackgroundMethodInfluentialFault-Tolerant Scheduling for Real-Time Tasks on Multiple Earth-Observation Satellites
Zhu, X., Wang, J., Qin, X., Wang, J., Liu, Z., & Demeulemeester, E. (2015) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2014.2363657 · Cited by 34
Upper bounds for revenue maximization in a satellite scheduling problem
Benoist, T., & Rottembourg, B. (2004) · 4OR · doi:10.1007/s10288-004-0044-8 · Cited by 37
“Various algorithms have been developed to solve this problem for instance in Bensana et al. (1999) or Vasquez and Hao (2001) .”
MethodSolving (Weighted) Partial MaxSAT with ILP.
Ansótegui, C., & Gabàs, J. (2013) · Integration of AI and OR Techniques in Constraint Programming · Cited by 31
Heuristic Scheduling Algorithm Oriented Dynamic Tasks for Imaging Satellites
Wang, M., Dai, G., & Vasile, M. (2014) · Mathematical Problems in Engineering · doi:10.1155/2014/234928 · Cited by 30
“Vasquez and Hao [3] formalized the daily photograph scheduling problem of EOS as a generalized version of the well-known knapsack model and developed a tabu search algorithm to solve the problem.”
Kernel based tabu search for the Set-union Knapsack Problem
Wei, Z., & Hao, J. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113802 · Cited by 35
“The kernel search procedure is inspired by the work presented in (Vasquez & Hao, 2001) where the notion of kernel was introduced for solving a logic-constrained knapsack problem.”
BackgroundMethodInfluentialSelf-citationImaging-Duration Embedded Dynamic Scheduling of Earth Observation Satellites for Emergent Events
Niu, X., Tang, H., Wu, L. X., Deng, R., & Zhai, X. (2015) · Mathematical Problems in Engineering · doi:10.1155/2015/731734 · Cited by 32
“They proposed a Tabu search algorithm to solve the model [5].”
MethodWang, J., Demeulemeester, E. L., Hu, X., & Wu, G. (2020) · IEEE Systems Journal · doi:10.1109/jsyst.2019.2961236 · Cited by 30
“Moreover, metaheuristics for EOS scheduling also include tabu search algorithms [20], [26], [34], [35], [46], genetic algorithms [23], [31], [39], [42], ant colony algorithms [10], [24], [40], [45], local search algorithms [21], [22], and simulated annealing algorithms [18], [20].”
MethodScheduling of a Constellation of Satellites: Creating a Mixed-Integer Linear Model
Monmousseau, P. (2021) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-021-01875-2 · Cited by 32
Metaheuristic and Multiobjective Approaches for Space Allocation
Silva, L., & Dario, J. (2003) · Nottingham ePrints (University of Nottingham) · Cited by 48
A db-Scan Hybrid Algorithm: An Application to the Multidimensional Knapsack Problem
García, J., Moraga, P., Valenzuela, M. A., & Pinto, H. (2020) · Mathematics · doi:10.3390/math8040507 · Cited by 27
“MKP modeling has been used in project selection and capital budgeting [38] applications as well as in the delivery of groceries in vehicles with multiple compartments [39] and the daily photographic scheduling problem of an Earth observation satellite [40].”
MethodLiu, B., Deng, M., Wu, G., Xinyu, P., Li, H., & Pedrycz, W. (2022) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2022.3143158 · Cited by 29
“Many models, including scene selection [12], knapsack problem optimization [13], workshop scheduling [14], task clustering [9, 30], have been proposed to construct the mathematical models of satellite scheduling problem.”
BackgroundMethodHybrid Algorithms for Satellite Imaging Scheduling
Lin, W.-C., & Chang, S.-C. (2006) · 2005 IEEE International Conference on Systems, Man and Cybernetics · doi:10.1109/icsmc.2005.1571527 · Cited by 27
“[7] 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,” Computational Optimization and Applications, Vol. 20, No. 2, pp. 137-157, 2001.”
BackgroundAn iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem
Wilbaut, C., Salhi, S., & Hanafi, S. (2008) · European Journal of Operational Research · doi:10.1016/j.ejor.2008.11.036 · Cited by 30
“We also give the lower bounds reported by Vasquez and Hao (2001b) (column ‘‘V&H”).”
Qin, J., Bai, X. L., Du, G., Liu, J., Peng, N., & Xu, M. (2024) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2024.3397958 · Cited by 30
“Vasquez et al. [5] adopted tabu search to solve the single-satellite scheduling problem, which improved the efficiency of the solution.”
BackgroundLocal Search and Backtracking vs Non-Systematic Backtracking
Prestwich, S. (2001) · Cited by 33
A precedence-rule-based heuristic for satellite onboard activity planning
Liang, J., Zhu, Y., Luo, Y.-Z., Zhang, J., & Zhu, H. (2020) · Acta Astronautica · doi:10.1016/j.actaastro.2020.10.020 · Cited by 26
Image collection planning for KOrea Multi-Purpose SATellite-2
Jang, J., Choi, J.-W., Bae, H. J., & Choi, I. C. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.04.009 · Cited by 25
Exact algorithms for single frame selection on multiaxis Satellites
Song, D., van der Stappen, A. F., & Goldberg, K. (2006) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2005.860617 · Cited by 30
“Recent research [2], [8], [18], [ 33 ] on the satellite space mission problem and its variations focuses on developing exact and approximate methods using numerical methods, such as column generation, Tabu search, and genetic algorithms (GAs).”
BackgroundScheduling multiple agile Earth observation satellites with multiple observations
Wang, X., Han, C., & Leus, R. (2026) · Advances in Space Research · doi:10.1016/j.asr.2025.10.042 · Cited by 24
“…scheduling refers to the problem of allocating multiple satellites, each constrained by limited resources such as energy and memory, to a set of observation tasks, with the Conventional EOS (CEOS) scheduling has been extensively studied (Vasquez and Hao, 2001; Lin et al., 2005; Wang et al., 2019).”
Chang, Z., Zhou, Z., Li, R., Xiao, H., & Xing, L. (2022) · Computers & Industrial Engineering · doi:10.1016/j.cie.2022.108252 · Cited by 30
A Tabu Search Algorithm for Satellite Imaging Scheduling
Lin, W.-C., & Liao, D.-Y. (2005) · 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583) · doi:10.1109/icsmc.2004.1399860 · Cited by 24
“Keywords: Satellite Scheduling, Tabu Search”
Habet, D., & Vasquez, M. (2005) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai.2004.110 · Cited by 28
“Very good results were obtained by M. Vasquez and J.K. Hao [ 11 ] using a TS algorithm.”
MethodSelf-citationMultiregion Mission Planning by Satellite Swarm Using Simulated Annealing and Neighborhood Search
Wu, X., Yang, Y., Xie, Y., Ma, Q., & Zhang, Z. (2023) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2023.3337066 · Cited by 26
“Vasquez et al. [21] also investigated the daily problem of scheduling SPOTS, mapping the problem to a knapsack problem and establishing a constraint satisfaction problem model.”
Background
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.