Solution Algorithm Involving Heuristics and Criterion Set Dissection to Solve Large Scale Multicriteria Knapsack Problems
DOI:
https://doi.org/10.15837/ijccc.2026.1.7267Keywords:
Multiple objective combinatorial optimization, knapsack problem, heuristicsAbstract
Multiobjective combinatorial optimization is an essential approach for handling trade-offs in complex control and communications systems, when multiple conflicting objectives (performance, cost, reliability) must be counterbalanced. Many well known combinatorial problems can be easier solved by customizing a general approach, namely by employing problem specific algorithms in key points of the general framework. In this paper we adapt the general framework PESA (2020) from continual to the discrete case taking advantage of the particular shapes of both decision and criterion space of combinatorial problems, and replace the exact optimization algorithms with new developed heuristics. The results is an anytime heuristics approach that progressively dissecting the Pareto front and deriving approximated non-dominated points. To test the performances of the approach we customized the algorithms and carried out experiments on multiple criteria multidimensional 0/1 Knapsack problems recalled from the literature. The comparative numerical results reported in the paper support the conclusion that the novel approach has the ability to generate good first-level approximations to the Pareto fronts of the addressed problems in reasonable time.
References
C. Audet, J. Bigeon, D. Cartier, S. Le Digabel, and L. Salomon (2021). Performance indicators in multiobjective optimization. European J. of Operational Research, 292(2):397-422, 2021. https://doi.org/10.1016/j.ejor.2020.11.016
X. Cai, M. Hu, D. Gong, Y. Guo, Y. Zhang, Z. Fan, and Y. Huang (2019). A decomposition-based coevolutionary multiobjective local search for combinatorial multiobjective optimization. Swarm and Evolutionary Computation, 49:178-193, 2019. https://doi.org/10.1016/j.swevo.2019.05.007
X. Cai, H. Sun, and Z. Fan (2018). A diversity indicator based on reference vectors for manyobjective optimization. Information Sciences, 430-431:467 - 486, 2018. https://doi.org/10.1016/j.ins.2017.11.051
G. Ceyhan, M. Köksalan, and B. Lokman (2019). Finding a representative nondominated set for multi-objective mixed integer programs. European J. of Operational Research, 272(1):61-77, 2019. https://doi.org/10.1016/j.ejor.2018.06.012
H. Charkhgarda, H.R. Moghaddama, A. Eshraghb, and S. Mahmoudinazlou (2025). Solving hard bi-objective knapsack problems using deep reinforcement learning. Computers & Operations Research, 55, 2025. https://doi.org/10.1016/j.disopt.2025.100879
C. Coello, A. Carlos, and M. Reyes Sierra (2004). A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm. In Raúl Monroy, Gustavo Arroyo-Figueroa, Luis Enrique Sucar, and Humberto Sossa, editors, MICAI 2004: Advances in Artificial Intelligence, pages 688-697, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-24694-7_71
C. Gomes da Silva, J. Climaco, and J. Figueira (2024). A scatter search method for the bi-criteria multi-dimensional 0,1-knapsack problem using surrogate relaxation. Journal of Mathematical Modelling and Algorithms, 3:183-208, 2004. https://doi.org/10.1023/B:JMMA.0000038617.09620.02
K. Deb and H. Jain (2014). An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4):577-601, 2014. https://doi.org/10.1109/TEVC.2013.2281535
K. Deb and K. Miettinen (2009). A Review of Nadir Point Estimation Procedures Using Evolutionary Approaches: A Tale of Dimensionality Reduction, pages pp. 1-14. Proceedings of the Multiple Criterion Decision Making (MCDM-2008) Conference., 2009.
M.A. Dominguez-Rios, F. Chicano, and E. Alba (2021). Effective anytime algorithm for multiobjective combinatorial optimization problems. Information Sciences, 565:210-228, 2021. https://doi.org/10.1016/j.ins.2021.02.074
P.O. Dusadeerungsikul and S.Y. Nof (2024). A collaborative control protocol with artificial intel-ligence for medical student work scheduling. International Journal of Computers, Communications, Control, 19(4):6686, 2024. https://doi.org/10.15837/ijccc.2024.4.6686
Matthias Ehrgott, X. Gandibleux, and A. Przybylski (2016). Exact Methods for Multi-Objective Combinatorial Optimisation, pages 817-850. Springer New York, New York, NY, 2016. https://doi.org/10.1007/978-1-4939-3094-4_19
X. Gandibleux and A. Freville (2000). Tabu search based procedure for solving the 0-1 multiobjective knapsack problem : the two objectives case. Journal of Heuristics, 6(3):361-383, 2000. https://doi.org/10.1023/A:1009682532542
I. Kaliszewski and J. Miroforidis (2022). Probing the pareto front of a large-scale multiobjective problem with a mip solver. Operational Research, 22:5617-5673, 2022. https://doi.org/10.1007/s12351-022-00708-y
A. Kaur, J.S. Dhillon, and M. Singh (2024). Emended snake optimizer to solve multiobjective hybrid energy generation scheduling. Yugoslav Journal of Operations Research, 34(4):627-668, 2024. https://doi.org/10.2298/YJOR240315018K
N. Mladenović and B. Stanojević (2025). Anytime algorithm to generate non-dominated vectors to bi-objective integer programming problems. In B. Andrić Guvsavac M. Kuzmanović, D. Makajić- Nikolić, editor, Proceedings of SymOpIs 2025, pages 324-329. FON, 2025.
G.A. Montoya, C. Lozano-Garzon, C. Paternina-Arboleda, and Y. Donoso (2025). Mathematical optimization approach for prioritized services in IoT networks for energy-constrained smart cities. International Journal of Computers, Communications, Control, 20(1):6912, 2025. https://doi.org/10.15837/ijccc.2025.1.6912
M. Nagy, J.L. de Miranda, and N. Popescu-Bodorin. Decision making and robust optimization for information systems oriented to emergency events. International Journal of Computers, Communications, Control, 19(6):6861, 2024. https://doi.org/10.15837/ijccc.2024.6.6861
O. Ozpeynirci and M. Koksalan (2010). An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Management Science, 56(12):2302- 2315, 2010. https://doi.org/10.1287/mnsc.1100.1248
P. M. Pardalos, A. Žilinskas, and J. Žilinskas (2017). Non-Convex Multi-Objective Optimization. Springer, 2017. https://doi.org/10.1007/978-3-319-61007-8
A. Rong and J.R. Figueira (2013). A reduction dynamic programming algorithm for the biobjective integer knapsack problem. European J. of Operational Research, 231(2):299-313, 2013. https://doi.org/10.1016/j.ejor.2013.05.045
B. Stanojević, S. Dzitac, and I. Dzitac (2020). Fuzzy numbers and fractional programming in making decisions. International Journal of Information Technology & Decision Making, 19(04):1123- 1147, 2020. https://doi.org/10.1142/S0219622020300037
B. Stanojević and F. Glover (2020). A new approach to generate pattern-efficient sets of nondominated vectors for multi-objective optimization. Information Sciences, 530:22-42, 2020. https://doi.org/10.1016/j.ins.2020.04.040
M. Toloo, S. Talatahari, A.H. Gandomi, and I. Rahimi (2022). 1 - multiobjective combinatorial optimization problems: social, keywords, and journal maps. In M. Toloo, S. Talatahari, and I. Rahimi, editors, Multi-Objective Combinatorial Optimization Problems and Solution Methods, pages 1-9. Academic Press, 2022. https://doi.org/10.1016/B978-0-12-823799-1.00010-3
Y. Wang and Z. Xu (2022). A multi-objective location decision making model for emer-gency shelters giving priority to subjective evaluation of residents. International Journal of Computers, Communications, Control, 17(4):4749, 2022. https://doi.org/10.15837/ijccc.2022.4.4749
Y. Wang, Z. Xu, and F.G. Filip (2022). Multi-objective model to improve network reliability level under limitedbudget by considering selection of facilities and total service distance in rescue operations. International Journal of Computers, Communications, Control, 17(1):4573, 2022. https://doi.org/10.15837/ijccc.2022.1.4573
[Online] Available at: http://web.archive.org/web/20061205225020/ and http://www.univvalenciennes.fr:80/road/mcdm/.
Additional Files
Published
Issue
Section
License
Copyright (c) 2025 Nada Mladenovic, Bogdana Stanojević
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
