ГлавнаяАрхивКомбинаторные свойства задачи об ограниченном рюкзаке

Комбинаторные свойства задачи об ограниченном рюкзаке | Прикладная дискретная математика. 2024. № 63. DOI: 10.17223/20710410/63/8

Рассматриваются комбинаторные свойства множества решений в задаче об ограниченном рюкзаке. Как и в общем случае, эта задача является NP-полной задачей комбинаторной оптимизации и её точное решение требует применения алгоритмов перебора с декомпозицией множества допустимых решений. В связи с этим актуален вопрос определения и оценки свойств множества допустимых решений. Получены формулы, позволяющие вычислять среднее значение функционала задачи на множестве её допустимых решений и мощность этого множества через число решений подзадач меньшей размерности. Базовой техникой получения результатов служит метод производящих функций. Рассмотрена задача о рюкзаке с произвольными значениями переменных, в которой совпадают коэффициенты вектора ограничений и целевой функции. Для неё предполагается «сюръективность» множества решений. Найдены оценки значений функционала в этой задаче. Результаты могут представлять интерес для конструирования вычислительных алгоритмов нахождения и оценки числа решений и значения функционала на оптимальных решениях. Найденные выражения также могут быть использованы во вспомогательных процедурах для оценки оптимальности решения в декомпозиционных или эвристических алгоритмах решения задачи о рюкзаке.
  • Title Комбинаторные свойства задачи об ограниченном рюкзаке
  • Headline Комбинаторные свойства задачи об ограниченном рюкзаке
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 63
  • Date:
  • DOI 10.17223/20710410/63/8
Ключевые слова
задача о рюкзаке, производящие функции, NP-полные задачи, метод коэффициентов, вычет, методы декомпозиции
Авторы
Ссылки
Kellerer Н., Pferschy U., and Pisinger D. Knapsack Problems. Berlin: Springer, 2004. 548 p.
Егорычев Г. П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977. 285 с.
Zhang Н., Plan W., Lai X., et al. Survey on cyberspace security // Sci. China Inform. Sci. 2015. V. 58. No. 11. P.1-43.
Lyubashevsky V., Palacio A., and Segev G. Public-key cryptographic primitives provablv as secure as subset sum // LNCS. 2010. V. 5978. P. 382-400'.
Ranjith J. and Mahantesh K. Blockchain-based knapsack system for security and privacy preserving to medical data // SN Comput. Sci. 2021. V. 2. https://www.researcher-app.com/paper/7553542.
Martello S. and Toth P. Knapsack Problems: Algorithms and Computer Implementations. N.Y.: John Wiley & Sons, 1990. 308 p.
Zhang X., Huang S., Hu Y., et al. Solving 0-1 knapsack problems based on amoeboid organism algorithm // Appl. Math.Comput. 2013. V.219. No. 19. P.9959-9970.
Kulkarni A.J. and Shabir H. Solving 0-1 knapsack problem using Cohort Intelligence Algorithm // Int. J. Mach. Learn. & Cyber. 2014. V. 7. P.427-441.
Rezoug A., Bader-El-Den M., and Boughaci D. Guided genetic algorithm for the multidimensional knapsack problem // Memetic Computing. 2018. V. 10. P.29-42.
Kong X., Gao L., Ouyang H., and Li S. Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm // Computers k, Operations Res. 2015. V.63. P.7-22.
Lv J., Wang X., Huang M., et al. Solving 0-1 knapsack problem by greedy degree and expectation efficiency // Appl. Soft Comput. 2016. V.41. P.94-103.
Chen Y. and Hao J.-K. A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem // Europ. J. Operational Res. 2014. V. 239. No. 2. P. 312- 322.
Voβ S. and Lalla-Ruiz E. A set partitioning reformulation for the multiple-choice multidimensional knapsack problem // Engin. Optimization. 2016. V. 48. No. 5. P. 831 850.
Dang C. and Ye Y. A fixed point iterative approach to integer programming and its distributed computation // Fixed Point Theory Appl. 2015. https://fixedpointtheoryand_algorithms.springeropen.com/articles/10.1186/sl3663-015-0429-8.
Pesant G. Counting solutions of CSPs: A structural spproach // Proc. IJCAF05. Edinburgh, Scotland, 2005. P.260-265.
Louveaux Q. and Weismantel R. Polyhedral properties for the intersection of two knapsacks // Math. Program. 2008. V. 113. P. 15-37.
Hojny C., Gaily T., Habeck O., et al. Knapsack polvtopes: a survey // Ann. Oper. Res. 2020. V.292. P.469-517.
Леонтьев В. К., Гордеев Э. Н. Производящие функции в задаче о ранце // Доклады Академии наук. 2018. Т. 481. №5. С. 478-480.
Гордеев Э.Н., Леонтьев В. К. О некоторых комбинаторных свойствах задачи о рюкзаке // Ж. вычисл. матем. и матем. физ. 2019. Т. 59. №8. С. 1439-1447.
Леонтьев В. К., Гордеев Э. Н. О числе решений системы булевых уравнений // Автоматика и телемеханика. 2021. №9. С. 150-168.
Леонтьев В. К., Гордеев Э.Н. О некоторых особенностях задачи разрешимости систем булевых уравнений j j Вопросы кибербезопасности. 2021. №1(41). С. 18-28.
Леонтьев В. К. О псевдобулевых полиномах // Ж. вычисл. матем. и матем. физ. 2015. Т. 55. №11. С. 1952-1958.
Леонтьев В. К., Гордеев Э. Н., Волков М. С. А. Классическая непрерывности и ее дискретный вариант // Прикладная физика и математика. 2022. №1. С. 31-37.
Комбинаторные свойства задачи об ограниченном рюкзаке | Прикладная дискретная математика. 2024. № 63. DOI: 10.17223/20710410/63/8
Комбинаторные свойства задачи об ограниченном рюкзаке | Прикладная дискретная математика. 2024. № 63. DOI: 10.17223/20710410/63/8