Исследование и решение двухкритериальной задачи о покрытии множества

Исследование и решение двухкритериальной задачи о покрытии множества

Автор: Заозерская Лидия Анатольевна, Колоколов Александр Александрович

Журнал: Проблемы информатики @problem-info

Рубрика: Теоретическая информатика

Статья в выпуске: 1 (2), 2009 года.

Бесплатный доступ

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

Многокритериальная оптимизация, дискретная оптимизация, целочисленное программирование, задача о наименьшем покрытии множества, задача о доминирующем множестве, перебор l-классов, центр телекоммуникаций

Короткий адрес: https://sciup.org/14362798

IDR: 14362798

Список литературы Исследование и решение двухкритериальной задачи о покрытии множества

  • ЕРЕМЕЕВ А. В., ЗАОЗЕРСКАЯ Л. А., КОЛОКОЛОВ А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования//Дискретный анализ и исследование операций. Серия 2. 2000. Т. 7, № 2. С. 22-46.
  • КРИСТОФИДЕС Н. Теория графов. Алгоритмический подход. М: Мир, 1978.
  • BALAS E., CARRERA M. C. A dynamic subgradient-based branch and bound procedure for set covering//Oper. Res. 1996. V. 44, N 6. P. 875-890.
  • BALAS E., HO A. Set covering algorithms using cutting planes, heuristics and subgradient optimization: a computational study//Math. Prog. Study. 1980. V. 12. P. 37-60.
  • BEASLEY J. E., JORNSTEN K. Enhancing an algorithm for set covering problems//Europ. J. Oper. Res. 1992. V. 58. P. 293-300.
  • FISHER M. L., KEDIA P. Optimal solution of set covering/partitioning problems using dual heuristics//Manag. Sci. 1990. V. 36. P. 674-688.
  • LIFSCHITZ V., PITTEL B. The worst and the most probable performance of a class of set-covering algorithms//SIAM J. Comput. 1983. V. 12, N 2. P. 329-346.
  • ЗАОЗЕРСКАЯ Л. А. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества//Тр. 11-й Байкал. междунар шк.-семинара "Методы оптимизации и их приложения". Иркутск: S. n., 1998. Т. 1. С. 139-142.
  • EREMEEV A. V., KOLOKOLOV A. A., ZAOZERSKAYA L. A. A hybrid algorithm for set covering//Proc. of Intern. workshop on discrete optimization methods design. Minsk: S. n., 2000. P. 123-129.
  • КОЛОКОЛОВ А. А. Регулярные разбиения и отсечения в целочисленном программировании//Сиб. журн. исследования операций. 1994. № 2. С. 18-39.
  • САЙКО Л. А. Исследование мощности L-накрытий некоторых задач о покрытии//Дискретная оптимизация и анализ сложных систем: Сб. научн. тр. Новосибирск: Вычисл. центр СО АН СССР. 1989. С. 76-97.
  • CAPRARA A., FISCHETTI M., TOTH P. Algorithms for the set covering problem/DEIS -Operations Res. Group. 1998. Technical Rep. N OR-98-3.
  • RAHOUAL M., HADJI R., BACHELET V. Parallel ant system for the set covering problem//Lecture notes in computer science.: S. l.: Springer, 2002. P. 262-267.
  • SOLAR M. V. PARADA V., URRUTIA R. A parallel genetic algorithm to solve the set-sovering problem. Computer and operations research 29. 2002. P. 1221-1235.
  • НЕЧЕПУРЕНКО М. И., ПОПКОВ В. К., МАЙНАГАШЕВ С. М. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние, 1990.
  • ПОПКОВ В. К. Математические модели связности/Новосибирск: Ин-т вычисл. математики и мат. геофизики СО РАН, 2006.
  • CAPRARA A., FISCHETTI M., TOTH P., VIGO D. Modeling and solving the crew rostering problem//Oper. Res. 1998. V. 46. P. 820-830.
  • KITRINOU E., KOLOKOLOV A. A., ZAOZERSKAYA L. A. The location choice for telecenters in remote areas. The case of the Aegean islands//Proc. of the 2nd Intern. workshop on discrete optimization methods in production and logistics. Omsk: S. n., 2004. P. 61-65.
  • ЗАОЗЕРСКАЯ Л. А., КИТРИНОУ Е., КОЛОКОЛОВ А. А. Задача оптимального размещения центров телекоммуникаций в регионе//Тр. 13 Байкал. междунар. шк.-семинара "Методы оптимизации и их приложения". Иркутск: S. n., 2005. Т. 1. C. 469-475.
  • KOLOKOLOV A. A., ZAOZERSKAYA L. A. A bicriteria problem of optimal service centers location//Proc. of 12th IFAC intern. symp., St. Etienne (France), 17-19 мay 2006. Elsevier, 2006. S. l.: V. 3. P. 429-434.
  • ПОДИНОВСКИЙ В. В. Оптимизация по последовательно применяемым критериям/В. В. Подиновский, В. М. Гаврилов. М.: Советское радио, 1975.
  • ПЕРЕПЕЛИЦА В. А. Многокритериальные задачи теории графов. Алгоритмический подход. Киев: УМК ВЩ ЗГУ, 1989.
  • ЕМЕЛИЧЕВ В. А., КРАВЦОВ М. К. О неразрешимости векторных задач дискретной оптимизации на системах подмножеств в классе алгоритмов линейной свертки критериев//Докл. АН. 1994. Т. 334, № 1. C. 9-11.
  • ЕМЕЛИЧЕВ В. А., КРАВЦОВ М. К., ЯНУШКЕВИЧ О. А. Лексикографические оптимумы многокритериальной задачи дискретной оптимизации//Математические заметки. 1995. Т. 58, вып. 3. C. 365-371.
  • CHVÁTAL V. A greedy heuristic for the set-covering problem//Mathematics Oper. Res. 1979. V. 4, N 3. P.233-235.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp