Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних
На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибо...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2017 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/131446 |
| 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: | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-131446 |
|---|---|
| record_format |
dspace |
| spelling |
Чупов, С.В. 2018-03-23T10:55:32Z 2018-03-23T10:55:32Z 2017 Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. 2616-5619 https://nasplib.isofts.kiev.ua/handle/123456789/131446 519.854.33 На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибору множин, які аналізуються алгоритмом, так щоб вони утворювали розбиття множини допустимих розв’язків задачі. Проведені експериментальні дослідження з використанням відомого тестового набору задач. Результати експериментів свідчать про високу якість, отриманих за прийнятний час, розв’язків. На основе анализа структурных особенностей задачи о многомерном булевом ранце, представлен алгоритм лексикографического поиска, в процессе работы которого определение лексикографических максимумов отдельных множеств осуществляется параллельно. Обосновывается правило выбора множеств, которые анализируются алгоритмом, так чтобы они образовывали разбиение множества допустимых решений задачи. Проведены экспериментальные исследования с использованием известного тестового набора задач. Результаты экспериментов свидетельствуют о высоком качестве, полученных за приемлемое время решений. On the basis of an analysis of the structural features of the multidimensional boolean knapsack problem it is presented the algorithm of lexicographic search in the course of work of which the determination of lexicographic maxima of separate sets is carried out in parallel. The rule of the selection of the sets, which are analyzed by the algorithm, so that they form a partition of the set of feasible values of the problem, is substantiated. Experimental researches using the known test set of problems have been conducted. The results of the experiments testify to the high quality of solutions obtained within a reasonable time. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних Приближенный алгоритм параллельного лексикографического поиска для многомерной булевой задачи о ранце при фиксированном упорядочении переменных The approximate algorithm of parallel lexicographical search for the multidimensional boolean knapsack problem with a fixed ordering of variables Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| spellingShingle |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних Чупов, С.В. |
| title_short |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_full |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_fullStr |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_full_unstemmed |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_sort |
наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| author |
Чупов, С.В. |
| author_facet |
Чупов, С.В. |
| publishDate |
2017 |
| language |
Ukrainian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Приближенный алгоритм параллельного лексикографического поиска для многомерной булевой задачи о ранце при фиксированном упорядочении переменных The approximate algorithm of parallel lexicographical search for the multidimensional boolean knapsack problem with a fixed ordering of variables |
| description |
На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибору множин, які аналізуються алгоритмом, так щоб вони утворювали розбиття множини допустимих розв’язків задачі. Проведені експериментальні дослідження з використанням відомого тестового набору задач. Результати експериментів свідчать про високу якість, отриманих за прийнятний час, розв’язків.
На основе анализа структурных особенностей задачи о многомерном булевом ранце, представлен алгоритм лексикографического поиска, в процессе работы которого определение лексикографических максимумов отдельных множеств осуществляется параллельно. Обосновывается правило выбора множеств, которые анализируются алгоритмом, так чтобы они образовывали разбиение множества допустимых решений задачи. Проведены экспериментальные исследования с использованием известного тестового набора задач. Результаты экспериментов свидетельствуют о высоком качестве, полученных за приемлемое время решений.
On the basis of an analysis of the structural features of the multidimensional boolean knapsack problem it is presented the algorithm of lexicographic search in the course of work of which the determination of lexicographic maxima of separate sets is carried out in parallel. The rule of the selection of the sets, which are analyzed by the algorithm, so that they form a partition of the set of feasible values of the problem, is substantiated. Experimental researches using the known test set of problems have been conducted. The results of the experiments testify to the high quality of solutions obtained within a reasonable time.
|
| issn |
2616-5619 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/131446 |
| citation_txt |
Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. |
| work_keys_str_mv |
AT čupovsv nabliženiialgoritmparalelʹnogoleksikografíčnogopošukudlâbagatovimírnoíbulevoízadačíproranecʹprifíksovanomuvporâdkuvannízmínnih AT čupovsv približennyialgoritmparallelʹnogoleksikografičeskogopoiskadlâmnogomernoibulevoizadačioranceprifiksirovannomuporâdočeniiperemennyh AT čupovsv theapproximatealgorithmofparallellexicographicalsearchforthemultidimensionalbooleanknapsackproblemwithafixedorderingofvariables |
| first_indexed |
2025-12-07T17:32:00Z |
| last_indexed |
2025-12-07T17:32:00Z |
| _version_ |
1850871613004709888 |