Algorithm for solving the knapsack problem with certain properties of Pareto layers

Authors

  • Sergey V. Chebakov United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus
  • Liya V. Serebryanaya BIP – University of Law and Social-Information Technologies, 3 Karalia Street, Minsk 220004, Belarus; Belarusian State University of Informatics and Radioelectronics, 6 P. Broŭki Street, Minsk 220013, Belarus

Keywords:

knapsack problem, multicriteria optimisation, Pareto set, Pareto layer

Abstract

An algorithm for solving the knapsack problem based on the proposed multicriteria model has been developed. The structure of admissible subsets is presented for the value of the non-dominance depth of the Pareto layer equal to zero. The sum of the resource of the elements of this layer is greater than or equal to the value of the volume of the knapsack. Based on the structure, the form of the optimal admissible subset with the maximum total value of the weight of its elements is determined. It is shown that at a certain stage the developed algorithm includes the solution of a number of knapsack subtasks. Their knapsack volumes are smaller than in the original problem with input data sets. The definition of the redundancy of the set of initial data and the condition for the existence of redundancy for a given value of the depth of non-dominance of the Pareto layer are introduced.

Author Biographies

  • Sergey V. Chebakov, United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus

    PhD (physics and mathematics); senior researcher at the department of computing networks

  • Liya V. Serebryanaya, BIP – University of Law and Social-Information Technologies, 3 Karalia Street, Minsk 220004, Belarus; Belarusian State University of Informatics and Radioelectronics, 6 P. Broŭki Street, Minsk 220013, Belarus

    PhD (engineering), docent; head of the department of information technology and mathematics, faculty of economics and law, BIP – University of Law and Social-Information Technologies, and associate professor at the department of software for information technologies, faculty of computer systems and networks, Belarusian State University of Informatics and Radioelectronics

References

  1. Мartello S, Toth P. Knapsack problems: algorithms and computer implementations. New York: John Wiley & Sons; 1990. 308 p.
  2. Posypkin MA. [Combined parallel algorithm for solving the knapsack problem]. In: Trudy IV Mezhdunarodnoi konferentsii «Parallel’nye vychisleniya i zadachi upravleniya»; 27–29 oktyabrya 2008 g.; Moskva, Rossiya [Proceedings of the 4th International conference «Parallel Computing and Control Problems»; 2008 October 27–29; Moscow, Russia]. Moscow: Institute of Control Sciences of the Russian Academy of Sciences; 2008. p. 177–189. Russian.
  3. Chebakov SV. [A two-criterion model for constructing an optimal subset of alternatives with the maximum total probability of achieving the goal]. Vesci Nacyjanal’naj akadjemii navuk Belarusi. Seryja fizika-matjematychnyh navuk. 2005;2:112–118. Russian.
  4. Chebakov SV, Serebryanaya LV. Finding of optimal subset structure in the knapsack problem. Doklady BGUIR. 2019;6:72–79. Russian. DOI: 10.35596/1729-7648-2019-124-6-72-79.
  5. Chebakov SV, Serebryanaya LV. Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem. Journal of the Belarusian State University. Mathematics and Informatics. 2020;2:97–104. Russian. DOI: 10.33581/2520-6508-2020-2-97-104.
  6. Kung HF, Luccio F, Preparata FP. On finding the maxima of a set of vectors. Journal of the ACM. 1975;22(4):469–476. DOI: 10.1145/321906.321910.

Downloads

Published

2022-12-27

Issue

No. 3 (2022): Journal of the Belarusian State University. Mathematics and Informatics

Section

Discrete Mathematics and Mathematical Cybernetics

License

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Chebakov, S.V. and Serebryanaya, L.V. 2022. Algorithm for solving the knapsack problem with certain properties of Pareto layers. Journal of the Belarusian State University. Mathematics and Informatics. 3 (Dec. 2022), 54–66. DOI:https://doi.org/10.33581/2520-6508-2022-3-54-66.