Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem

  • Sergey V. Chebakov United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus
  • Liya V. Serebryanaya Belarusian State University of Informatics and Radioelectronics, 6 P. Broŭka Street, Minsk 220013, Belarus https://orcid.org/0000-0001-7189-7378
DOI: https://doi.org/10.33581/2520-6508-2020-2-97-104

Abstract

An algorithm is developed for finding the structure of the optimal subset in the knapsack problem based on the proposed multicriteria optimization model. A two-criteria relation of preference between elements of the set of initial data is introduced. This set has been split into separate Pareto layers. The depth concept of the elements dominance of an individual Pareto layer is formulated. Based on it, conditions are determined under which the solution to the knapsack problem includes the first Pareto layers. They are defined on a given set of initial data. The structure of the optimal subset is presented, which includes individual Pareto layers. Pareto layers are built in the introduced preference space. This does not require algorithms for enumerating the elements of the initial set. Such algorithms are used when finding only some part of the optimal subset. This reduces the number of operations required to solve the considered combinatorial problem.  The method for determining the found Pareto layers shows that the number of operations depends on the volume of the knapsack and the structure of the Pareto layers, into which the set of initial data in the entered two-criteria space is divided.

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 laboratory of computing networks

Liya V. Serebryanaya, Belarusian State University of Informatics and Radioelectronics, 6 P. Broŭka Street, Minsk 220013, Belarus

PhD (engineering), docent; associate professor at the department of software for information technologies, faculty of computer systems and networks

References

  1. Мartello S, Toth P. Knapsack problems: algorithms and computer implementations. Chichester: John Wiley & Sons; 1990. 308 p.
  2. Posypkin MA, Sigal IKh. Parallel combined algorithm for solving knapsack problems. In: Proceedings of the 4th International conference «Parallel computations and control problems»; 2008 October 27–29; Moscow, Russia. Moscow: Institute of Control Sciences; 2008. p. 177–189. Russian.
  3. Chebakov SV. [Two-criteria model for constructing an optimal subset of alternatives with a maximum total probability of achieving a goal]. Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 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. Kung HT, Luccio F, Preparata FP. On finding the maxima of a set of vectors. Journal of the Association for Computing Machinery. 1975;22(4):469–476.
Published
2020-07-30
Keywords: knapsack problem, multicriteria optimization, Pareto set, Pareto layer
How to Cite
Chebakov, S. V., & Serebryanaya, L. V. (2020). Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem. Journal of the Belarusian State University. Mathematics and Informatics, 2, 97-104. https://doi.org/10.33581/2520-6508-2020-2-97-104
Issue
No 2 (2020): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

Copyright (c) 2020 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International 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.)