Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж

Запропоновано спосіб динамічної побудови дерева розгалуження у методі гілок та меж, що означає зміну кореневої вершини та порядку інших вершин у процесі пошуку. Також запропоновано використання нелінійних оцінок. Такі зміни призводять до підвищення ефективності методу гілок та меж....

Full description

Saved in:

Bibliographic Details
Date:	2019
Main Authors:	Бойко, В.В., Кузьменко, В.М., Ненахов, Е.І.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Series:	Теорія оптимальних рішень
Online Access:	http://dspace.nbuv.gov.ua/handle/123456789/161676
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж / В.В. Бойко, В.М. Кузьменко, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 67-72. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-161676
record_format	dspace
spelling	irk-123456789-1616762019-12-19T01:25:07Z Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж Бойко, В.В. Кузьменко, В.М. Ненахов, Е.І. Запропоновано спосіб динамічної побудови дерева розгалуження у методі гілок та меж, що означає зміну кореневої вершини та порядку інших вершин у процесі пошуку. Також запропоновано використання нелінійних оцінок. Такі зміни призводять до підвищення ефективності методу гілок та меж. Предложен способ динамического построения дерева ветвления в методе ветвей и границ, что означает смену корневой вершины и порядка других вершин в процессе поиска. Также предложено использование нелинейных оценок. Такие изменения приводят к увеличению эффективности метода ветвей и границ. A way for dynamic building of a branching tree in the branch and bound method is proposed. This way means changing the root vertex and the order of other vertices in the search process. Also, non-linear estimation of branches is proposed. Such changes lead to an increase of the efficiency of the branch and bound method. 2019 Article Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж / В.В. Бойко, В.М. Кузьменко, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 67-72. — Бібліогр.: 11 назв. — укр. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/161676 519.85 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Запропоновано спосіб динамічної побудови дерева розгалуження у методі гілок та меж, що означає зміну кореневої вершини та порядку інших вершин у процесі пошуку. Також запропоновано використання нелінійних оцінок. Такі зміни призводять до підвищення ефективності методу гілок та меж.
format	Article
author	Бойко, В.В. Кузьменко, В.М. Ненахов, Е.І.
spellingShingle	Бойко, В.В. Кузьменко, В.М. Ненахов, Е.І. Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж Теорія оптимальних рішень
author_facet	Бойко, В.В. Кузьменко, В.М. Ненахов, Е.І.
author_sort	Бойко, В.В.
title	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж
title_short	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж
title_full	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж
title_fullStr	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж
title_full_unstemmed	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж
title_sort	динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
url	http://dspace.nbuv.gov.ua/handle/123456789/161676
citation_txt	Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж / В.В. Бойко, В.М. Кузьменко, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 67-72. — Бібліогр.: 11 назв. — укр.
series	Теорія оптимальних рішень
work_keys_str_mv	AT bojkovv dinamíčnapobudovagíloknaosnovínelíníjnihocínokumetodígíloktamež AT kuzʹmenkovm dinamíčnapobudovagíloknaosnovínelíníjnihocínokumetodígíloktamež AT nenahoveí dinamíčnapobudovagíloknaosnovínelíníjnihocínokumetodígíloktamež
first_indexed	2025-07-14T14:15:59Z
last_indexed	2025-07-14T14:15:59Z
_version_	1837632124363997184
fulltext	ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 67 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Запропоновано спосіб динамічної побудови дерева розгалуження у методі гілок та меж, що означає зміну кореневої вершини та по- рядку інших вершин у процесі по- шуку. Також запропоновано ви- користання нелінійних оцінок. Та- кі зміни призводять до підвищен- ня ефективності методу гілок та меж.  В.В. Бойко, В.M. Кузьменко, Е.І. Ненахов, 2019 УДК 519.85 В.В. БОЙКО, В.М. КУЗЬМЕНКО, Е.І. НЕНАХОВ ДИНАМІЧНА ПОБУДОВА ГІЛОК НА ОСНОВІ НЕЛІНІЙНИХ ОЦІНОК У МЕТОДІ ГІЛОК ТА МЕЖ Вступ. Підхід до цілочисельної та комбінато- рної оптимізації на основі ідеї гілок та меж веде до широкого класу алгоритмів, що да- ють можливість розв'язувати трудні задачі або точно, або в межах деяких обґрунтованих оцінок. Ці методи існують у різних видах та формах. Використання такого підходу є доцільним, коли пошук оптимального розв'язку прямими методами є складною проблемою як в теоре- тичному сенсі, так і в сенсі необхідного об’єму розрахунків для задач з конкретними даними. Багато робіт з використання таких методів присвячені розв’язку задач із розміщення ви- робництва [1, 2]. Також цей метод застосову- ється до багатьох типів комбінаторних задач – багаторівневого розміщення виробництва [3], задач кластеризації [4], задачі комі- вояжера [5], задач з дисконтами [6], задачі k-центрів [7], задачі побудови розкладів для машин [8]. Для розв'язання оптимізаційної задачі ме- тодом меж та гілок на деякій допустимій множині рішень  мають виконуватися такі загальні властивості задачі. Множина допустимих розв'язків може бу- ти задана ефективно (скажімо, системою об- межень «помірної» кількості). Для певних підмножин допустимої мно- жини мають «легко» розраховуватися нижні L та верхні U межі по цільовій функції та нижні Lx та верхні Ux границі для змінних. В.В. БОЙКО, В.М. КУЗЬМЕНКО, Е.І. НЕНАХОВ 68 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 Ми розглядатимемо задачу пошуку  -мінімального значення цільової фун- кції ( , )f x y на допустимій множині, що визначається умовами ( , ) 0g x y  , x . Тут x та y – вектори багатовимірних просторів, умова ( , ) 0g x y  – уза- гальнене обмеження з неперервною функцією ( , )g   , а множина  визначає дискретну (комбінаторну) природу задачі через вектор змінних x . Вектор y є вектором неперервних змінних, які не обов'язково мають бути в задачі. Пошук  -мінімального значення означає, що ми шукаємо таку допустиму пару векторів ( , )x y  , що ( , ) min{ ( , ) \| ( , ) 0, }f x y f x y g x y x      , 0  . Загальна схема застосування методу гілок та меж для цієї задачі. Початкову допустиму множину  назвемо допустимою множиною рівня 0 і позначимо 0 . Рівень 0 назвемо найвищим. Цільовій функції найкращого припустимого розв’язку дамо значення Rf  , якщо такого розв’язку ще немає, або скінчене значення, якщо якийсь розв'язок є. Метод починає працювати з рівня 1, послідовно розбиваючи допустимі множини верхніх рівнів 1r на підмножини нижчих рівнів r i . Виконуються такі кроки: 1) розбиття поточної допустимої підмножини 1r на rk підмножин (як правило дві), що не перетинаються: 1 1 rkr r ii      , r r i j   , i j  , , 1,..., ri j k , r i   , 1,..., ;ri k 2) розрахунок нижніх r iL та верхніх r iU оцінок розв'язку задачі на підмно- жинах { ( , ) 0, }r r i ig x y x    , 1,..., ri k . Якщо r i  , то призначимо ;r r i iL U   3) оновлення рекордного (найкращого для знайдених припустимих розв’яз- ків задачі) значення цільової функції 1 2min{ , , , ..., }; r r r r R R kf f U U U 4) вибір підмножини r r i для подальшого розбиття серед тих, які можна ро- збити та для яких r i RL f   , 1,..., ;ri k 5) якщо така множина є, то перехід на крок 1 на наступному рівні 1r  для множини r r i . Якщо такої множини немає, то перехід на крок 4 з поверненням на рівень 1r  і уточнення нижньої оцінки для множини 1 1 r r i   : 1 1 1,..., min ; r r r r i i i k L L     6) припинення роботи, якщо 1 0r   . При досить простій формальній схемі методу його реалізація потребує конк- ретизації внутрішніх процедур, від яких залежить ефективність алгоритму. Це є вибір способу розбиття та кількості підмножин, розрахунок оцінок, вибір підм- ножини для подальшого розбиття. ДИНАМІЧНА ПОБУДОВА ГІЛОК НА ОСНОВІ НЕЛІНІЙНИХ ОЦІНОК У МЕТОДІ ГІЛОК ТА МЕЖ ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 69 Конкретизація і підбір внутрішніх процедур залежить від типу задачі. Але мають виконуватися такі загальні умови. Процедура розбиття має бути такою, щоб для конкретної задачі до початку роботи алгоритму була відома максимальна кількість рівнів maxr , що буде використана. Верхні і нижні оцінки повинні розраховуватися значно швидше ніж розв’язування задачі в цілому будь-яким іншим методом. При цьому оцінки мають бути побудовані таким чином, щоб для максимального рівня maxr на кроці 4 виконувалася умова maxr i RL f , max 1,..., ri k , така ж нерівність має ви- конуватися на будь-якому рівні для підмножин, які не можна розбити. Нижні оцінки не мають бути вище за оптимальний розв’язок задачі на поточній підм- ножині min{ ( , ) \| ( , ), }r r i iL f x y g x y x  , а верхні оцінки r iU мають бути зна- ченнями цільової функції ( , )f x y на знайдених припустимих розв’язках задачі. Якщо внутрішні процедури відповідають таким умовам, то метод повернеть- ся на рівень 0 за скінчену кількість кроків і буде виконана нерівності 0 min{ ' }RL f серед знайдених допустимих розв язків    , що означає, що най- кращий припустимий розв'язок є також і  -оптимальним розв’язком. Метод гілок та меж генерує дерево пошуку розв’язку, яке потенційно містить всі допустимі цілочисельні значення зміних x . Але в залежності від вибраних процедур та бажаної точності  піддерево, по якому пройде метод, може бути значно меншим, що напряму впливає на час пошуку розв’язку. Існують різні стратегії пошуку на дереві розв'язків. А саме: • пошук в глибину, що веде до більш швидкого зменшення рекордного зна- чення Rf ; • пошук у ширину, що веде до швидшого скорочення дерева пошуку за ра- хунок збільшення мінімальної нижньої оцінки; • вибір для розбиття в першу чергу вершини з кращими оцінками (мінімаль- на нижня оцінка r iL або мінімальна різниця r r i iU L ); • інші евристики. Одним з головних недоліків «класичного» підходу до пошуку на дереві є те, що максимальний «час», протягом якого вибраний на рівні r елемент розбиття може залишатися незмінним, є пропорційним кількості вершин дерева, що є до- чірніми до цього елемента, а це – величина порядку max(2 ) r r O  . Тобто, чим вище рівень елемента, тим довше він не змінюється при пошуку. Це може призводити до того, що метод витрачає багато часу на пошук на множині розв’язків, серед яких немає «хорошої» верхньої оцінки. Цей недолік пропонується подолати за рахунок динамічної побудови дерева розгалуження. А саме, за деяким правилом алгоритм, що реалізує метод, має змінювати через певну кількість кроків або через певний час порядок розбиття початкової множини  на підмножини. Зрозуміло, що такий порядок залежить В.В. БОЙКО, В.М. КУЗЬМЕНКО, Е.І. НЕНАХОВ 70 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 від множини  та способу розбиття. Так у випадку, коли компоненти вектора x є булевими змінними, а множина  складається з вершин одиничного гіперку- бу і розбиття здійснюється на дві підмножини шляхом фіксації окремих компо- нент на значеннях 0 або 1, зміною порядку розбиття може бути відміна фіксацій, що були зроблені на рівнях з 1-го по max / 2r , якщо на рівні maxr був знайдений припустимий розв'язок maxr U , що дав покращення рекорду Rf . Це дасть можли- вість шукати наступне покращення, використовуючи знайдений рекорд. Розглянемо тепер побудову нелінійних оцінок на прикладі задачі пошуку k медіан у неперервному просторі з евклідовою метрикою [9]. Задача полягає у пошуку множини C , що складається з k точок , 1,...,n iy R i k  , у просторі розмірності n таких, що сума зважених евклідових відстаней від m зафіксованих точок , 1,...,n jp R j m  , до множини C є мінімальною. Задачу можна сформулювати таким чином ,, 1 min , i ij j m j j y x j c    (1) за умов 2 (1 ) , 1,..., , 1,..., ,i j j ijy p x M i k j m       (2) 1 1, 1,..., , k ij i x j m    (3) {0,1}, 1,..., , 1,..., ,ijx i k j m   (4) 1, 1,..., ; , 1,..., ,n i jy R i k R j m     (5) де M велике число із значенням не меншим ніж 2, 1,..., max i j i j m p p   , 0jc  . При побудові нижньої оцінки для задачі (1) – (5) на рівні розгалуження r частина булевих змінних ijx є фіксованою, а нефіксовані змінні ми будемо розглядати як неперервні. В такому випадку задача (1) – (5) стає опуклою з ко- нічними обмеженнями (2) другого порядку. Для її розв'язання можуть бути використані як загальні методи опуклого програмування [10], так і спеціально розроблені для задач з конічними обмеженнями. Верхня оцінка отримується за рахунок побудови допустимого розв'язку з використанням евристики при збереженні значень фіксованих змінних. На- приклад, може бути використані евристики, що описані в [7] або [9]. Константа M відіграє важливе значення при розв’язуванні задачі (1) – (5). Формально її значення може бути як завгодно великим, але це погіршує оцінки ДИНАМІЧНА ПОБУДОВА ГІЛОК НА ОСНОВІ НЕЛІНІЙНИХ ОЦІНОК У МЕТОДІ ГІЛОК ТА МЕЖ ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 71 знизу. При використанні значення меншого ніж вказане вище задача не втрачає сенсу. Так при значенні 0 задача перетворюється в задачу Вебера [11] пошуку одного центру для всіх точок , 1,...,jp j m з мінімальною сумою відстаней. Для демонстрації залежності розв’язку задачі (1) – (5) при булевих та непе- рервних змінних ijx від значення константи M розв’язано серію задач для 20 точок і 3-х центрів з прикладу в [9]. Значення розв’язків наведено в табл. 1. ТАБЛИЦЯ 1 M Булеві змінні ijx Неперервні змінні ijx 0 1.176697 1.176697 1 0.9252061 0.5983953 2 0.5065739 0.2518134 3 0.4386914 0.1088168 4 0.4074184 0.0405136 5 0.4074184 0.0 7 0.3820393 0.0 Розрахункове значення M для цієї задачі дорівнює 6.1444. Але при такому значенні нижня границя дорівнює 0, що є неприйнятним. Щоб покращити ниж- ню оцінку введемо квадратичні штрафи за нецілі значення змінних ijx , а саме, добавимо до (1) штрафну складову 1 1 (1 ) k m ij iji j K x x      , де 0K  – штраф- ний множник. Такий штраф робить задачу неопуклою та багато екстремальною, але при невеликих значеннях K в задачі залишається один мінімум. Залежність цільової функції (1) та штрафу від значення K при 7M  в результаті пошуку локального мінімуму задачі (1) – (5) з неперервними змінними ijx наведено в табл. 2. Бачимо, що при значенні 0.05K  цільова функція (1) не змінилася, а при 0.5K  її значення перевищує оптимальне значення при булевих змінних. От- же, збільшити нижню оцінку і при цьому не перевищити значення розв'язку по- чаткової задачі та зберегти один локальний мінімум можна при незначному штрафному коефіцієнті K , контролюючи його через величину цільової функції (1). ТАБЛИЦЯ 2 K Цільова функція (1) + штраф Цільова функція Штраф без K 0.05 0.1918472 0.0 3.836944 0.1 0.3071568 0.02484152 2.823153 0.5 0.9428522 0.7168544 0.4519957 0.75 0.7836932 0.7836932 0.0 В.В. Бойко, В.Н. Кузьменко, Э.И. Ненахов В.В. БОЙКО, В.М. КУЗЬМЕНКО, Е.І. НЕНАХОВ 72 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 ДИНАМИЧЕСКОЕ ВЕТВЛЕНИЕ НА ОСНОВЕ НЕЛИНЕЙНЫХ ОЦЕНОК В МЕТОДЕ ВЕТВЕЙ И ГРАНИЦ Предложен способ динамического построения дерева ветвления в методе ветвей и границ, что означает смену корневой вершины и порядка других вершин в процессе поиска. Также пред- ложено использование нелинейных оценок. Такие изменения приводят к увеличению эффек- тивности метода ветвей и границ. V.V. Boyko, V.M. Kuzmenko, E.I. Nenakhov A DYNAMIC BRANCHING BASED ON NONLINEAR ASTIMATIONS IN THE BRANCH AND BOUND METHOD A way for dynamic building of a branching tree in the branch and bound method is proposed. This way means changing the root vertex and the order of other vertices in the search process. Also, non- linear estimation of branches is proposed. Such changes lead to an increase of the efficiency of the branch and bound method. Список літератури 1. Akinc U., Khumawala B.M. An efficient branch and bound algorithm for the capacitated ware- house location problem. Management Science. 23 (6). 1977. P. 545 – 665. 2. Bilde O., Krarup J. Sharp lower bounds and efficient algorithm for the simple plant location problem. Annals of Discrete Mathematics. 1. 1977. P. 79 – 97. 3. Tcha D., Lee B. A branch-and-bound algorithm for the multi-level uncapacitated facility loca- tion problem. European Journal of Operational Research. 18. 1984. P. 35 – 43. 4. Sherali H.D., Desai J.A Global Optimization RLT-based Approach for Solving the Hard Clus- tering Problem. Journal of Global Optimization. 2005. 32 (2). P. 281 – 306. 5. Gager G., Goldengorin B. How to make a greedy heuristic for the asymmetric traveling sales- man problem competitive. University of Groningen, Research Institute SOM (Systems, Organ- isations and Management), Research Report. 2005. 15 p. 6. Goldengorin B., Keane J., Kuzmenko V., Tso MK-S. Optimal supplier choice with discounting. Journal of the Operational Research Society. 62 (4). 2011. P. 690 – 699. doi:10.1057/jors.2009.164. 7. Fayed A., Atiya A. A mixed breadth-depth first strategy for the branch and bound tree of Eu- clidean k-center problems. Computational Optimization and Applications. 2013. 54 (3). 29 p. 8. Batsyn M., Goldengorin B., Sukhov P., Pardalos P. Lower and Upper Bounds for the Preemp- tive Single Machine Scheduling Problem with Equal Processing Times. Springer Proceedings in Mathematics and Statistics. 59. 2013. P. 11 – 27. doi: 10.1007/978-1-4614-8588-9_2. 9. Kuzmenko V., Uryasev S. Kantorovich-Rubinstein distance minimization: application to loca- tion problems. Large Scale Optimization Applied to Supply Chain & Smart Manufacturing: Theory & Real Applications. Springer Optimization and Its Applications. 2019. Р. 36 – 46. 10. Кузьменко В.Н., Бойко В.В. Использование PNK-метода для решения невыпуклых задач оптимизации. Теорія оптимальних рішень. 2012. – С. 47 – 52. 11. Fernandes I.F., Aloise D., Aloise D.J., Hansen P., Liberti L. On the Weber facility location problem with limited distances and side constraints. Optimization Letters, Springer. 2014. 8(2). P. 407 – 424. doi: 10.1007/s11590-012-0538-9. Одержано 18.03.2019

Динамічна побудова гілок на основі нелінійних оцінок у методі гілок та меж

Institution

Similar Items