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

К. Sh. Mamedov, N. N. Mamedov

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.

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.

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.


GOST Style Citations


1. Корбут А. А. Дискретное программирование / А. А. Корбут,
Ю. Ю. Финкельштейн. – М. : Наука, 1969. – 368 с.
2. Ковалев М. М. Дискретная оптимизация (целочисленное программирование) / М. М. Ковалев. – М. : УРСС, 2003. – 246 с.
3. Martello S. Knapsack problems, Algorithm and Computers
implementations. / S. Martello, P. Toth. – John Wiley & Sons,
Chichster, 1990. – 296 p.
4. Kellerer H. Knapsack problems. / H. Kellerer, U. Pferschy, D. Pisinger. – Berlin, Heidelberg, New-York : Springer Verlag, 2004. – 546 p.
5. Сигал И. Х. Введение в прикладное дискретное программирование: модели, вычислительные алгоритмы / И. Х. Сигал,
А. П. Иванова. – М. : Физмат лит., 2007. – 304 с.
6. Сергиенко И. В. Приближенные методы решения дискретных задач оптимизации / И. В.Сергиенко, Т. Т. Лебедева, В. А. Рошин. – Киев : Наукова думка, 1980. – 276 с.
7. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации / И. В. Сергиенко. – АН УССР, Институт Кибернетики : Наукова Думка, 1988. – 471 с.
8. Сергиенко И. В. Исcледование устойчивости и параметрический анализ дискретных оптимизационных задач / И. В. Сергиенко, Л. Н. Козерацкая, Т. Т. Лебедева. – Киев : Наук. думка, 1995. – 169 с.
9. Сергиенко И. В. Задачи дискретной оптимизации: проблемы, методы, решения, исследования / И. В. Сергиенко, В. П. Шило. – Киев : Нац. акад. наук Украины, Ин-т кибернетики им. В. М. Глушкова Наука. думка, 2003. – 261 с.
10. Мамедов К. Ш. Исследование по целочисленной оптимизации (методы, алгоритмы и вычислительные эксперименты) / К. Ш. Мамедов. – Германия : Lambert Academic Publishing, 2012. – 276 с.
11. Бабаев Дж.А. Методы построения субоптимальных решений многомерной задачи о ранце / Дж. А. Бабаев, К. Ш. Мамедов, М. Г. Мехтиев // ЖВМ и МФ. – 1978. – Т. 28, № 6. – С. 1443–1453.
12. Нуриев У. Г. Гибридный метод для решения многомерной задачи о ранце / У. Г. Нуриев. – Препринт ИК АН УССР, 1983. – 45 с.
13. Emelichev V. Quantitative stability analysis for vector problems of 0-1 programming / V. Emelichev, D. Podkopaev // Discrete Optimization. – 2010. – Vol. 7. – P. 48–63.
14. Мамедов К. Ш. Алгоритмы построения гарантированного
решения и гарантированного приближенного решения мно-
гомерной задачи о ранце / К. Ш. Мамедов, Н. Н. Мамедов //
Международный научно-технический журнал «Проблемы
Управления и Информатики». – 2014. – № 5. – C. 30–37.
15. Mamedov K. Sh. Guaranteed solution and its finding in the Integer Programming Problems. / K. Sh. Mamedov, N. N. Mamedov // International Journal of Applied Science and Tecnology. – August. – 2015. – Vol. 5, № 4. – P. 46–54.
16. Мамедов К. Ш. Понятие гарантированного решения и гарантированного субоптимального решения относительно целевой функии в задаче о ранце и его построение (на азерб. языке) / К. Ш. Мамедов, Н. Н. Мамедов // Изв. НАН Азерб. Баку. – 2016. – № 3. – C. 42–49.
17. Senjy S. An approach to linear programming with 0-1 variables. / S. Senjy, Y. Toyoda // J. Manag. Sci. – 1978. – V.15, № 4. – P. 196–207.




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



Copyright (c) 2018 К. Sh. Mamedov, N. N. Mamedov

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.