Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних
На основі аналізу структурних особливостей багатовимірної булевої задачі про ранець, представлено наближений алгоритм лексикографічного пошуку розв’язків високої якості, у процесі роботи якого визначення лексикографічних максимумів окремих множин здійснюється паралельно. Обгрунтовується правило вибо...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2017 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/131446 |
| 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: | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862711718155649024 |
|---|---|
| author | Чупов, С.В. |
| author_facet | Чупов, С.В. |
| citation_txt | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних / С.В. Чупов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 115-124. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| 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.
|
| first_indexed | 2025-12-07T17:32:00Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-131446 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-5619 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:32:00Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних Чупов, С.В. |
| title | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_alt | Приближенный алгоритм параллельного лексикографического поиска для многомерной булевой задачи о ранце при фиксированном упорядочении переменных The approximate algorithm of parallel lexicographical search for the multidimensional boolean knapsack problem with a fixed ordering of variables |
| title_full | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_fullStr | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_full_unstemmed | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_short | Наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| title_sort | наближений алгоритм паралельного лексикографічного пошуку для багатовимірної булевої задачі про ранець при фіксованому впорядкуванні змінних |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/131446 |
| 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 |