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 101–200 of 239
Proof-of-Useful-Work: BlockChain Mining by Solving Real-Life Optimization Problems
Todorović, M., Matijević, L., Ramljak, D., Davidović, T., Urošević, D., Krüger, T. J., & Jovanović, Đ. (2022) · Symmetry · doi:10.3390/sym14091831 · Cited by 27
A Hybrid Genetic Algorithm for Satellite Image Downlink Scheduling Problem
Song, B., Yao, F., Chen, Y., Chen, Y., & Chen, Y. (2018) · Discrete Dynamics in Nature and Society · doi:10.1155/2018/1531452 · Cited by 27
A hybrid binary artificial bee colony algorithm for the satellite photograph scheduling problem
Luo, K. (2019) · Engineering Optimization · doi:10.1080/0305215x.2019.1657113 · Cited by 24
“This work extends the special model for the SPOT-5 daily photograph scheduling problem (Vasquez and Hao 2001).”
BackgroundMethodInfluentialA Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
Zufferey, N., & Vasquez, M. (2014) · RAIRO - Operations Research · doi:10.1051/ro/2014027 · Cited by 23
Self-citationMission Planning Issues of Imaging Satellites: Summary, Discussion, and Prospects
Zhang, G., Li, X., Hu, G., Zhang, Z., An, J., & Man, W. (2021) · International Journal of Aerospace Engineering · doi:10.1155/2021/7819105 · Cited by 26
“[6] who then developed a constraint satisfaction model for the singlesatellite planning problem of SPOT-5 considering the platform storage capacity constraint and solved the model using a forbidden search algorithm.”
MethodA Novel Spaceborne SAR Constellation Scheduling Algorithm for Sea Surface Moving Target Search Tasks
Liu, D., Chang, S., Deng, Y., He, Z., Wang, F., Zhang, Z., Han, C., & Yu, C. (2024) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2024.3355974 · Cited by 25
“Vasquez and Hao [18] approached the satellite scheduling problem through a knapsack model and introduced a tabu search algorithm for its resolution.”
BackgroundAn exact algorithm optimizing coverage-resolution for automated satellite frame selection
Song, D., van der Stappen, A. F., & Goldberg, K. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2004.1307130 · Cited by 24
“More recent research [7], [9], [17], [26] on the SM problem and its variations focuses on developing exact and approximate methods for some applications and using techniques like column generation, Tabu search, and genetic algorithms.”
MethodReactive Dialectic Search Portfolios for MaxSAT
Ansótegui, C., Pon, J., Sellmann, M., & Tierney, K. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10660 · Cited by 22
“MaxSAT solvers have been used to effectively tackle problems in several domains, such as scheduling (Vasquez and Hao 2001), FPGA routing (Xu, Rutenbar, and Sakallah 2003), and circuit design and debugging (Safarpour et al. 2007), among many others.”
MethodScatter Search for the 0–1 Multidimensional Knapsack Problem
Hanafi, S., & Wilbaut, C. (2008) · Journal of Mathematical Modelling and Algorithms · doi:10.1007/s10852-008-9078-9 · Cited by 24
“Applications range from cutting stocks [9] to the more recent daily scheduling of satellite photographs [26].”
BackgroundEssential Particle Swarm Optimization queen with Tabu Search for MKP resolution
Ktari, R., & Chabchoub, H. (2013) · Computing · doi:10.1007/s00607-013-0316-2 · Cited by 20
“There are other applications such as cutting stock [21], loading problems [22], processor allocation in distributed systems [23] and the daily management of a satellite [24].”
BackgroundA new hybrid combinatorial genetic algorithm for multidimensional knapsack problems
Lai, G., Yuan, D., & Yang, S. (2014) · The Journal of Supercomputing · doi:10.1007/s11227-014-1268-9 · Cited by 20
“Recently, the MKP has been used to model the daily management of a remote sensing satellite like SPOT, which consists in deciding which photographs every day will be attempted in the next day [1].”
MethodEnergy-Dependent Mission Planning for Agile Earth Observation Satellite
Zhao, L., Wang, S., Hao, Y., & Wang, Y. (2018) · Journal of Aerospace Engineering · doi:10.1061/(asce)as.1943-5525.0000949 · Cited by 22
A Multiple Agile Satellite Staring Observation Mission Planning Method for Dense Regions
Huang, W., Wang, H., Yi, D., Wang, S., Zhang, B., & Cui, J. (2023) · Remote Sensing · doi:10.3390/rs15225317 · Cited by 19
Yang, W., Chen, Y., He, R., Chang, Z., & Chen, Y. (2018) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2018.8477851 · Cited by 22
“The traditional EOS scheduling problem has been intensively investigated in [1-11].”
BackgroundHierarchical Reinforcement-Learning for Real-Time Scheduling of Agile Satellites
Ren, L., Ning, X., & Li, J. (2020) · IEEE Access · doi:10.1109/access.2020.3040748 · Cited by 22
“Many researchers constructed many different models, such as the integer programming model, constraint satisfaction model, graph theory modeling, and generalized backpack model [2]–[5].”
BackgroundBattery-aware scheduling in low orbit: the GomX–3 case
Bisgaard, M., Gerhardt, D., Hermanns, H., Krčál, J., Nies, G., & Stenger, M. (2018) · Formal Aspects of Computing · doi:10.1007/s00165-018-0458-2 · Cited by 19
Wu, G., Wang, H., Li, H., Pedrycz, W., Qiu, D., Ma, M., & Liu, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.6098 · Cited by 23
“B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 0 500 1000 1500 2000 2500 3000 3500 4000 4500 Index of each scenario P ro fit ASA-DTC ACO-LS-STC TS-STC ASA-STC ACO-STC GA-STC SA-STC HPFS-STC C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 0 500 1000 1500 2000 2500 3000 3500 Index of each scenario P ro fit ASA-DTC ACO-LS-STC TS-STC ASA-STC ACO-STC GA-S…”
BackgroundMethodInfluentialLiu, L., Dong, Z., Su, H., & Yu, D. (2021) · Sensors · doi:10.3390/s21196660 · Cited by 21
Tabu Search to Solve Real-Life Combinatorial Optimization Problems: A Case of Study
Habet, D. (2009) · Studies in computational intelligence · doi:10.1007/978-3-642-01085-9_6 · Cited by 17
“Hao using a dedicated Tabu Search algorithm [ 28 ].”
MethodBuilding state-of-the-art sat solvers
Lynce, I., & Marques-Silva, J. P. (2002) · ePrints Soton (University of Southampton) · Cited by 20
Satellite Imaging Order Scheduling with Stochastic Weather Condition Forecast
Liao, D.-Y., & Yang, Y.-T. (2006) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2005.1571528 · Cited by 22
“Vasquez and Hao [10] formulate the daily photograph-scheduling problem of SPOT as a generalized version of the knapsack model and solve by a dedicated Tabu search algorithm.”
MethodMaximum satisfiability using cores and correction sets
Bjørner, N., & Narodytska, N. (2015) · International Conference on Artificial Intelligence · Cited by 16
Mission Planning for Agile Earth Observing Satellite Based on Genetic Algorithm
Han, P., He, Z., Geng, Y., Guo, Y., Li, C., & Zhao, G. (2019) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2019.8865283 · Cited by 17
“Some mathematical models have been proposed to describe mission planning, such as the graph theoretic([1]), the knapsack model([2]), integer programming([3]), and the constraint satisfaction framework([4]).”
MethodMulti Criteria Decision Making for the Multi-Satellite Image Acquisition Scheduling Problem
Vasegaard, A. E., Picard, M., Hennart, F., Nielsen, P. A., & Saha, S. (2020) · Sensors · doi:10.3390/s20051242 · Cited by 19
“Mansour and Dessouky [11] extended the model of Vasquez and Hao [12] and proposed a genetic algorithm based search technique for maximizing the number of images as well as profits.”
BackgroundInfluentialStrong formulation for the spot 5 daily photograph scheduling problem
Ribeiro, G. M., Constantino, M. F., & Lorena, L. A. N. (2009) · Journal of Combinatorial Optimization · doi:10.1007/s10878-009-9215-z · Cited by 15
“This formulation is obtained by strengthening a model by Vasquez and Hao (2001) with valid inequalities that arise in node packing and k-regular independent system polyhedra, the so-called clique inequalities.”
BackgroundMethodInfluentialFixed Interval Scheduling of Multiple Earth Observation Satellites with Multiple Observations
Wang, X., Leus, R., & Han, C. S. (2018) · International Conference on Mechanical and Aerospace Engineering · doi:10.1109/icmae.2018.8467667 · Cited by 16
“In a logic-constrained knapsack model, Vasquez and Hao [3] developed a tabu algorithm for daily scheduling of an EOS.”
BackgroundMethodInfluentialA threshold search based memetic algorithm for the disjunctively constrained knapsack problem
Wei, Z., & Hao, J. (2021) · Computers & Operations Research · doi:10.1016/j.cor.2021.105447 · Cited by 14
Self-citationResponsive strategic oscillation for solving the disjunctively constrained knapsack problem
Wei, Z., Hao, J., Ren, J., & Glover, F. (2023) · European Journal of Operational Research · doi:10.1016/j.ejor.2023.02.009 · Cited by 14
“To complete the comparison, we also tested the 21 benchmark instances from the real-life daily photograph scheduling problem (DPSP) of the earth observation satellite SPOT5 [3,44].”
BackgroundMethodSelf-citationHyper-Reactive Tabu Search for MaxSAT
Ansótegui, C., Heymann, B., Pon, J., Sellmann, M., & Tierney, K. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-05348-2_27 · Cited by 13
A Constraint Programming Approach for Agile Earth Observation Satellite Scheduling Problem
Küçük, M., & Topaloğlu, Ş. (2019) · International Conference on Recent Advances in Space Technologies · doi:10.1109/rast.2019.8767841 · Cited by 17
“Based on this data, Vasquez and Hao [7] have presented a tabu search algorithm together with a logicconstrained knapsack formulation.”
MethodDaily imaging scheduling of an Earth observation satellite
Lin, W.-C., Liu, C.-Y., Liao, D.-Y., & Lee, Y.-Y. (2004) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2003.1244686 · Cited by 17
Peng, S., Chen, H., Li, J., & Ning, J. (2017) · Mathematical Problems in Engineering · doi:10.1155/2017/7304506 · Cited by 15
“Then they are solved by metaheuristic algorithms (like genetic algorithm [3, 6, 13], tabu search [14, 15], and ant colony optimization [9]), mathematical programmingmethods (like Lagrangian relaxation [2, 12], branch and cut [7], and column generation [8]), and other domain knowledge based heuristic approaches [10, 16…”
MethodTask Packing: Efficient task scheduling in unbalanced parallel programs to maximize CPU utilization
Utrera, G., Farreras, M., & Fornes, J. (2019) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2019.08.003 · Cited by 12
“The knapsack problem has a long tradition of applications in cryptography [26, 27], production planning [28] and scheduling [29, 30] between others.”
BackgroundMulti-Satellite Resource Scheduling Based on Deep Neural Network
Meng, H., Li, C., Lu, W., Dong, Y., Zhao, Z., & Wu, B. (2019) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2019.8852044 · Cited by 13
Optimization of Single-Satellite Operational Schedules Towards Enhanced Communication Capacity
Spangelo, S., & Cutler, J. (2012) · AIAA Guidance, Navigation, and Control Conference and Exhibit · doi:10.2514/6.2012-4610 · Cited by 15
“The EOS problem is often generalized and formulated with a common problem structure, such as a knapsack problem [13, 14], a packing problem [15], a single-machine scheduling problem [16], or a network flow problem [17].”
BackgroundA hybrid discrete particle swarm optimization for satellite scheduling problem
Zhang, D., Guo, L., Cai, B., Sun, N., & Wang, Q. (2013) · IEEE Conference Anthology · doi:10.1109/anthology.2013.6784716 · Cited by 11
Dupont, A., Alvernhe, E., & Vasquez, M. (2004) · Annals of Operations Research · doi:10.1023/b:anor.0000032575.38969.ab · Cited by 11
“This method has been applied to some industrial problems adjacent to the FAPP (Vasquez, 2002): the Daily Photographs Satellite Problem (DPSP) (Vasquez and Hao, 2001b) and the Antenna Positioning Problem (APP) (Vasquez and Hao, 2001a), which is the upstream problem of the FAPP.”
MethodSelf-citationAn optimization approach to the planning of Earth observing satellites
Bianchessi, N., Piuri, V., Righini, G., Roveri, M., Laneve, G., & Zigrino, A. (2004) · Virtual Community of Pathological Anatomy (University of Castilla La Mancha) · Cited by 12
Li, F., Wan, Q., Wen, F., Zou, Y., He, Q., Li, D., & Zhong, X. (2024) · Remote Sensing · doi:10.3390/rs16010194 · Cited by 12
“Bianchessi et al. [10] addressed the multiple satellite and multiple orbit problem by proposing a tabu search heuristic [11] that selects and schedules requests to maximize the total utility under operational constraints.”
A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems
Bouhmala, N. (2014) · The Scientific World JOURNAL · doi:10.1155/2014/798323 · Cited by 10
“Examples include routing [2], scheduling [3], modelchecking [4] of finite state systems, design debugging [5], AI planning [6], and electronic markets [7].”
BackgroundConsistent Neighbourhood in a Tabu Search
Vasquez, M., Dupont, A., & Habet, D. (2005) · Springer eBooks · doi:10.1007/0-387-25383-1_17 · Cited by 11
Self-citationThe integrated agile Earth observation satellite scheduling problem
Rocha, Y., Chagas, G. O., Coelho, L. C., & Subramanian, A. (2025) · Computers & Operations Research · doi:10.1016/j.cor.2025.107212 · Cited by 13
Baek, S., Cho, K.-R., Lee, D.-W., & Kim, H. (2010) · Journal of the Korean Society for Aeronautical & Space Sciences · doi:10.5139/jksas.2010.38.1.048 · Cited by 9
Mitrović-Minić, S., Thomson, D., Berger, J., & Secker, J. (2019) · Springer optimization and its applications · doi:10.1007/978-3-030-10501-3_11 · Cited by 12
Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing
Makarov, A., Taddei, M. M., Osaba, E., Franceschetto, G., Villar-Rodríguez, E., & Oregi, I. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-48232-8_1 · Cited by 8
“Our classical formulation for the SPOT5 instances (we refer the reader to [2] for a complete description of the structure of the instances) is largely inspired by [19], and it can be stated in the language of mathematical programming as follows.”
BackgroundJoint Scheduling of Heterogeneous Earth Observing Satellites for Different Stakeholders
Wang, P., & Tan, Y. (2008) · SpaceOps Conference (SpaceOps) · doi:10.2514/6.2008-3512 · Cited by 8
Wang, J., Demeulemeester, E. L., Qiu, D., & Jin, L. (2015) · SSRN Electronic Journal · doi:10.2139/ssrn.2634934 · Cited by 11
“Metaheuristics: A large number of metaheuristics were proposed for EOS scheduling, which primarily contain tabu search algorithms [5, 9, 11, 31, 33, 41, 51, 52], genetic algorithms [2, 23, 26, 38, 39, 49, 51], ant colony algorithms [27, 45, 50], local search algorithms [24, 25, 43] and simulated annealing algorithms […”
Multi-Satellite Observation-Relay Transmission-Downloading Coupling Scheduling Method
He, C., & Dong, Y. (2023) · Remote Sensing · doi:10.3390/rs15245639 · Cited by 8
Model-Guided Approaches for MaxSAT Solving
Morgado, A., Heras, F., & Marques-Silva, J. P. (2013) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai.2013.142 · Cited by 7
“Other applications include routing problems [9], bioinformatics problems such as Protein Alignment [10] or Reasoning over Biological Networks[11], scheduling [12], course timetabling [13], [14], and more.”
BackgroundThe Impact of Max-SAT Resolution-Based Preprocessors on Local Search Solvers
Heras, F., & Bañeres, D. (2010) · Journal on Satisfiability Boolean Modeling and Computation · doi:10.3233/sat190080 · Cited by 7
“They include academic problems such as Max-Cut or Max-Clique , and real problems in domains like routing [46], bioinformatics [40], scheduling [45], probabilistic reasoning [33] and electronic markets [36].”
A Scheduling Method of Using Multiple SAR Satellites to Observe a Large Area
Zheng, Q., Yue, H., Liu, D., & Jia, X. (2023) · Sensors · doi:10.3390/s23063353 · Cited by 8
“Studies [26,27] presented a formulation of the problem that includes numerous binary and ternary logical constraints, and they tested the tabu search algorithm with realistic benchmark instances.”
MethodCho, K.-R., Baek, S., & Lee, D.-W. (2010) · Journal of Institute of Control Robotics and Systems · doi:10.5302/j.icros.2010.16.6.572 · Cited by 7
Solving the swath segment selection problem through Lagrangean relaxation
Cordone, R., Gandellini, F., & Righini, G. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2006.04.005 · Cited by 7
Liu, L., Dong, Z., Su, H., Yu, D., & Yu, L. (2021) · IEEE Advanced Information Technology, Electronic and Automation Control Conference (IAEAC) · doi:10.1109/iaeac50856.2021.9390990 · Cited by 6
“…scheduling problems, they build diverse models by setting up different constrains according to their needs, and use methods like ant colony algorithm (ACO) [1-3], simulated annealing (SA) algorithm[4, 5], genetic algorithm (GA) [6-8] , tabu search algorithm (TS) [9-11], etc. to solve them.”
MethodSummary of intelligent algorithms in planning & scheduling of Earth observation satellite
Wang, H., Li, X., Liu, Y., & Zhou, B. (2010) · IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS) · doi:10.1109/icicisys.2010.5658475 · Cited by 6
“Vasquez [4] think that the Earth observation satellite mission planning problem is a multidimensional knapsack problem, and establish the following mathematical model: n n max Lg, xx, , sub ject to Lm, xx, j .. l ",.,1 fe,xx,s,M ,'v'{i,j} 31, x,+x}S,I, 'v'i,x, 3 {o,l} i .. 1 (2) In the equation,…”
BackgroundAnalysis and Design of Fault-Tolerant Scheduling for Real-Time Tasks on Earth-Observation Satellites
Zhu, X., Wang, J., Wang, J., & Qin, X. (2014) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2014.58 · Cited by 6
The Satellite Downlink Scheduling Problem: A Case Study of RADARSAT-2
Karapetyan, D., Mitrović-Minić, S., Malladi, K. T., & Punnen, A. P. (2014) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4939-1007-6_21 · Cited by 6
(2008) · DSpace@MIT (Massachusetts Institute of Technology)
A modified genetic algorithm for large-scale and joint satellite mission planning
Zheng, Q., Cai, Y., & Wang, P. (2025) · Egyptian Informatics Journal · doi:10.1016/j.eij.2025.100713 · Cited by 5
Vasegaard, A. E., Moon, I., Nielsen, P. A., & Saha, S. (2022) · Flexible Services and Manufacturing Journal · doi:10.1007/s10696-022-09444-z · Cited by 6
“2017), is shown to be a generalization of the knapsack problem (Vasquez and Hao 2001) as well as equivalent to that of the piecewise linear cluster restricted maximum weight clique problem (Malladi et al.”
BackgroundThe Knapsack Problem and Its Variants: Formulations and Solution Methods
Wilbaut, C., Hanafi, S., Coelho, I. M., & Lucena, A. (2022) · Springer eBooks · doi:10.1007/978-3-030-96935-6_4 · Cited by 5
Alonso, C. L., Caro, F., & Montaña, J. L. (2005) · Lecture notes in computer science · doi:10.1007/11499305_7 · Cited by 5
“Many practical problems can be formulated as a MKP instance: the capital budgeting problem in economy; the allocation of databases and processors in a distributed computer system ([6]) or, more recently, the problem of the daily management of a remote sensing satellite ([ 15 ]).”
BackgroundYang, B., Wang, M., Jin, S., & Pan, J. (2012) · The international archives of the photogrammetry, remote sensing and spatial information sciences/International archives of the photogrammetry, remote sensing and spatial information sciences · doi:10.5194/isprsarchives-xxxix-b1-339-2012 · Cited by 5
“…and optimization algorithms are proposed, such as ant colony algorithm, greedy algorithm, the local optimal search algorithm, dynamic programming algorithm, constraint programming algorithm and so on (Lemaitre et al., 2002; Aarts and Lenstra, 2003; Bensana et al., 1996; Vasquez and Hao, 2001).”
MethodSuboptimal colorings and solution of large chromatic scheduling problems
Blöchliger, I. (2005) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-3363 · Cited by 5
Modeling and Optimizing Space Networks for Improved Communication Capacity
Spangelo, S. (2013) · Deep Blue (University of Michigan) · Cited by 10
Systems and Algorithms for Collaborative Teleoperation
Song, D. (2004) · Cited by 6
On the Computational Complexity of MaxSATPreprint
Halaby, M. E. (2016) · Electronic colloquium on computational complexity · Cited by 5
Yoda, K., & Prékopa, A. (2016) · Mathematics of Operations Research · doi:10.1287/moor.2015.0749 · Cited by 5
A GRASP for Next Generation Sapphire Image Acquisition Scheduling
Wang, Y., Mitrović-Minić, S., Leitch, R., & Punnen, A. P. (2016) · International Journal of Aerospace Engineering · doi:10.1155/2016/3518537 · Cited by 4
“Vasquez and Hao (2001) [2] formulated the daily photograph scheduling of an Earth observation satellite as a knapsack model and proposed a tabu search algorithm to determine the scheduling.”
BackgroundClosed-Loop Multi-Satellite Scheduling Based on Hierarchical MDP
Tharmarasa, R., Chatterjee, A., Wang, Y., Kirubarajan, T., Berger, J., & Florea, M. C. (2019) · International Conference on Information Fusion (FUSION) · doi:10.23919/fusion43075.2019.9011427 · Cited by 7
“Many EOS scheduling problems are solved in open-loop forms [1], [4], [13], [17], which cannot handle the failure of tasks due to uncertainties such as the presence of clouds.”
BackgroundChang, Z., & Li, J. F. (2015) · Advances in engineering research/Advances in Engineering Research · doi:10.2991/eame-15.2015.148 · Cited by 4
Variable Neighbourhood Decomposition Search with Bounding for Multidimensional Knapsack Problem
Hanafi, S., Lazić, J., Mladenović, N., & Wilbaut, C. (2009) · IFAC Proceedings Volumes · doi:10.3182/20090603-3-ru-2001.00339 · Cited by 4
A Taxonomy of Exact Methods for Partial Max-SAT
Menaï, M. E. B., & Al-Yahya, T. N. (2013) · Journal of Computer Science and Technology · doi:10.1007/s11390-013-1325-5 · Cited by 5
“Keywords Partial Max-SAT, Davis-Putnam-Logenmann-Loveland, branch and bound, unsatisfiability, pseudo-Boolean optimization”
BackgroundVasquez, M., Dupont, A., & Habet, D. (2003) · RAIRO - Operations Research · doi:10.1051/ro:2004004 · Cited by 4
“Note that the ∆ evaluation is carried out very quickly using efficient incremental techniques, which are now well known [5, 6, 15, 16].”
MethodSelf-citationUNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE
Silva, P. H. G. (2015) · Cited by 4
An Efficient Task Autonomous Planning Method for Small Satellites
Long, J., Li, C., Zhu, L., Chen, S., & Liu, J. (2018) · Information · doi:10.3390/info9070181 · Cited by 4
“The task planning of the satellites [24–27] is Non-deterministic Polynomial hard [28], taking the time-dependency and resource-dependency into consideration, hence, making the modeling even more difficult.”
BackgroundHao, H.-C., Jiang, W., Li, Y., & Pang, Z.-H. (2012) · International Conference on Management Science and Engineering (ICMSE) · doi:10.1109/icmse.2012.6414177 · Cited by 3
“In previous studies, satellite mission planning and multi-user requirements are studied by using the following methods([15-20]).”
MethodQuery-guided maximum satisfiability
Zhang, X., Mangal, R., Nori, A. V., & Naik, M. (2016) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/2837614.2837658 · Cited by 5
“A number of interesting problems that span across a diverse set of areas such as program reasoning [24, 25, 35, 58], information retrieval [14, 29, 45, 48], databases [5, 40], circuit design [56], bioinformatics [16, 52], planning and scheduling [26, 53, 57], and many others can be naturally encoded as MAXSAT formulae.”
BackgroundVasegaard, A. E., Picard, M., Nielsen, P. A., & Saha, S. (2024) · IEEE Access · doi:10.1109/access.2024.3366454 · Cited by 4
Zhao, Q., Jiang, B., Yu, X., & Zhang, Y. (2021) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2021092 · Cited by 3
“demand for satellite images, researchers and task managers have successfully improved the utilization of single satellite and small satellite constellation by applying operational research and optimization methods to satellite business [16, 6, 7].”
BackgroundSolving MaxSAT by Successive Calls to a SAT Solver
Halaby, M. E. (2017) · Lecture notes in networks and systems · doi:10.1007/978-3-319-56994-9_31 · Cited by 3
“Many theoretical and practical problems can be encoded into SAT and MaxSAT such as debugging [51], circuits design and scheduling of how an observation satellite captures photos of Earth [56], course timetabling [11, 45, 41, 34], software package upgrades [24], routing [58, 46], reasoning [52] and protein structure al…”
BackgroundOptimal path planning for multi-target observation of remote sensing satellite
Li, H., & Li, Y. (2016) · IEEE CSAA Guidance, Navigation and Control Conference (CGNCC) · doi:10.1109/cgncc.2016.7828847 · Cited by 3
“Current researches often use various algorithms to solve the satellite scheduling problem which can be divided into optimization algorithm, the heuristic algorithm based on rules and intelligent optimization algorithm [2-9].”
MethodClustered genetic algorithm to solve multidimensional knapsack problem
Gupta, I. K., Choubey, A., & Choubey, S. (2017) · International Conference on Computing, Communication and Networking Technologies (ICCCNT) · doi:10.1109/icccnt.2017.8204118 · Cited by 3
“Currently, MDKP has been applied in modeling of daily management of remote satellite like SPOT, which consisted in deciding each day what photographs will be attempted the next day [13].”
MethodSong, Y., Ma, X., Zhang, Z., Xing, L., & Chen, Y. (2018) · Communications in computer and information science · doi:10.1007/978-981-13-2826-8_39 · Cited by 5
Imperialist Competitive Algorithm with Independence and Constrained Assimilation
Dzalbs, I., Kalganova, T., & Dear, I. (2020) · International Congress on Human-Computer Interaction, Optimization and Robotic Applications (ICHORA) · doi:10.1109/hora49412.2020.9152916 · Cited by 3
“[2], cargo loading [3], satellite management [4], project selection [5] and capital budgeting [6].”
Xing, L., Hu, X., Hu, N., Xia, W., & Sun, H. (2025) · Expert Systems with Applications · doi:10.1016/j.eswa.2025.130724 · Cited by 3
Consistent Neighborhood Search for Combinatorial Optimization
Vasquez, M., & Zufferey, N. (2012) · ISRN Computational Mathematics · doi:10.5402/2012/671423 · Cited by 2
Self-citationLi, V. C., Liang, Y.-C., Sun, Y.-Y., & Chen, Y.-S. (2012) · Journal of the Chinese Institute of Industrial Engineers · doi:10.1080/10170669.2012.743643 · Cited by 2
“Many applications of the MKP are to allocate resources, such as cutting stock [8], project selection [33], loading [36], and scheduling of satellite photographs [37].”
BackgroundResearch on Multi-satellite Observation Multi-region Task Planning based on Genetic Algorithm
Zhang, Y., Wang, J., Yuan, B., Wang, C., & Shi, L. (2019) · IOP Conference Series Materials Science and Engineering · doi:10.1088/1757-899x/685/1/012002 · Cited by 2
“Similar to the French SPOT-5 satellite system[3], the US Landsat-7 satellite system[4], the EO-1 satellite system[5], etc., in the past, China’s satellites were managed separately and independently, according to professional vertical protection, various satellites and their The application system…”
ResultCubeSat Mission Scheduling Method Considering Operational Reliability
Zhang, J., He, C., Zhang, Y., Qi, X., & Yang, X. (2024) · Energies · doi:10.3390/en17020490 · Cited by 3
Song, Y., Ou, J., Pham, D. T., Li, J.-T., Huang, J.-B., & Xing, L. (2023) · Communications in computer and information science · doi:10.1007/978-981-99-1549-1_7 · Cited by 2
On Relaxing and Steady State Genetic Methods for Satellite Imaging Scheduling
Xiao-shan, J., Li, J., & Jing, N. (2008) · ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD) · doi:10.1109/snpd.2008.108 · Cited by 2
“But their upper bound is not good enough and lacks the optimal feasible solution (Vasquez and Hao, 2001a, 2001b).”
BackgroundChen, S.-J., Li, Z., & Hu, M. (2019) · IOP Conference Series Materials Science and Engineering · doi:10.1088/1757-899x/608/1/012030 · Cited by 2
RETRACTED: Resource satellite intelligent management and control mode based on mission planning
Lu, H. M., Xue, H., & Xiong, J. (2019) · International Journal of Electrical Engineering Education · doi:10.1177/0020720919883807 · Cited by 2
RetractedVasegaard, A. E., & Nielsen, P. (2021) · International Conference on Robotics, Control and Automation (ICRCA) · doi:10.1145/3471985.3472382 · Cited by 2
Mini-bucket Elimination with Bucket Propagation
Rollón, E., & Larrosa, J. (2006) · Lecture notes in computer science · doi:10.1007/11889205_35 · Cited by 2
“These frameworks have important applications in fields such as routing [4], bioinformatics [5], scheduling [6] or probabilistic reasoning [7].”
BackgroundUn algorithme de programmation par contraintes pour la recherche d'allocations leximin-optimales
Bouveret, S., & Lemaître, M. (2006) · HAL · Cited by 2
Dzalbs, I., Kalganova, T., & Dear, I. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.06617 · Cited by 2
Performance of population size on Knapsack problem
Oyewola, D. O., Hakimi, D., Yahaya, A. Y., & Bolarin, G. (2016) · New Trends in Mathematical Science · doi:10.20852/ntmsci.2016.111 · Cited by 1
Exploring Tabu Tenure Policies with Machine Learning
Konovalenko, A., & Hvattum, L. M. (2025) · Electronics · doi:10.3390/electronics14132642 · Cited by 3
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.