Том 18, номер 4, 2011 г., Стр. 3-16

УДК 519.8
Береснев В. Л., Гончаров Е. Н., Мельников А. А.
Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций

Аннотация:
Для задачи оптимизации псевдобулевой функции рассматривается алгоритм локального поиска с обобщённой окрестностью. Такая окрестность строится для локально-оптимальных решений и включает в себя другие локально-оптимальные решения, «окружающие» данное. Приводятся результаты вычислительных экспериментов с использованием псевдобулевых функций, оптимизация которых эквивалентна задачам размещения предприятий, покрытия множества и конкурентного размещения предприятий. Целью экспериментов является сравнительная оценка локально-оптимальных решений, получаемых стандартным алгоритмом локального поиска и алгоритмом локального поиска с обобщённой окрестностью.
Табл. 6, библиогр. 11.

Ключевые слова: оптимизация, локальный спуск, полином от булевых переменных, задача размещения предприятий, задача о покрытии.

Береснев Владимир Леонидович ^1,2
Гончаров Евгений Николаевич ^1,2
Мельников Андрей Андреевич ²
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: beresnev@math.nsc.ru, goncharov@math.nsc.ru, a.a.melnikov@hotmail.com

Статья поступила 4 апреля 2011 г.

Литература

[1] Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. — Новосибирск: Изд-во Ин-та математики, 2005. — 408 с.

[2] Береснев В. Л. Верхние оценки для целевых функций дискретных задач конкурентного размещения предприятий / / Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 4. — С. 3-24.

[3] Береснев В. Л., Мельников А. А. Приближённые алгоритмы для задачи конкурентного размещения предприятий / / Дискрет, анализ и исслед. операций. — 2010. — Т. 17, № 6. — С. 3-19.

[4] http://old.math.nsc.ru/AP/benchmarks/

[5] Beasly J. Е. An algorithm for set covering problem // Eur. J. Oper. Res. — 1987. - Vol. 31. - P. 85-93.

[6] Beasly J. E. OR-library: distributing test problems by electronic mail // Eur. J. Oper. Res. - 1990. - Vol. 41. - P. 1069-1072.

[7] Dempe S. Foundations of bilevel programming. — Dordrecht: Kluwer Acad. Publ., 2002. - 332 p.

[8] Discrete location theory (eds. Mirchandani P. B., Francis R. L.). — New York: John Wiley and Sons, 1990. — 555 p.

[9] Dobson G., Karmarkar U. Competitive location on network // Oper. Res. - 1987. - Vol. 35. - P. 565-574.

[10] Hammer P. L., Rudeanu S. Boolean method in operations research and related areas. — Berlin: Springer-Verb, 1968. — 330 p.

[11] Local Search in Combinatorial Optimization. — Chichester: John Wiley and Sons, 1997. - 512 p.