Реоптимізація 2-критеріальної задачі про узагальнену виконуваність
Показано, що є виграш як наближення для реоптимізації 2-критеріальної задачі про узагальнену виконуваність. При додаванні деякого зваженого обмеження, відповідне відношення апроксимації є 1/(2- d(P)) > d(P) , де для відповідної однокритеріальної задачі існує d(P) – наближений поліномі- альний ал...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2018 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/161895 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Реоптимізація 2-критеріальної задачі про узагальнену виконуваність / В.О. Михайлюк, Т.І. Чепрасова, Н.А. Дрейчан // Компьютерная математика. — 2018. — № 2. — С. 145-153. — Бібліогр.: 13 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161895 |
|---|---|
| record_format |
dspace |
| spelling |
Михайлюк, В.О. Чепрасова, Т.І. Дрейчан, Н.А. 2019-12-25T19:42:11Z 2019-12-25T19:42:11Z 2018 Реоптимізація 2-критеріальної задачі про узагальнену виконуваність / В.О. Михайлюк, Т.І. Чепрасова, Н.А. Дрейчан // Компьютерная математика. — 2018. — № 2. — С. 145-153. — Бібліогр.: 13 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/161895 519.854 Показано, що є виграш як наближення для реоптимізації 2-критеріальної задачі про узагальнену виконуваність. При додаванні деякого зваженого обмеження, відповідне відношення апроксимації є 1/(2- d(P)) > d(P) , де для відповідної однокритеріальної задачі існує d(P) – наближений поліномі- альний алгоритм, (d(P) – це ймовірність виконання довільного обмеження предиката P при рівноймовірному виборі. Показано, что есть выигрыш в качестве приближения для реоптимизации 2-критериальной задачи об обобщенной выполнимости. При добавлении некоторого взвешенного ограничения, соответствующее отношение аппроксимации есть 1/(2- d(P)) > d(P) , где для соответствующей однокритериальной задачи существует d(P) – приближенный полиномиальный алгоритм, (d(P) – это вероятность выполнения произвольного ограничения предиката P при равновероятном выборе. It is shown that there is a gain in the quality of the approximation for the reoptimization of the 2-criteria problem of generalized satisfiability. When adding some weighted constraint, the corresponding approximation ratio is 1/(2- d(P)) > d(P), where there is a d(P)-approximated polynomial algorithm for the corresponding one-objective problem (d(P) is the probability that an arbitrary restriction of the predicate is satisfied with an equal choice). uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Реоптимізація 2-критеріальної задачі про узагальнену виконуваність Реоптимизация 2-критериальной задачи об обобщенной выполнимости Reoptimization of 2-criteria satisfiability problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність |
| spellingShingle |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність Михайлюк, В.О. Чепрасова, Т.І. Дрейчан, Н.А. Теория и методы оптимизации |
| title_short |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність |
| title_full |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність |
| title_fullStr |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність |
| title_full_unstemmed |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність |
| title_sort |
реоптимізація 2-критеріальної задачі про узагальнену виконуваність |
| author |
Михайлюк, В.О. Чепрасова, Т.І. Дрейчан, Н.А. |
| author_facet |
Михайлюк, В.О. Чепрасова, Т.І. Дрейчан, Н.А. |
| topic |
Теория и методы оптимизации |
| topic_facet |
Теория и методы оптимизации |
| publishDate |
2018 |
| language |
Ukrainian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Реоптимизация 2-критериальной задачи об обобщенной выполнимости Reoptimization of 2-criteria satisfiability problem |
| description |
Показано, що є виграш як наближення для реоптимізації 2-критеріальної задачі про узагальнену виконуваність. При додаванні деякого зваженого обмеження, відповідне відношення апроксимації є 1/(2- d(P)) > d(P) , де для відповідної однокритеріальної задачі існує d(P) – наближений поліномі- альний алгоритм, (d(P) – це ймовірність виконання довільного обмеження предиката P при рівноймовірному виборі.
Показано, что есть выигрыш в качестве приближения для реоптимизации 2-критериальной задачи об обобщенной выполнимости. При добавлении некоторого взвешенного ограничения, соответствующее отношение аппроксимации есть 1/(2- d(P)) > d(P) , где для соответствующей однокритериальной задачи существует d(P) – приближенный полиномиальный алгоритм, (d(P) – это вероятность выполнения произвольного ограничения предиката P при равновероятном выборе.
It is shown that there is a gain in the quality of the approximation for the reoptimization of the 2-criteria problem of generalized satisfiability. When adding some weighted constraint, the corresponding approximation ratio is 1/(2- d(P)) > d(P), where there is a d(P)-approximated polynomial algorithm for the corresponding one-objective problem (d(P) is the probability that an arbitrary restriction of the predicate is satisfied with an equal choice).
|
| issn |
2616-938Х |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161895 |
| citation_txt |
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність / В.О. Михайлюк, Т.І. Чепрасова, Н.А. Дрейчан // Компьютерная математика. — 2018. — № 2. — С. 145-153. — Бібліогр.: 13 назв. — укр. |
| work_keys_str_mv |
AT mihailûkvo reoptimízacíâ2kriteríalʹnoízadačíprouzagalʹnenuvikonuvanístʹ AT čeprasovatí reoptimízacíâ2kriteríalʹnoízadačíprouzagalʹnenuvikonuvanístʹ AT dreičanna reoptimízacíâ2kriteríalʹnoízadačíprouzagalʹnenuvikonuvanístʹ AT mihailûkvo reoptimizaciâ2kriterialʹnoizadačiobobobŝennoivypolnimosti AT čeprasovatí reoptimizaciâ2kriterialʹnoizadačiobobobŝennoivypolnimosti AT dreičanna reoptimizaciâ2kriterialʹnoizadačiobobobŝennoivypolnimosti AT mihailûkvo reoptimizationof2criteriasatisfiabilityproblem AT čeprasovatí reoptimizationof2criteriasatisfiabilityproblem AT dreičanna reoptimizationof2criteriasatisfiabilityproblem |
| first_indexed |
2025-11-27T05:58:24Z |
| last_indexed |
2025-11-27T05:58:24Z |
| _version_ |
1850803650700509184 |
| fulltext |
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 145
Показано, що є виграш як набли-
ження для реоптимізації 2-крите-
ріальної задачі про узагальнену
виконуваність. При додаванні де-
якого зваженого обмеження, від-
повідне відношення апроксимації є
1 ( )(2 ( )) d Pd P , де для відпо-
відної однокритеріальної задачі
існує d(P) – наближений поліномі-
альний алгоритм, (d(P) – це ймо-
вірність виконання довільного об-
меження предиката P при рівно-
ймовірному виборі.
В.О. Михайлюк, Т.І. Чепрасова,
Н.А. Дрейчан, 2018
УДК 519.854
В.О. МИХАЙЛЮК, Т.І. ЧЕПРАСОВА, Н.А. ДРЕЙЧАН
РЕОПТИМІЗАЦІЯ
2-КРИТЕРІАЛЬНОЇ ЗАДАЧІ
ПРО УЗАГАЛЬНЕНУ ВИКОНУВАНІСТЬ
Вступ. Елементи багатокритеріальної опти-
мізації виникають при дослідженні багатьох
технічних, економічних, природних і соці-
ально-наукових процесів. Наприклад, в логі-
стиці зацікавлені в маршрутах з одночасною
мінімізацією транспортних витрат і часу
транспортування. Не існує єдиного розв’яз-
ку, який є оптимальним для обох цілей, так
як вони є суперечливими. Треба враховувати
компроміси між обома завданнями, тобто
деякі маршрути будуть дешевими, інші
швидкими. Множина Парето описує поняття
оптимальності в цьому випадку. Вона скла-
дається з усіх розв’язків, які оптимальні
в тому сенсі, що не існує розв’язку, який
строго кращий. Для осіб, що приймають рі-
шення множина Парето дуже корисна, оскі-
льки враховує компроміси між оптимальни-
ми розв’язками для поточного екземпляра.
Багатокритеріальні задачі про узагальнену
виконуваність (Multicriteria Constraint Satis-
faction problems, Multicriteria CSPs) – частин-
ний випадок багатокритеріальної оптимізації,
коли при задаванні критеріїв використову-
ють предикати, а не функції. Ми матимемо
справу з комбінаторною багатокритеріаль-
ною оптимізацією та багатокритеріальними
задачами про узагальнену виконуваність
[1, 2].
Концепція реоптимізаціі [2 – 8] полягає
в наступному. Нехай Q деяка NP-складна
(можливо NP-повна) задача, I початковий
екземпляр задачі ,Q оптимальний розв’язок
якого відомий.
Пропонуємо новий екземпляр 'I задачі ,Q
отриманий деякими «незначними» змінами .I
Виникає питання: як ми можемо ефективно
В.О. МИХАЙЛЮК, Т.І. ЧЕПРАСОВА, Н.А. ДРЕЙЧАН
ISSN 2616-938Х. Компьютерная математика. 2018, № 2146
використовувати знання про оптимальний розв’язок I для знаходження точного
або наближеного розв’язку екземпляра 'I ? Мета реоптимізації при використанні
наближених методів – застосування знань про розв’язок початкового екземпляра
I для досягнення кращої якості наближення (відношення апроксимації),
або більш ефективного (за часом) алгоритму для визначення оптимальних або
близьких до них розв’язків, або виконання першого і другого пунктів.
Є дуже мало результатів з реоптимізаціі комбінаторних багатокритеріальних
задач взагалі й узагальнених задач про виконуваність, зокрема. Один з підходів є
так звана бюджетна реоптимізація [9, 10], коли бюджетні обмеження додаються
до основної задачі, а потім досліджуються впливи на оптимальний розв’язок.
У цій роботі вивчається ефект додавання довільного зваженого обмеження
до довільного екземпляра 2-критеріальної задачі про узагальнену виконуваність.
Будемо використовувати поняття роботи [1, 11].
Поняття багатокритеріального розв’язку і багатокритеріальної
NP-складності. Нехай 1k . Комбінаторна k -критеріальна оптимізаційна зада-
ча ( k -критеріальна задача, коротко) є кортежем ( , , )S f , де
1. : 2NS N відображає екземпляр x N на множину допустимих
розв’язків екземпляра, позначених як xS N . Має існувати деякий поліном ,p
такий, що для довільного x N і кожного xs S випливає ( )s p x
і множина {( , ) : , }xx s x N s S має бути поліноміально розв’язною.
2. :{( , ) : , }x kf x s x N s S N відображає екземпляр x N і розв’язок
xs S до його значення ( ) .x kf s N f має бути поліноміально обчислювальною.
3. k kN N – відношення часткового порядку, що визначає напрямок
оптимізації. Має виконуватись
1 1 1 1 1( ,..., ) ( ,..., )k k k k ka a b b a b a b ,
де i є , якщо ціль i -го критерію полягає в мінімізації і i є , якщо ціль
i -го критерію полягає у максимізації (для задач про узагальнену виконуваність
це буде саме так).
Для екземплярів і розв’язків дозволимо інші об’єкти (наприклад, графи),
де передбачається зручне кодування, можливо, встановивши xS Ø, якщо x
недопустимий код. Пишемо і також для багатовимірних варіантів,
тобто використовується як частковий порядок , де i для всіх .i
kN -вершинно-помічений (відповідно kN -реберно-помічений) граф є трійка
( , , )G V E l , така, що ( , )V E представляє собою граф, і : kl V N (відповідно,
: kl E N ) є загальна функція.
РЕОПТИМІЗАЦІЯ 2-КРИТЕРІАЛЬНОЇ ЗАДАЧІ ПРО УЗАГАЛЬНЕНУ ВИКОНУВАНІСТЬ
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 147
Верхній індекс x у f і S може бути опущений, якщо це ясно з контексту.
Проекція xf на i -ту компоненту позначається як x
if , де ( )x
i if s v , якщо
1( ) ( ,..., )x
kf s v v . Крім того, відношення порядку визначається як
1,..., k також записується у вигляді 1( ,..., )k . Якщо a b ми говоримо,
що a слабо домінує b (тобто, a за меншою мірою, так само добре, як b ). Якщо
a b і a b ми говоримо, що a домінує b . Зверніть увагу, що завжди вка-
зує у напрямку кращого значення. Якщо f і x зрозуміло з контексту, то ми
поширюємо на комбінації значень і розв’язків. Таким чином, ми можемо
говорити про слабке домінування між розв’язками і писати ,s t якщо
( ) ( ), ,x xf s f t s c якщо ( )xf s c , і так далі, де , xs t S і kc N .
Для наближення треба послабити поняття домінування на коефіцієнт .
Для будь-якого дійсного 1a визначимо
a
u v u a v і
a
u v a u v .
Фіксуємо 1( ,..., )k , де { , }i нехай 1( ,... ),kp p p 1( ,..., ) k
kq q q N
і 1( ,..., ) k
ka a R , де 1,..., 1ka a . Будемо говорити, що p слабо – домінує
,q p q
скорочено, якщо
i
i i ip q
, для 1 i k .
Нехай A і B множини. F – багатозначна функція з A у B , якщо
F A B . Множина значень x є ( ) { : ( , ) }set F x y x y F . F називається
загальною, якщо для всіх ,x ( )set F x Ø.
Для порівняння понять розв’язків оптимізаційних задач нам необхідне
відповідне поняття зведення. Введемо поняття розв’язків :F
( ) { :set F x y y розв’язує x у термінах розв’язків поняття }F .
В цьому сенсі, поняття розв’язку – загальна багатозначна функція, яка відо-
бражає екземпляр x на всі ( )y set F x . Таким чином, поняття розв’язку мож-
на порівняти з допомогою зведень для загальної багатозначної функції. Ми ви-
користовуємо означення Зельмана [12] зведення за поліноміальний час Тюрінга
для багатозначних функцій, обмежених загальною багатозначною функцією.
Загальна функція f – уточнення загальної багатозначної функції ,F якщо для
всіх , ( ) ( ).x f x set F x Загальна багатозначна функція F поліноміально зво-
диться по Тюрінгу до загальної багатозначної функції , ,p
TG F G якщо існує
детермінована поліноміально обмежена оракульна машина Тюрінга ,M така, що
уточнення g функції G випливає, що M з ,g як оракул обчислює загальну
функцію, що є уточненням .F Зазначимо, що оракульна модель передбачає, що
p
T – транзитивний, навіть якщо довжина елементів в ( )set F x не є поліно-
міально обмеженою по x .
В.О. МИХАЙЛЮК, Т.І. ЧЕПРАСОВА, Н.А. ДРЕЙЧАН
ISSN 2616-938Х. Компьютерная математика. 2018, № 2148
F називається поліноміально розв’язною, якщо існує загальна поліноміаль-
но обчислювана функція ,f така, що f – уточнення F . Поняття розв’язку F
називається NP -складним, якщо всі задачі в NP поліноміально зводяться до .F
Для k -критеріальної задачі ( , , )O S f обговоримо кілька понять
«розв’язання O ». Таким чином, ми зацікавлені тільки в недомінованих роз-
в’язках, які називаються Парето-оптимальними розв’язками.
D O домінуюче поняття розв’зку.
Обчислити розв’язок, який слабо домінує заданий цільовий вектор.
Вхід: екземпляр ,x цільовий вектор kc N .
Вихід: деякий xs S з ( )xf x c або повідомити, що немає таких s .
W O зважене поняття суми (тільки, якщо всі цілі треба мінімізувати або
максимізувати).
Одноцільова задача яка «зважує» всі цілі заданим способом.
Вхід: екземпляр x , вектор ваги kw N .
Вихід: деякий ,xs S що оптимізує
1
( )
k x
i ii
w f s
або повідомити,
що xS Ø.
Припускатимемо, що ці поняття аналогічні поняттю точного оптимального
розв’зку в звичайній однокритеріальній оптимізації.
Багатокритеріальні поняття наближення. Ми обговоримо розумні понят-
тя «наближеного розв’язку для O » для k -критеріальної задачі ( , , )O S f ,
де визначене з 1,..., k . Наведемо – наближені версії D O і .W O
D O – наближене поняття домінуючого розв’язку.
Обчислити розв’язок, який слабо – домінує заданий цільовий вектор.
Вхід: екземпляр ,x цільовий вектор .kc N
Вихід: деякий ,xs S такий, що s c
або повідомити, що не існує таких
,xs S що s c
.
W O – наближене поняття зваженої суми (якщо всі завдання зводять-
ся до мінімуму або максимуму).
Однокритеріальна задача, що «зважує» цілі заданим способом.
Вхід: екземпляр ,x вектор ваги kw N .
Вихід: деякий ,xs S такий, що
11 1
( ) ( ')
k kx x
i i i ii i
w f s w f s
для всіх ' xs S (1)
або повідомити, що xS Ø.
РЕОПТИМІЗАЦІЯ 2-КРИТЕРІАЛЬНОЇ ЗАДАЧІ ПРО УЗАГАЛЬНЕНУ ВИКОНУВАНІСТЬ
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 149
Означення 1. Нехай :{ 1,1} {0,1}kP – предикат. Екземпляр задачі
Max CSP P складається з m зважених обмежень, кожне з яких є k -кортеж
літералів
1
( ,..., ),
ki iz z взятих з множини 1 1{ ,..., , ,..., }.n nx x x x Всі змінні в цьому
кортежі вважаються різними. Обмеження виконано тоді і тільки тоді, коли P
приймає цей кортеж. Розв’язок є приписування істиннісних значень до
1{ ,..., }.nx x Значення розв’язку є
1
1
( ,..., )
k
m
i i i
i
w P z z
, де iw – (невід’ємна) вага
i -го обмеження. Мета полягає у максимізації цього значення. Коли P залежить
від не більше ніж k літералів Max CSP P будемо називати Max kCSP P ,
якщо в P рівно k літералів, то Max EkCSP P . Поряд з проблемами типу
Max CSP P розглядаються проблеми типу CSP P , де мета полягає у знахо-
дженні такого приписування, що всі обмеження виконані (аналогічно визнача-
ються kCSP P і EkCSP P ).
Якщо в комбінаторній k -критеріальній оптимізаційній задачі, що визнача-
ється кортежем ( , , )S f f визначається через предикати ,P а є ,
то будемо говорити про k -критеріальну задачу про виконуваність.
У випадках W O розв’язок ,s будемо називати -наближеним розв’яз-
ком. Має місце твердження 1, 2, що є аналогом тверджень 2, 3 з [11].
Твердження 1. Для будь-якої k -критеріальної задачі про виконуваність
( , , )O S f і будь-якого 0 1 виконується
( ,..., ) .k k p
TD O W O
Твердження 2. Наступні твердження еквівалентні для деякої k -критері-
альної задачі про виконуваність ( , , ) :O S f
• D O поліноміально розв’язувана для деяких 1( ,..., )k з 0 1i .
• W O поліноміально розв’язувана для деякого 0 1 .
Реоптимізація 2-критеріальної задачі про узагальнену виконуваність.
Нехай ( , , )O S f – 2-критеріальна задача про узагальнену вико-
нуваність ( 2 CSP , скорочено) екземплярами є предикат ,P вагові
коефіцієнти 1 2( ) ( ( ), ( )),w p w p w p p P з невід’ємними компонентами,
1
1 1 1 1 2 1( ( ) ( )P
p P
f p w p p w p
для вагового вектора з невід’ємними компонен-
тами 1 2( , )w w w , maxPf .
Нехай Max EkCSP P довільна CSP задача, I довільний екземпляр
задачі Max EkCSP P , екземпляр 'I задачі отримується з екземпляра I
додаванням довільного ( 1)m -го обмеження
В.О. МИХАЙЛЮК, Т.І. ЧЕПРАСОВА, Н.А. ДРЕЙЧАН
ISSN 2616-938Х. Компьютерная математика. 2018, № 2150
1
( 1)( 1) ( ,...,mm
iz z ( 1)
1 1( { ,..., , ,..., }, [ ])
j
m
n niz x x x x j k
з деякими вагами
( 1)( )mw p ( 1)( 1)
1 2( ( ), ( ))mmw p w p .
Визначимо реоптимізаційний варіант задачі Max EkCSP P і 2 CSP .
Задача 2Ins CSP . Вхідні дані. Довільний екземпляр I задачі
Max EkCSP P або 2 ,CSP *p оптимальний розв’язок екземпляра .I
Результат. Знайти оптимальний розв’язок екземпляра 'I (отриманого ви-
ходячи з ,I як описано вище) задачі 2 ,CSP використовуючи *.p
Мета. Знайти ,p який максимізує число виконаних обмежень екземпляра 'I .
Оскільки випадкове приписування виконує довільне P -обмеження з ймо-
вірністю 1( ) 2 (1)kd P P , має місце теорема.
Теорема 1. 1) 2-критеріальна задача про узагальнену виконуваність
( 2 CSP ) задовольняє поняттю ( )d PW O і є поліноміально розв’язуваною;
2) 2-критеріальна задача про узагальнену виконуваність ( 2 CSP ) задово-
льняє поняттю 2 ( ),2 ( )d P d PD O і є поліноміально розв’язуваною.
Доведення. 1. Припустимо є екземпляр з m обмеженнями. Випадкове при-
писування виконує кожне дане обмеження з ймовірністю ( )d P і, таким чином,
виконує ( )d P m обмежень в середньому. Оскільки оптимальне приписування
виконує не більше m обмежень маємо випадковий ( )d P – наближений алго-
ритм. Методом умовних ймовірностей цей випадковий алгоритм може бути
дерандомізованим [13].
2. Цей результат можна встановити, застосовуючи твердження 1 і 2 до дове-
дення 1.
Теорема 2. 1) реоптимізаційна версія 2-критеріальної задачі про узагальне-
ну виконуваність ( 2Ins CSP ) задовольняє поняттю
1
2 ( )d PW O і є поліно-
міально розв’язуваною;
2) реоптимізаційна версія 2-критеріальної задачі про узагальнену виконува-
ність ( 2Ins CSP ) задовольняє поняттю
2 2,
2 ( ) 2 ( )d P d PD O
і є поліноміально
розв’язуваною.
Доведення 1. Нехай I екземпляр задачі 2 ,CSP який складається з систе-
ми обмежень ( ){ , [ ]}iC z i m і оптимального розв’язку *;p *( )w p число
виконаних обмежень у системі C є розв’язком *.p До системи додається
РЕОПТИМІЗАЦІЯ 2-КРИТЕРІАЛЬНОЇ ЗАДАЧІ ПРО УЗАГАЛЬНЕНУ ВИКОНУВАНІСТЬ
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 151
обмеження ( 1)mz з деякими вагами ( 1) ( 1) ( 1)
1 2( ) ( ( ), ( ))m m mw p w p w p , в резуль-
таті отримуємо екземпляр 'I задачі 2 CSP , нехай *
'Ip його оптимальний
розв’язок. Якщо *
'Ip не виконує обмеження ( 1)mz , тобто *p оптимальний
розв’язок екземпляра 'I задачі 2Ins CSP , звідси отримуємо
* *
' 1( ) ( )I mw p w p , (2)
де ( 1) ( 1)
1 1 2
m m
m w w
(у лівій частині записана умова, що *p оптимальний
розв’язок 'I , а в правій, що оптимальний розв’язок не виконує обмеження
( 1)mz ). Нехай *
'Ip виконує обмеження ( 1)mz і є l варіантів, при яких буде
виконано обмеження ( 1)mz (очевидно, 2kl ). Побудуємо l наближених
розв’язків ( [ ])ip i l наступним чином. Беремо i -те приписування, яке виконує
( 1)mz . Із системи обмежень видаляємо ( 1)mz і до обмежень, які залишилися
(враховуючи результат приписування), застосовуємо деякий поліноміальний
-наближений алгоритм, отримаємо наближений розв’язок ip . В результаті
отримуємо
* *
' 1 1 ' 1( ) ( ( ) ) ( ) (1 ).i
I m m I mw p w p w p (3)
Домножимо (2) на 1 і додамо до (3) отримуємо
* * * *
' 1 ' 1 '(1 ) ( ) ( ) (1 )( ( ) ) ( ) (1 ) ( ).i
I m I m Iw p w p w p w p w p
Серед розв’язків *p і ip вибираємо найкращий (тобто з найбільшим зна-
ченням цільової функції w ) і позначаємо p . Маємо
* *
'( ) (1 1)max{ ( ), ( )} (2 ) ( ).i
Iw p w p w p w p
Звідки *
'
1( ) ( )
2 Iw p w p
. Oписаний алгоритм буде поліноміальним,
оскільки при 2k 2k cn ( n загальне число змінних, constc ). Таким
чином, в результаті виконання описаного алгоритму отриманий наближений
розв’язок p екземпляра 'I з відношенням апроксимації 1
2
. Ясно, що
завжди 1 ( 1)
2
. Покладемо 1( ) 2 (1)kd P P , тобто застосувавши
наближений поліноміальний алгоритм з теореми 1, отримаємо твердження даної
теореми.
2. Цей результат можна встановити, застосовуючи твердження 1 і 2 до дове-
дення 1.
В.О. МИХАЙЛЮК, Т.І. ЧЕПРАСОВА, Н.А. ДРЕЙЧАН
ISSN 2616-938Х. Компьютерная математика. 2018, № 2152
Таким чином, для реоптимізаційних версій багатокритеріальних оптиміза-
ційних задач отримані поліпшені розв’язки (з кращою якістю наближення).
Висновки. Вивчається складність і наближення комбінаторних багатокри-
теріальних NP -складних оптимізаційних задач.
Визначені поняття розв’язків, наближених розв’язків, поняття NP-склад-
ності з допомогою поліноміальних зведень Тюрінга з багатозначних функцій.
Наводяться результати в яких випадках поліноміальна розв’язність перекла-
дається з одного поняття на інше. Для задач, де всі цілі максимізуються, резуль-
тати наближення перекладаються з однокритеріальної оптимізації на багатокри-
теріальну. Цей факт був встановлений при дослідженні реоптимізаційної версії
2-критеріальної задачі про узагальнену виконуваність при додаванні одного
зваженого обмеження.
В.А. Михайлюк, Т.И. Чепрасова, Н.А. Дрейчан
РЕОПТИМИЗАЦИЯ 2-КРИТЕРИАЛЬНОЙ ЗАДАЧИ ОБ ОБОБЩЕННОЙ
ВЫПОЛНИМОСТИ
Показано, что есть выигрыш в качестве приближения для реоптимизации 2-критериальной
задачи об обобщенной выполнимости. При добавлении некоторого взвешенного ограниче-
ния, соответствующее отношение аппроксимации есть 1 ( )(2 ( )) d Pd P , где для соответст-
вующей однокритериальной задачи существует d(P) – приближенный полиномиальный алго-
ритм, (d(P) – это вероятность выполнения произвольного ограничения предиката P при рав-
новероятном выборе.
V.A. Mikhailyuk, T.I. Cheprasova, N.A. Dreychan
REOPTIMIZATION OF 2-CRITERIA SATISFIABILITY PROBLEM
It is shown that there is a gain in the quality of the approximation for the reoptimization of the
2-criteria problem of generalized satisfiability. When adding some weighted constraint, the corre-
sponding approximation ratio is 1 ( )(2 ( )) d Pd P , where there is a d(P)-approximated polyno-
mial algorithm for the corresponding one-objective problem (d(P) is the probability that an arbitrary
restriction of the predicate is satisfied with an equal choice).
Список літератури
1. Hardness and approximability in multi-objective optimization/[Glaβer Christian, Reitwieβner
Christian, Schmitz Heinz, Witek Maximilian]. Computability in Europe (CiE). 2010. Lecture
Notes in Computer Science (LNCS), 6158. 2010. P. 180 – 189.
2. Михайлюк В.О., Сергієнко І.В. Постоптимальний аналіз та наближені алгоритми ре-
оптимізації для задач дискретного програмування. Київ: Наукова думка, 2015. 248 с.
3. Ausiello G., Escoffier B., Monnot J. and Paschos V.Th Reoptimization of minimum and max-
imum traveling salesman’s tours. Lect. Notes Comput. Sci. 2006. Vol. 4059. P. 196 – 207.
4. Bockenhauer H.J., Forlizzi L., Hromkovic J. et al. On the approximability of TSP on local
modifications of optimal solved instances. Algorithmic Oper. Res. 2007. Vol. 2, N 2.
P. 83 – 93.
РЕОПТИМІЗАЦІЯ 2-КРИТЕРІАЛЬНОЇ ЗАДАЧІ ПРО УЗАГАЛЬНЕНУ ВИКОНУВАНІСТЬ
ISSN 2616-938Х. Компьютерная математика. 2018, № 2 153
5. Bockenhauer H. J., Hromkovic J., Momke T. and Widmayer P. On the hardness of reoptimiza-
tion. Lect. Notes Comput. Sci. 2008. Vol. 4910, P. 50 – 65.
6. Archetti C., Bertazzi L. and Speranza M.G. Reoptimizing the travelling salesman problem.
Network. 2003. Vol. 42. N 3. P. 154 – 159.
7. Ausiello G., Bonifacci V. and Escoffier B. Complexity and approximation in reoptimization.
In: S. Barry Cooper and Andrea Sorbi, Eds. Computability in Context: Computation and Logic
in the Real World. London: Imperial College Press. 2011. P. 101 – 130.
8. Mikhailyuk V.A. Reoptimization of set covering problems. Cybernetics and Systems Analysis.
2010. Vol. 46, N 6. P. 879 – 883.
9. Berger A.,Bonifaci V., Grandoni F.,Schafer G.Budgeted matching and budgeted matroid inter-
section via the gasoline puzzle. Mathematical Programming. 2011. 128(1–2). P. 355 – 372.
10. Ravi R., Goemans M.X. The constrained minimum spanning tree problem. Lect. Notes Com-
put. Sci. 1996. Vol. 1097. P. 66 – 75.
11. Tkachuk N.A. Some result on reoptimization of 2-objective minimum vertex cover. Theoreti-
cal and Applied Aspects of Cybernetics. Proceedings of the 4th International Scientific Confer-
ence of Students and Young Scientists. Kyiv: Bukrek, 2014. P. 231 – 237.
12. Selman A.L. A taxonomy on complexity classes of functions. Journal of Computer and System
Sciences. 1994. 48. P. 357 – 381.
13. Vazirani V.V. Approximation algorithms. Berlin: Springer, 2001. 380 p.
Одержано 10.12.2018
Про авторів:
Михайлюк Віктор Олексійович,
доктор фізико-математичних наук, професор,
завідувач кафедри прикладної математики та інформатики
Східноєвропейського національного університету імені Лесі Українки, Луцьк, Україна,
Е-mail: mikhailyukvictor2@gmail.com
Чепрасова Тетяна Іванівна,
кандидат педагогічних наук, доцент кафедри прикладної математики та інформатики
Східноєвропейського національного університету імені Лесі Українки, Луцьк, Україна,
Е-mail: cheprasova.tatiana@eenu.edu.ua
Дрейчан Надія Анатоліївна,
аспірантка Східноєвропейського національного університету імені Лесі Українки,
факультет інформаційних систем, фізики та математики, Луцьк, Україна.
Е-mail: nadyushka.dr@gmail.com
|