Geodesic
Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem
Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2020), pp. 97-104.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: knapsack problem; multicriteria optimization; Pareto set; Pareto layer. 
@article{BGUMI_2020_2_a9,
     author = {S. V. Chebakov and L. V. Serebryanaya},
     title = {Finding algorithm of optimal subset structure based on the {Pareto} layers in the knapsack problem},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {97--104},
     publisher = {mathdoc},
     volume = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2020_2_a9/}
}
TY  - JOUR
AU  - S. V. Chebakov
AU  - L. V. Serebryanaya
TI  - Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2020
SP  - 97
EP  - 104
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2020_2_a9/
LA  - ru
ID  - BGUMI_2020_2_a9
ER  - 
%0 Journal Article
%A S. V. Chebakov
%A L. V. Serebryanaya
%T Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2020
%P 97-104
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2020_2_a9/
%G ru
%F BGUMI_2020_2_a9
S. V. Chebakov; L. V. Serebryanaya. Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem. Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2020), pp. 97-104. http://geodesic.mathdoc.fr/item/BGUMI_2020_2_a9/

[1] S. Martello, P. Toth, “Knapsack problems: algorithms and computer implementations”, Chichester: John Wiley and Sons, 1990, 308 | MR

[2] M. A. Posypkin, I. Kh. Sigal, “Kombinirovannyi parallelnyi algoritm resheniya zadachi o rantse”, Trudy IV Mezhdunarodnoi konferentsii «Parallelnye vychisleniya i zadachi upravleniya» (Rossiya), 2008, 177–189, Moskva: Institut problem upravleniya

[3] S. V. Chebakov, “Dvukhkriterialnaya model postroeniya optimalnogo podmnozhestva alternativ s maksimalnoi summarnoi veroyatnostyu dostizheniya tseli”, Izvestiya Natsionalnoi akademii nauk Belarusi. Seriya fiziko-matematicheskikh nauk, 2 (2005), 112–118 | MR

[4] S. V. Chebakov, L. V. Serebryanaya, “Opredelenie struktury optimalnogo podmnozhestva v zadache o rantse”, Doklady BGUIR, 6 (2019), 72–79 | DOI

[5] H. T. Kung, F. Luccio, F. P. Preparata, “On finding the maxima of a set of vectors”, Journal of the Association for Computing Machinery, 22(4) (1975), 469–476 | DOI | MR | Zbl