THE CONCEPT OF GUARANTEED SOLUTION THROUGH THE FUNCTIONAL FOR MUTIDIMENTIONAL KNAPSACK PROBLEM AND METHODS OF ITS CONSTRUCTION

Authors

  • К. Sh. Mamedov Institute of Control Systems of the National Academy of Sciences of Azerbaijan, Baku, Azerbaijan
  • N. N. Mamedov National Aviation Academy of Azerbaijan, Baku, Azerbaijan

DOI:

https://doi.org/10.15588/1607-3274-2018-1-19

Keywords:

one-dimensional and multidimensional knapsack problems, guaranteed solution and guaranteed suboptimal solution through the functional, non-linear multicriteria the problem of Boolean programming, dichotomy approach, computational experiment.

Abstract

Contex. The problem of constructing a guaranteed suboptimal (approximate) solution with respect to a functional in one-dimensional and multidimensional knapsack problems is considered. The object of the study was a model with an increment of the coefficients of the objective function.
Objective. The methods of constructing guaranteed suboptimal solution through the functional in one-dimensional and multidimensional
knapsack problem has been developed.
That is it is necessary to find such minimal changes coefficient of the objective function in the set of integer intervals so that the solution
found guarantees the value of the functional not less than the predetermined value.
Method. The concept of guaranteed solution and guaranteed suboptimal solution relative to the objective function in the satchel problem
is introduced. It is necessary to find such minimal changes coefficient of the objective function in the set of integer intervals so that the
solution found guarantees the value of the functional not less than the predetermined value. Such kind of solution we name as guaranteed
solution through the functional for one-dimensional and multidimensional knapsack problem. The methods of their construction has been developed. A software package was developed to find these solutions and numerous computational experiments were performed on random large-dimensional problems.
Results. The algorithm of constructing guaranteed suboptimal solution through the functional in one-dimensional and multidimensional
knapsack problem has been developed.
Conclusions. A software package was developed to find the concept of guaranteed solution and guaranteed suboptimal solutions and
numerous computational experiments were performed on random large-dimensional problems.

References

Korbut A. A., Finkel’shtejn Yu. Yu. Diskretnoe programmirovanie.

Moscow, Nauka, 1969. – 368 p.

Kovalev M. M. Diskretnaya optimizaciya (celochislennoe

programmirovanie). Moscow, URSS, 2003, 246 p.

Martello S., Toth P. Knapsack problems, Algorithm and Computers

implementations. John Wiley & Sons, Chichster, 1990, 296 p.

Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin,

Heidelberg, New-York, Springer Verlag, 2004, 546 p.

Sigal I. X., Ivanova A. P. Vvedenie v prikladnoe diskretnoe

programmirovanie: modeli, vychislitel’nye algoritmy. Moscow,

Fizmat lit., 2007, 304 p.

Sergienko I. V., Lebedeva T. T., Roshin V. A. Priblizhennye metody

resheniya diskretnyx zadach optimizacii. Kiev, Naukova dumka,

, 276 p.

Sergienko I. V. Matematicheskie modeli i metody resheniya zadach

diskretnoj optimizacii. AN USSR, Institut Kibernetiki, Naukova

Dumka, 1988, 471 p.

Sergienko I. V., Kozerackaya L. N., Lebedeva T. T. Iscledovanie

ustojchivosti i parametricheskij analiz diskretnyx

optimizacionnyx zadach. Kiev, Nauk. dumka, 1995, 169 p.

Sergienko I. V., Shilo V. P. Zadachi diskretnoj optimizacii:

problemy, metody, resheniya, issledovaniya. Kiev, Nac. akad.

nauk Ukrainy, In-t kibernetiki im. V. M. Glushkova Nauka. dumka,

, 261 p.

Mamedov K. Sh. Issledovanie po celochislennoj optimizacii

(metody, algoritmy i vychislitel’nye e’ksperimenty). Germaniya,

Lambert Academic Publishing, 2012, 276 p.

Babaev Dzh. A., Mamedov K. Sh., Mextiev M. G. Metody

postroeniya suboptimal’nyx reshenij mnogomernoj zadachi o

rance, ZhVM i MF, 1978, Vol. 28, No. 6, pp. 1443–1453.

Nuriev U. G. Gibridnyj metod dlya resheniya mnogomernoj zadachi

o rance. Preprint IK AN USSR, 1983, 45 p.

Vladimir Emelichev, Podkopaev Dmitry Quantitative stability

analysis for vector problems of 0-1 programming, Discrete

Optimization, 2010, Vol. 7, pp. 48–63.

Mamedov N. N., Mamedov K. Sh., Algoritmy postroeniya

garantirovannogo resheniya i garantirovannogo priblizhennogo

resheniya mnogomernoj zadachi o rance, Mezhdunarodnyj

nauchno-texnicheskij zhurnal «Problemy Upravleniya i

Informatiki», 2014, No. 5, pp. 30–37.

Mamedov N. N., Mamedov K. Sh. Guaranteed solution and its

finding in the Integer Programming Problems, International

Journal of Applied Science and Tecnology, 2015, August, Vol. 5,

No. 4, pp. 46–54.

Mamedov N. N., Mamedov K. Sh. Ponyatie garantirovannogo

resheniya i garantirovannogo suboptimalnogo resheniya

otnositelno celevoj funkii v zadache o rance i ego postroenie (na

azerb. yazyke), Izv. NAN Azerb. Baku, 2016, No. 3, pp. 42–49.

Senjy S., Toyoda Y. An approach to linear programming with 0–

variables, J. Manag. Sci, 1978, Vol.15, No. 4, pp. 196–207.

How to Cite

Mamedov К. S., & Mamedov, N. N. (2018). THE CONCEPT OF GUARANTEED SOLUTION THROUGH THE FUNCTIONAL FOR MUTIDIMENTIONAL KNAPSACK PROBLEM AND METHODS OF ITS CONSTRUCTION. Radio Electronics, Computer Science, Control, (1), 166–173. https://doi.org/10.15588/1607-3274-2018-1-19

Issue

Section

Control in technical systems