Складність аналізу стійкості задач дискретного програмування з булевими змінними

Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів уз...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автор:	Ліщук, Н.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Назва видання:	Компьютерная математика
Теми:	Теория и методы оптимизации
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/168369
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-168369
record_format	dspace
spelling	irk-123456789-1683692020-05-01T01:28:58Z Складність аналізу стійкості задач дискретного програмування з булевими змінними Ліщук, Н.В. Теория и методы оптимизации Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів узагальнено близьких задач (відрізняються одним елементом в матрицях обмежень або правих частинах). Показано, что проблемы анализа устойчивости обобщенно близких задач о покрытии множествами и задач о многомерном булевом ранце являются NP-трудными. Это означает, что при несовпадении классов P и NP в наихудшем случае не существует соответствующих полиномиальных алгоритмов анализа сложности устойчивости рассмотренных классов обобщенно близких задач (отличаются одним элементом в матрицах ограничений либо в правых частях). It is shown that the problems of sensitivity analysis for the generalized adjacent set covering problems and multivariate boolean knapsack problems are NP-hard. This implies that when the classes P and NP are mismatched, in worst case, the corresponding polynomial algorithms of sensitivity analysis for the classes of generally similar problems (differing in one element of matrices of constraints or in right hand sides) do not exist. 2015 Article Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/168369 519.854.33 uk Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Теория и методы оптимизации Теория и методы оптимизации
spellingShingle	Теория и методы оптимизации Теория и методы оптимизации Ліщук, Н.В. Складність аналізу стійкості задач дискретного програмування з булевими змінними Компьютерная математика
description	Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний булевий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості розглянутих класів узагальнено близьких задач (відрізняються одним елементом в матрицях обмежень або правих частинах).
format	Article
author	Ліщук, Н.В.
author_facet	Ліщук, Н.В.
author_sort	Ліщук, Н.В.
title	Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_short	Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_full	Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_fullStr	Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_full_unstemmed	Складність аналізу стійкості задач дискретного програмування з булевими змінними
title_sort	складність аналізу стійкості задач дискретного програмування з булевими змінними
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
topic_facet	Теория и методы оптимизации
url	http://dspace.nbuv.gov.ua/handle/123456789/168369
citation_txt	Складність аналізу стійкості задач дискретного програмування з булевими змінними / Н.В. Ліщук // Компьютерная математика. — 2015. — № 1. — С. 118-124. — Бібліогр.: 5 назв. — укр.
series	Компьютерная математика
work_keys_str_mv	AT líŝuknv skladnístʹanalízustíjkostízadačdiskretnogoprogramuvannâzbulevimizmínnimi
first_indexed	2025-07-15T03:09:48Z
last_indexed	2025-07-15T03:09:48Z
_version_	1837680808746287104
fulltext	118 Компьютерная математика. 2015, № 1 Показано, що проблеми аналізу стійкості узагальнено близьких задач про покриття множинами та задач про багатовимірний бу- левий рюкзак є NP-складними. Це означає, що при незбіганні класів P і NP у найгіршому випадку не існує відповідних поліноміальних алгоритмів аналізу стійкості роз- глянутих класів узагальнено бли- зьких задач (відрізняються одним елементом в матрицях обмежень або правих частинах).  Н.В. Ліщук, 2015 УДК 519.854.33 Н.В. ЛІЩУК СКЛАДНІСТЬ АНАЛІЗУ СТІЙКОСТІ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАМУВАННЯ З БУЛЕВИМИ ЗМІННИМИ Вступ. Предметом розгляду розділу, який на- зивається аналізом стійкості (sensitivity analysis) [1], є дослідження впливу змін па- раметрів вихідної задачі на оптимальний розв’язок цієї задачі. Зокрема, як знаючи оп- тимальний розв’язок деякої задачі, знайти оптимальний розв’язок (або визначити, що він залишився без змін) «близьких» у тому чи іншому сенсі задач. Важливе значення приділяється оцінками складності аналізу стійкості дискретних задач оптимізації. Для NP -складних задач це зводиться до аналізу існування поліноміальних алгоритмів знахо- дження оптимальних розв’язків змінених за- дач, виходячи з оптимальних розв’язків по- чаткової задачі. В роботі [2] наводяться ре- зультати по складності аналізу стійкості 0/1 задач з лінійної цільової функції при зміні значень цільового вектора. Показано, що є NP -складним (не існує поліноміального ал- горитму при P NP ) визначити чи залиша- ється оптимальний розв’язок незмінним для NP -складних задач при довільній зміні век- тора значень цільової функції. Подібних ре- зультатів по зміні матриці обмежень або ко- ефіцієнтів вектора обмежень, або взагалі не- має, або вони нечисленні. Розглядаються: узагальнена задача про покриття множинами, а також багатовимірна задача про рюкзак. Постановка задач. Узагальнену задачу про покриття множинами розглянемо у такій постановці: в комбінаторному варіанті дано множину {1,..., }M m і набір її під- множин 1,..., nM M , таких, що 1 . n j j M M   Сукупність підмножин jM ,  1,...j J n  , СКЛАДНІСТЬ АНАЛІЗУ СТІЙКОСТІ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАМУВАННЯ ... Компьютерная математика. 2015, № 1 119 називається покриттям множини ,M якщо .j j J M M   Кожному jM відпові- дає вага 0;jc  потрібно знайти покриття мінімальної сумарної ваги; у варіанті цілочислового лінійного програмування     , , min , 0,1f c A b cx Ax b x   . (1) { }ijA a – матриця розмірності m n з елементами 1,ija  якщо ,ji M і 0ija  у протилежному випадку; 1( ,..., )mb b b ib – натуральні числа, 1, ..., ;i m  1,..., nc c c − вектор ваги;  1,..., nx x x − вектор змінних з ком- понентами 1,jx  якщо jM входить у покриття, і 0jx  у протилежному випадку. Отже, розглянемо узагальнену задачу про покриття множинами ( GenSet ): 1 min , n i i i c x         1 , 1,..., , n ij j i j a x b i m    {0,1}, 1,..., .ix i n  (2) Аналіз стійкості для GenSet будемо проводити таким чином: у розглядува- ній задачі змінюються лише елементи ( , )m n -матриці  ijA a  1,..., ; 1,...,i m j n  і вектора  1,..., mb b b (елементи вектора  1,..., nc c c залишаються незмінними). Тому екземпляр задачі (2) будемо позначати ( , )GenSet A b або  GenSet A , де ( , )A A b − ( , 1)m n  -матриця або ( )GenSet І , де I A . Для довільних двох  , 1m n  -матриць  ijA a і  ,ijB b  1,..., ; 1,..., , 1i m j n n   введемо метрику   , , .ij ij i j A B a b   Багатовимірну булеву задачу про рюкзак розглянемо у постановці: 1 max , n i i i c x           1 , 1,..., , n ij j i j a x b i m    {0,1}, 1,..., .ix i n  (3) Н.В. ЛІЩУК 120 Компьютерная математика. 2015, № 1 Будемо вважати, що елементи матриці { },ijA a векторів 1( ,..., )nc c c і 1( ,..., )mb b b – невід’ємні цілі числа. Екземпляр задачі (3) будемо позначати ( , , )KP A b c або ( , ),KP A c де ( , ) ( , 1)A A b m n   – матриця. Аналіз стійкості для KP будемо проводити таким чином: у розглядуваній задачі змінюються лише елементи  ,m n -матриці  ijA a ( 1,..., ;i m 1,..., )j n і вектора  1,..., mb b b (елементи вектора 1( ,..., )nc c c залиша- ються незмінними). Тому екземпляр задачі (3) будемо позначати ( , )KP A b або   ,KP A де ( , )A A b − ( , 1)m n   матриця або ( ),KP I де .I A Будемо говорити, що функція ( )f n поліноміального росту  ( )f n  ( ) ,poly n якщо для деякої константи c (що не залежить від n ) при досить великих n виконується ( ) .cf n n Будемо вважати, що елементи матриці A з ( )KP A є ( )poly m n . Зміна параметрів задач. Для проведення аналізу стійкості будемо змінюва- ти на один елемент матриці ( , ).A A b У зв’язку з цим дамо означення. Означення 1. Задачу ( ')GenSet A ( ( ')KP A ) з 'A таку, що  ', 1A A  будемо називати узагальнено близькою до задачі ( )GenSet A ( ( )KP A ). При цьо- му узагальнено близькими будуть екземпляри I A та ' 'I A . Позначимо Re ( ( '))opt GenSet A ( Re ( ( '))opt KP A ) проблему знаходження оп- тимального розв’язку відповідно задачі ( ')GenSet A ( ( ')KP A ) узагальнено близь- кої до ( )GenSet A ( ( )KP A ), використовуючи оптимальний розв’язок x задачі ( )GenSet A ( ( )KP A ). Аналіз стійкості узагальнено близьких задач про покриття. Будемо користуватись такими результатами. Лема 1 [3]. Нехай П NP -складна проблема і mod -П – деяка локальна мо- дифікація для . Якщо існує поліноміальний алгоритм ,A який для довільного екземпляра I проблеми  обчислює: 1) екземпляр 'I для ; 2) оптимальний розв’язок 'x для ';I 3) послідовність локальних модифікацій типу mod -П (не більше, ніж поліноміальну), яка перетворює 'I в ,I то проблема mod -П є NP -складною. СКЛАДНІСТЬ АНАЛІЗУ СТІЙКОСТІ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАМУВАННЯ ... Компьютерная математика. 2015, № 1 121 Лема 2. Існує поліноміальний алгоритм, який містить не більше max min c n c  кроків, для визначення допустимого розв’язку задачі (2)  max max{ };ii c c min min{ } .ii c c Доведення повністю аналогічне доведенню леми 1 з [4]. Позначимо 1 1{1,..., }, {1,..., }, { ,..., }kM m N n K i i    деяка вибірка з N обсягом (1 ; ; ).k k n k m m n    Точка 1( ,..., ) {0,1} ,n n n B      така, що 1j  при 1j K , 0j  при 1\j N K . Нехай max{ }i i b b . Позначимо: 1) 11,K  рядок 1 матриці A , такий, що серед елементів 1 1 2,...,{ , }kK i i i (як стовпчиків) є рівно 1b одиниць (решта елементів рівні 0); 2) 12,K  рядок 2 матриці ,A такий, що серед елементів 1 1 2,...,{ , }kK i i i (як стовпчиків) є рівно 2b одиниць (решта елементів рівні 0) і т. д.; k) 1,k K  рядок k матриці ,A такий, що серед елементів 1 1 2,...,{ , }kK i i i (як стовпчиків) є рівно kb одиниць (решта елементів рівні 0). Опишемо клас { }A булевих m n -матриць { }.ijA a { }A A тоді і тільки тоді, коли матриця A не містить однакових і нульових рядків і, крім цьо- го, виконуються умови: 1) у матриці A є підматриця 1A  1 1 1, , ... ; K k K          2) у матриці A є підматриця 2 1{ }( \ , ),ijA a i M K j N   така, що для довільного 1 * 1\ ,ij j K i M K a b    інші елементи у 2A  довільні. Вектор ,b що відповідає { }A A позначимо .b Нехай * * * 1( ,..., ) ,n nx x x B  такий, що 1 * ... 1, ki ix x   решта координат вектора x дорівнює 0, * { }.A A Лема 3. x  оптимальний розв’язок екземпляра ( , )I A b задачі (1). Н.В. ЛІЩУК 122 Компьютерная математика. 2015, № 1 Доведення випливає з того факту, що x  єдиний допустимий розв’язок ек- земпляра I задачі, такий, що не існує допустимого розв’язку 'x задачі (1), та- кого, що * ' ( ' , 1,..., ), ' ,i ix x x x i n x x    а, отже, він і буде оптимальним. Теорема 1. Проблема Re ( ( '))opt GenSet A є NP -складною. Доведення. Скористаємось лемою 1. Як  візьмемо задачу (2) (тобто ( )GenSet І , де I A ). В силу побудови { },A A вектора ,x а також, засто- совуючи леми 2 і 3, отримаємо виконання пп. 1) і 2) леми 1. Покажемо виконан- ня п. 3) леми 1. Нехай для довільної ( 1)m n  – матриці A , ( )T A  перетво- рення матриці A з заміною довільного одного елемента A 0 на 1, або 1 на 0; збільшенням або зменшенням вектора b на 1 в одній позиції. Будемо писати, що ' ( )A T A , якщо після застосування до A перетворення T отрималася матриця 'A (ясно, що ( , ') 1A A  ). Довільну матрицю ( , )A A b можна отримати з матриці ( , )A A b , застосовуючи не більше, ніж ( 1)m n  пере- творень :T 1 2 ...T T T T kA A A A A     , * * 1 1( ), ( , ) 1,A T A A A   1 1( ), ( , ) 1, 1,..., 1;i i i iA T A A A i k      ( 1).k m n   Візьмемо як mod -П перетворення ,T отримаємо п. 3) леми 1 і доведення теореми 1. Аналіз стійкості узагальнено близьких задач про багатовимірний буле- вий рюкзак. Будемо користуватись такими результатами. Лема 4. Існує поліноміальний алгоритм, який містить не більше max min c n c  кроків, для визначення допустимого розв’язку задачі (3) ( max max{ };ii c c min min{ }ii c c ). Доведення повністю аналогічне доведенню леми 1' з [4]. Нехай 1 1{1,2,..., }, { ,..., }kN n K i i   деяка вибірка з N обсягом * * * 1(1 ), ( ,..., ) ,n nk k n x x x B    такий, що 1 * ... 1, ki ix x   решта координат вектора x дорівнюють 0. Розглянемо екземпляр задачі (3) ( ),KP A де * ( , ) ( 1)A A b m n    -матриця, * * { }, { }( 1,..., ; 1,..., ),ij iA a b b i m j n    причому 11( 1,..., ; )ija i m j K   * 11( 1,..., ; \ )ija k i m j N K    * ( 1,..., ).ib k i m  Лема 5. x  оптимальний розв’язок екземпляра ( , )I A b задачі (3). СКЛАДНІСТЬ АНАЛІЗУ СТІЙКОСТІ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАМУВАННЯ ... Компьютерная математика. 2015, № 1 123 Доведення випливає з того факту, що x  єдиний допустимий розв’язок ек- земпляра I задачі, такий, що не існує допустимого розв’язку 'x задачі (3), та- кого, що * * ' ( ' , 1,..., ), ' ,i ix x x x i n x x    а, отже, він і буде оптимальним. Теорема 2. Проблема Re ( ( '))opt KP A є NP -складною. Доведення. Скористаємось лемою 1. Як П візьмемо задачу (3) (тобто ( ),KP І де I A ). В силу побудови , ,A b вектора ,x а також, застосовуючи леми 4 і 5, отримаємо виконання пп. 1) і 2) леми 1. Покажемо виконання п. 3) леми 1. Нехай для довільної ( 1)m n  – матриці A , ( )T A  перетворення матриці A із збільшенням або зменшенням матриці ,A або вектора b на 1 в одній позиції. Будемо писати, що ' ( )A T A , якщо після застосування до A перетворення T вийшла матриця 'A (ясно, що ( , ') 1A A  ). Довільну матрицю ( , )A A b можна отримати з матриці * * ( , ),A A b застосовуючи не більше, ніж ( )poly m n перетворень T : 1 2 ...T T T T kA A A A A     , * * 1 1( ), ( , ) 1,A T A A A   1 1( ), ( , ) 1, 1,..., 1;i i i iA T A A A i k      ( ).k poly m n  Візьмемо як mod -П перетворення ,T отримаємо п. 3) леми 1 і доведення теореми 2. Теорема 2 – узагальнення результату з [5]. Заключення. В роботі отримано наступний результат. Показано, що про- блема знаходження оптимального розв’язку узагальнено близьких задач про по- криття множинами та про багатовимірний булевий рюкзак є NP -складними, якщо виходити з оптимального розв’язку вихідної задачі. Таким чином, перевір- ка (у найгіршому випадку), що оптимальний розв’язок розглянутих класів задач залишиться без змін є також NP -складною. Це означає, що при P NP для таких класів задач не існує поліноміальних алгоритмів аналізу стійкості. Н.В. Лищук СЛОЖНОСТЬ АНАЛИЗА УСТОЙЧИВОСТИ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ Показано, что проблемы анализа устойчивости обобщенно близких задач о покрытии множествами и задач о многомерном булевом ранце являются NP-трудными. Это означает, что при несовпадении классов P и NP в наихудшем случае не существует соответствующих полиномиальных алгоритмов анализа сложности устойчивости рассмотренных классов обобщенно близких задач (отличаются одним элементом в матрицах ограничений либо в правых частях). Н.В. ЛІЩУК 124 Компьютерная математика. 2015, № 1 N.V. Lishchuk COMPLEXITY OF SENSITIVITY ANALYSIS FOR DISCRETE PROGRAMMING PROBLEMS WITH BOOLEAN VARIABLES It is shown that the problems of sensitivity analysis for the generalized adjacent set covering problems and multivariate boolean knapsack problems are NP-hard. This implies that when the classes P and NP are mismatched, in worst case, the corresponding polynomial algorithms of sensitivity analysis for the classes of generally similar problems (differing in one element of matrices of constraints or in right hand sides) do not exist. 1. Fernandez-Baca D., Benkatachalam B. Sensitivity analysis in combinatorial optimization // Handbook of Approximation Algorithms and Metaheuristics (ed. T. Guzalez). – Chapman&Hall/CRC Computer and Information Science Series. – 2007. – P. 30-1 – 30-29. 2. Van Hoesel S., A. Wagelmans On the complexity of postoptimality analysis of 0/1 programs // Discrete Applied Mathematics. – 1999. – 91. – P. 251 – 263. 3. Михайлюк В.О., Ляшко В.І. Реоптимізація задачі про покриття множинами: асимптотич- ний поріг відношення апроксимації // Наукові записки НаУКМА. Комп’ютерні науки. – 2012. – Т. 138. – С. 95 – 99. 4. Михайлюк В.А. Общий подход к оценке сложности постоптимального анализа дискрет- ных задач оптимизации // Кибернетика и системный анализ. – 2010. – 46, № 2. – С. 134 – 141. 5. Михайлюк В.A., Лищук Н.В.Анализ устойчивости задачи о ранце: один отрицательный результат // Там же. – 2013. – 49, № 2. – С. 48 – 51. Одержано 05.11.2014 Про автора: Ліщук Наталія Вікторівна, аспірантка Східноєвропейського національного університету імені Лесі Українки. Е-mail: lnatalkav@mail.ru

Складність аналізу стійкості задач дискретного програмування з булевими змінними

Репозитарії

Схожі ресурси