Abstract
The quadratic multiple knapsack problem (QMKP) consists in assigning objects with both individual and pairwise profits to a set of limited knapsacks in order to maximize the total profit. QMKP is a NP-hard combinatorial optimization problem with a number of applications. In this paper, we present an iterated responsive threshold search (IRTS) approach for solving the QMKP. Based on a combined use of three neighborhoods, the algorithm alternates between a threshold-based exploration phase where solution transitions are allowed among those satisfying a responsive threshold and a descent-based improvement phase where only improving solutions are accepted. A dedicated perturbation strategy is utilized to ensure a global diversification of the search procedure. Extensive experiments performed on a set of 60 benchmark instances in the literature show that the proposed approach competes very favorably with the current state-of-the-art methods for the QMKP. In particular, it discovers 41 improved lower bounds and attains all the best known results for the remaining instances. The key components of IRTS are analyzed to shed light on their impact on the performance of the algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Our best results are available at http://www.info.univ-angers.fr/pub/hao/qmkp.html. The source code of the IRTS algorithm will also be available.
We thank the authors of García-Martínez et al. (2014) for providing us with these values.
This is confirmed by the authors of Soak and Lee (2012).
References
Billionnet, A., & Soutif, E. (2004). An exact method for the 0–1 quadratic knapsack problem based on Lagrangian decomposition. European Journal of Operational Research, 157(3), 565–575.
Caprara, A., Pisinger, D., & Toth, P. (1999). Exact solution of the quadratic knapsack problem. INFORMS Journal on Computing, 11(2), 125–137.
Corder, G. W., & Foreman, D. I. (2014). Nonparametric statistics for non-statisticians: A step-by-step approach. Hoboken, NJ: Wiley.
Dueck, G., & Scheuer, T. (1990). Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Journal of Computational Physics, 90, 161–175.
Dueck, G. (1993). New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104, 86–92.
Di, Gaspero L., & Schaerf, A. (2006). Neighborhood portfolio approach for local search applied to timetabling problems. Journal of Mathematical Modeling and Algorithms, 5(1), 65–89.
Gallo, G., Hammer, P. L., & Simeone, B. (1980). Quadratic knapsack problems. Mathematical Programming Studies, 20, 132–149.
Glover, F., McMillan, C., & Glover, R. (1984). A heuristic programming approach to the employee scheduling problem and some thoughts on managerial robots. Journal of Operations Management, 4(2), 113–128.
Glover, F. (1995). Tabu thresholding: improved search by nonmonotonic trajectories. ORSA Journal on Computing, 7(4), 426–442.
García-Martínez, C., Glover, F., Rodríguez, F. J., Lozano, M., & Martí, R. (2014). Strategic oscillation for the quadratic multiple knapsack problem. Computational Optimization and Applications, 58(1), 161–185.
García-Martínez, C., Rodríguez, F. J., & Lozano, M. (2014). Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem. European Journal of Operational Research, 232(3), 454–463.
Hiley, A., & Julstrom, B. (2006). The quadratic multiple knapsack problem and three heuristic approaches to it. In Proceedings of the genetic and evolutionary computation conference (GECCO) (pp. 547–552).
Hung, M. S., & Fisk, J. C. (1978). An algorithm for 0–1 multiple-knapsack problems. Naval Research Logistics Quarterly, 25(3), 571–579.
Kellerer, H., Pferschy, U., & Pisinger D. (2004). Knapsack problems. New York: Springer., ISBN 3-540-40286-1.
Lü, Z., Hao, J. K., & Glover, F. (2011). Neighborhood analysis: A case study on curriculum-based course timetabling. Journal of Heuristics, 17(2), 97–118.
Lü, Z., Glover, F., & Hao, J. K. (2014). Neighborhood combination for unconstrained binary quadratic problems. In M. Caserta, & S. Voss (Eds.), Metaheuristics international conference 2011 post-conference book, chapter 4, pp. 49–61.
Martello, S., & Toth, P. (1981). Heuristic algorithms for the multiple knapsack problem. Computing, 27(2), 93–112.
Pisinger, D. (2007). The quadratic knapsack problem—A survey. Discrete Applied Mathematics, 155(5), 623–648.
Pisinger, D. (2009). An exact algorithm for large multiple knapsack problems. European Journal of Operational Research, 114(3), 528–541.
Saraç, T., & Sipahioglu, A. (2007). A genetic algorithm for the quadratic multiple knapsack problem. In Proceeding of second international symposium on advances in brain, vision, and artificial intelligence. Lecture notes in computer science, 4729, pp. 490–498.
Singh, A., & Baghel, A. (2007). A new grouping genetic algorithm for the quadratic multiple knapsack problem. In Proceedings of international conference on evolutionary computation in combinatorial optimization. Lecture notes in computer science, 4446, pp. 210–218.
Soak, S., & Lee, S. (2012). A memetic algorithm for the quadratic multiple container packing problem. Applied Intelligence, 36, 119–135.
Sundar, S., & Singh, A. (2010). A swarm intelligence approach to the quadratic multiple knapsack problem. In Proceeding of 17the international conference on neural information processing. Lecture notes in computer science, 6443, pp. 626–633.
Wang, H., Kochenberger, G., & Glover, F. (2012). A computational study on the quadratic knapsack problem with multiple constraints. Computers and Operations Research, 39(1), 3–11.
Acknowledgments
We are grateful to the reviewers for their insightful comments which helped us improve the paper. We would like to thank Dr. García-Martínez for answering our questions and making the codes of García-Martínez et al. (2014), García-Martínez et al. (2014) available to us. This work is partially supported by the RaDaPop (2009–2013) and LigeRo projects (2009–2013) from the Region of Pays de la Loire (France). Support for Yuning Chen from the China Scholarship Council is also acknowledged.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, Y., Hao, JK. Iterated responsive threshold search for the quadratic multiple knapsack problem. Ann Oper Res 226, 101–131 (2015). https://doi.org/10.1007/s10479-014-1720-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-014-1720-5