Решение задачи о покрытии минимальной мощности

Решение задачи о покрытии минимальной мощности

Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиск...

Full description

Saved in:
Bibliographic Details
Published in:Компьютерная математика
Date:2013
Main Author: Шило, В.П.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Subjects:
Теория и методы оптимизации
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/84759
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:Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-84759
record_format dspace
spelling Шило, В.П.
2015-07-14T16:06:11Z
2015-07-14T16:06:11Z
2013
Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос.
ХХХХ-0003
https://nasplib.isofts.kiev.ua/handle/123456789/84759
519.854.33
Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиска, использующий адаптивную настройку повторности и модифицированную целевую функцию. Приведены результаты обширных экспериментальных расчетов, которые показали преимущества предложенного алгоритма над известными лучшими алгоритмами. С помощью разработанного алгоритма найдено девятнадцать новых рекордных решений.
Робота присвячена розв'язанню NP-важкої задачі про покриття мінімальної потужності (MCSCP), що має численні застосування, – найбільш складному підкласу задач про покриття. Розглянуто кращі відомі алгоритми розв'язання цієї задачі. Запропоновано та досліджено новий випадковий алгоритм повторного локального пошуку, що використовує адаптивне настроювання повторності та модифіковану цільову функцію. Наведено результати експериментальних розрахунків, які показали переваги запропонованого алгоритму над відомими кращими алгоритмами. За допомогою розробленого алгоритму знайдено дев'ятнадцять нових рекордних розв'язків.
In this paper the Minimum Cardinality Set Covering Problem (MCSCP) is considered. The MCSCP is a NP-hard problem with a wide range of practical applications. MCSCP is the most complex subclass of the Set Covering Problem. We propose and investigate a new random algorithm with an adaptive iterative tuning based on the iterated local search. Our approach introduces a modifying objective function, which significantly improves the characteristics of the algorithm. The results of extensive computational experiments reveal a superior performance when compared with the stateof-the-art algorithms. The proposed approach improves the best existing solutions for 19 benchmark instances widely used in the literature.
Работа выполнена при частичной финансовой поддержке Украинского научно-технологического центра (грант № 5710).
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Компьютерная математика
Теория и методы оптимизации
Решение задачи о покрытии минимальной мощности
Розв'язання задачі про покриття мінімальної потужності
Random iterated local search algorithm for minimum cardinality set covering problem using modified objective function
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 Шило, В.П.
topic Теория и методы оптимизации
topic_facet Теория и методы оптимизации
publishDate 2013
language Russian
container_title Компьютерная математика
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Розв'язання задачі про покриття мінімальної потужності
Random iterated local search algorithm for minimum cardinality set covering problem using modified objective function
description Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиска, использующий адаптивную настройку повторности и модифицированную целевую функцию. Приведены результаты обширных экспериментальных расчетов, которые показали преимущества предложенного алгоритма над известными лучшими алгоритмами. С помощью разработанного алгоритма найдено девятнадцать новых рекордных решений. Робота присвячена розв'язанню NP-важкої задачі про покриття мінімальної потужності (MCSCP), що має численні застосування, – найбільш складному підкласу задач про покриття. Розглянуто кращі відомі алгоритми розв'язання цієї задачі. Запропоновано та досліджено новий випадковий алгоритм повторного локального пошуку, що використовує адаптивне настроювання повторності та модифіковану цільову функцію. Наведено результати експериментальних розрахунків, які показали переваги запропонованого алгоритму над відомими кращими алгоритмами. За допомогою розробленого алгоритму знайдено дев'ятнадцять нових рекордних розв'язків. In this paper the Minimum Cardinality Set Covering Problem (MCSCP) is considered. The MCSCP is a NP-hard problem with a wide range of practical applications. MCSCP is the most complex subclass of the Set Covering Problem. We propose and investigate a new random algorithm with an adaptive iterative tuning based on the iterated local search. Our approach introduces a modifying objective function, which significantly improves the characteristics of the algorithm. The results of extensive computational experiments reveal a superior performance when compared with the stateof-the-art algorithms. The proposed approach improves the best existing solutions for 19 benchmark instances widely used in the literature.
issn ХХХХ-0003
url https://nasplib.isofts.kiev.ua/handle/123456789/84759
citation_txt Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос.
work_keys_str_mv AT šilovp rešeniezadačiopokrytiiminimalʹnoimoŝnosti
AT šilovp rozvâzannâzadačípropokrittâmínímalʹnoípotužností
AT šilovp randomiteratedlocalsearchalgorithmforminimumcardinalitysetcoveringproblemusingmodifiedobjectivefunction
first_indexed 2025-12-07T20:08:38Z
last_indexed 2025-12-07T20:08:38Z
_version_ 1850881467871133696

Similar Items