Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

Minimum Complete Pareto Front of the Biobjective 0-1 Knapsack Problem

,

DOI: http://dx.doi.org/10.15439/2026F8577

Citation: Lasko Laskov,

Full text

Abstract. We propose an exact algorithm that constructs the minimum complete Pareto front of the biobjective knapsack problem with one linear objective function (that represents profit) and one nonlinear objective function (that represents risk). The algorithm is composed by two stages. The first stage is using a dynamic programming scheme that constructs a Pareto optimal solution that maximizes the profit objective function, and it is applied in the standard setup of the knapsack problem in which the total weight of the items is bigger than the capacity of the knapsack. In the trivial setup of the problem, in which the total weight of the items is less or equal to the capacity, we apply a greedy algorithm that constructs the remaining solutions that are not constructed in the first stage. We prove mathematically the correctness, the computational complexity and the memory complexity of the proposed algorithm. We demonstrate its execution using comprehensive numerical examples, and we demonstrate its applicability for large-scale instances in the provided experiments results.

References

  1. H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, 1st ed. Berlin Heidelberg: Springer-Verlag, 2004. ISBN 978-3-540-24777-7
  2. K. Miettinen, Nonlinear multiobjective optimization, 1st ed., ser. International Series in Operations Research & Management Science. Boston, USA: Springer New York, NY, 1999, vol. 12. ISBN 978-0-7923-8278-2. https://dx.doi.org/10.1007/978-1-4615-5563-6
  3. V. Cacchiani, M. Iori, A. Locatelli, and S. Martello, “Knapsack problems – an overview of recent advances. part i: Multiple, multidimensional, and quadratic knapsack problems,” Computers & Operations Research, vol. 143, p. 105693, 2022. https://dx.doi.org/10.1016/j.cor.2021.105693
  4. M. J. Rosenblatt and Z. Sinuany-Stern, “Generating the discrete efficient frontier to the capital budgeting problem,” Operations Research, vol. 37, no. 3, pp. 384–394, 1989. https://dx.doi.org/10.1287/opre.37.3.384
  5. M. Eben-Chaime, “Parametric solution for linear bicriteria knapsack models,” Management Science, vol. 42, no. 11, pp. 1565–1575, 1996. https://dx.doi.org/10.1287/mnsc.42.11.1565
  6. U.-E. Lukata and J. Teghem, “Solving multi-objective knapsack problem by a branch-and-bound procedure,” in Multicriteria Analysis (Proceedings of the 6th International Conference on MCDM), J. Clímaco, Ed. Berlin, Heidelberg: Springer, 1997. https://dx.doi.org/10.1007/978-3-642-60667-0_26 pp. 269–278.
  7. M. Visée, J. Teghem, M. Pirlot, and E. L. Ulungu, “Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem,” Journal of Global Optimization, vol. 12, no. 2, pp. 139–155, 1998. https://dx.doi.org/10.1023/A:1008258310679
  8. I. I. Melamed, I. K. Sigal, and N. Y. Vladimirova, “Study of the linear parametrization of criteria in the bicriteria knapsack problem,” Computational Mathematics and Mathematical Physics, vol. 39, no. 5, pp. 711–714, 1999.
  9. C. Bazgan, H. Hugot, and D. Vanderpooten, “Solving efficiently the 0–1 multi-objective knapsack problem,” Computers & Operations Research, vol. 36, no. 1, pp. 260–279, 2009. https://dx.doi.org/10.1016/j.cor.2007.09.009
  10. J. R. Figueira, L. Paquete, M. Simões, and D. Vanderpooten, “Algorithmic improvements on dynamic programming for the bi-objective 0,1 knapsack problem,” Computational Optimization and Applications, vol. 56, pp. 97–111, 03 2013. https://dx.doi.org/10.1007/s10589-013-9551-x
  11. R. Kumar and P. Singh, “Assessing solution quality of biobjective 0-1 knapsack problem using evolutionary and heuristic algorithms,” Applied Soft Computing, vol. 10, no. 3, pp. 711–718, 2010. https://dx.doi.org/10.1016/j.asoc.2009.08.037
  12. A. Liefooghe, L. Paquete, and J. R. Figueira, “On local search for biobjective knapsack problems,” Evolutionary Computation, vol. 21, no. 1, pp. 179–196, 03 2013. https://dx.doi.org/10.1162/EVCO_a_00074
  13. L. Paquete, T. Schiavinotto, and T. Stützle, “On local optima in multiobjective combinatorial optimization problems,” Annals of Operations Research, vol. 156, pp. 83–97, 03 2007. https://dx.doi.org/10.1007/s10479-007-02300
  14. S. Fidanova, Ant colony optimization and applications, 1st ed., ser. Studies in Computational Intelligence. Cham, Switzerland: Springer, 2021, ch. 3, pp. 9–19. ISBN 978-3-030-67380-2
  15. S. Fidanova and K. Atanassov, “Ant algorithm with local search procedure for multiple knapsack problem,” in Large-Scale Scientific Computations. LSSC 2023, ser. Lecture Notes in Computer Science, I. Lirkov and S. Margenov, Eds., vol. 13952. Cham: Springer Nature Switzerland, 2024. https://dx.doi.org/10.1007/978-3-031-56208-2_24. ISBN 978-3031-56208-2 pp. 246–252.
  16. D. Granata and A. Raiconi, “Bi-objective knapsack problem with conflicts,” Annals of Operations Research, vol. 357, pp. 979–1001, 2026. https://dx.doi.org/10.1007/s10479-025-06792-5
  17. C. F. Bernardes, P. Castellucci, D. Gonçalves, E. Duzzioni, and A. Mucherino, “Adiabatic quantum computing for the subset sum problem: Preliminary studies,” in Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), ser. Annals of Computer Science and Information Systems, M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, and D. Śl˛ezak, Eds., vol. 43. IEEE, 2025. https://dx.doi.org/10.15439/2025F5496 pp. 635–639.
  18. R. Bellman, Dynamic programming, ser. Rand Corporation research study. New Jersey: Princeton University Press, 1957. ISBN 0-69107591-X
  19. W. R. Inc., “Mathematica, Version 14.3,” champaign, IL, 2025. [Online]. Available: https://www.wolfram.com/mathematica
  20. J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” SIAM review, vol. 59, no. 1, pp. 65–98, 2017. https://dx.doi.org/10.1137/141000671