RAE.RU
Энциклопедия
ИЗВЕСТНЫЕ УЧЕНЫЕ
FAMOUS SCIENTISTS
Биографические данные и фото 17373 выдающихся ученых и специалистов
Логин   Пароль  
Регистрация Забыли пароль?
 

Кочетов Юрий Андреевич

Научная тема: « МЕТОДЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ДИСКРЕТНЫХ ЗАДАЧ РАЗМЕЩЕНИЯ »

Научная биография   « Кочетов Юрий Андреевич »

Членство в Российской Академии Естествознания

Специальность: 05.13.18

Год: 2009

Отрасль науки: Физико-математические науки

Основные научные положения, сформулированные автором на основании проведенных исследований:

  1. Совокупность результатов по разра­ботке и исследованию методов локального поиска для дискретных задач размещения, методы вычисления апостериорных оценок точ­ности, результаты по вычислительной сложности задач локального поиска и получению равновесных решений по Нэшу, а также кон­струкции сложных тестовых примеров.
  2. Разработаны и исследованы вероятностные методы локаль­ного поиска для ряда дискретных задач размещения. Все рассмат­риваемые задачи являются NP-трудными. Более того, одна из них, а именно конкурентная задача о р-медиане, является 2 -трудной, то есть имеет более высокий статус сложности, чем любая задача из класса NP. Полученные методы являются итерационными и в асимптотике позволяют находить точное решение задачи. Много­численные экспериментальные исследования показывают, что фак­тически оптимум находится достаточно быстро и предлагаемые ме­тоды могут с успехом применяться на практике.
  3. Для конкурентной задачи о р-медиане разработан точный конечный метод. Предшествующие аналоги основывались на схеме неявного перебора, что существенно ограничивало размерность ре­шаемых задач. Новый метод принципиально отличается от предше­ствующих. Он основан на оригинальной переформулировке задачи и идее постепенного наращивания семейства решений Конкурента. Новый метод позволяет существенно увеличить размерность ре­шаемых задач и дает общую схему получения оценок точности для приближенных методов решения данной задачи.
  4. Для задач унификации и стандартизации, являющихся обоб­щением задач размещения, разработаны итерационные методы вы­числения апостериорных оценок глобального оптимума. Эти мето­ды основаны на Лагранжевых релаксациях, что требует точного решения релаксированных задач. Исследована сложность получа­емых релаксированных задач, получены точные полиномиальные алгоритмы их решения.
  5. Исследована вычислительная сложность задачи нахождения локальных оптимумов для дискретных задач размещения с рядом полиномиально проверяемых окрестностей. Показано, что в худ­шем случае стандартный алгоритм локального улучшения может потребовать экспоненциального числа шагов при любом правиле замещения для каждой из рассматриваемых окрестностей и любого обобщения простейшей задачи размещения или любого обобщения задачи о р-медиане. Установлено, что задачи поиска локального оптимума принадлежат классу PLS (polynomial time local search problems), а некоторые из них являются плотно полными в этом классе. Если же требуется найти не произвольный локальный оп­тимум, а оптимум, достижимый из заданной стартовой точки, то такая задача часто оказывается PSPACE-полной.
  6. Исследована вычислительная сложность нахождения равно­весных решений по Нэшу в игровых моделях размещения. Показа­но, что поиск таких решений в чистых стратегиях является плотно PLS-полной задачей. В случае приближенных равновесных реше­ний ситуация может коренным образом измениться в зависимости от того, как оценивается допустимая погрешность. Найдены доста­точные условия, при которых поиск приближенных равновесных решений по Нэшу является полиномиально разрешимой задачей.
  7. Разработана уникальная электронная библиотека тестовых примеров «Дискретные задачи размещения». Она предназначена для проведения экспериментальных исследований и содержит пред­ложенные автором трудные тестовые примеры для различных мо­делей размещения. Построение и исследование таких тестов дает возможность увидеть границы применимости различных числен­ных методов, проводить сравнительный анализ алгоритмов и про­верять разные идеи и гипотезы. Уникальность библиотеки состоит в подборе оригинальных тестов разной вычислительной сложно­сти, имеющих небольшую размерность, но действительно трудных для нахождения точного решения.

Список опубликованных работ

1. Алексеева Е.В., Кочетов Ю.А. Генетический локальный по¬иск для задачи о р-медиане с предпочтениями клиентов // Дис¬кретный анализ и исследование операций. Серия 2. — 2007. — Т 14, № 1. — C. 3-31.

2. Береснев В.Л., Ибрагимов Г.И., Кочетов Ю.А. Алгоритмы решения задачи оптимального выбора динамического ряда изде¬лий // Управляемые системы / Сб. науч. тр. — Новосибирск: Ин-т математики СО АН СССР, 1984. — Вып. 24. — С. 3-19.

3. Васильев И.Л., Климентова К.Б., Кочетов К.Б. Новые ниж¬ние оценки для задачи размещения производства с предпочтения¬ми клиентов // Журнал вычислительной математики и математи¬ческой физики. — 2009. — Т. 49, № 6. — C. 1055-1066.

4. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жад¬ных алгоритмов для многостадийной задачи размещения // Дис¬кретный анализ и исследование операций. Серия 2. — 1999. — Т. 6, № 1. — С. 12-32.

5. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запре¬тами для дискретных задач безусловной оптимизации // Дискрет¬ный анализ и исследование операций. Серия 2. — 2002. — Т.9, № 2. — С. 13-30.

6. Кононов А.В., Кочетов А.В., Плясунов А.В. Конкурентные модели размещения производства // Журнал вычислительной ма¬тематики и математической физики. — 2009. — Т. 49, № 6. — C. 1037¬1054.

7. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дис-кретной математике и ее приложениям. — М: МГУ, 2001. — С. 87¬117.

8. Кочетов Ю.А. Вычислительные возможности локального по¬иска в комбинаторной оптимизации // Журнал вычислительной математики и математической физики. — 2008. — Т.48, № 5. — C. 747-764.

9. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Серия 2. — 2003. — Т. 10, № 1. — С.11-43.

10. Кочетов Ю.А., Пащенко М.Г. Лагранжевы релаксации в за¬даче выбора оптимального состава системы технических средств // Управляемые системы. — ИМ СО РАН, 1993, — вып.31. — С. 26-39.

11. Кочетов Ю.А., Пащенко М.Г. Динамические задачи выбора оптимального состава системы технических средств // Дискрет¬ный анализ и исследование операций — 1995. — Т. 2, № 1. — С. 36-49.

12. Кочетов Ю.А., Пащенко М.Г. Нижние границы в задаче выбора состава двухуровневой системы технических средств // Дискретный анализ и исследование операций. — 1995. — Т. 2, № 4. —С. 32-41.

13. Кочетов Ю.А., Пащенко М.Г., Плясунов А.В. О сложности локального поиска в задаче о р-медиане // Дискретный анализ и исследование операций. Серия 2. — 2005. — Т. 12, № 2. — С. 44-71.

14. Кочетов Ю.А., Плясунов А.В. Полиномиально разрешимый класс задач двухуровневого линейного программирования // Дис¬кретный анализ и исследование операций. Серия 2. — 1997. - Т. 4, № 2. — C. 23-33.

15. Кочетов Ю.А., Плясунов А.В. Задача выбора ряда изделий с частичным внешним финансированием // Дискретный анализ и исследование операций. Серия 2. — 2002. — Т. 9, № 2. C. 78-96.

16. Кочетов Ю.А., Столяр А.А. Использование чередующих¬ся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. Серия 2. — 2003. — Т. 10, № 2. — С. 29-55.

17. Кочетов Ю.А., Столяр А.А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. Серия 2. — 2005. — Т. 12, № 1. — С. 12-36.

18. Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the p-median problem // European Journal of Operational Research. — 2008. — V. 191, N 3. — P. 736-752.

19. Kochetov Yu., Alekseeva E., Levanova T., Loresh M. Large neig-hborhood local search for the р-median problem // Yugoslav Journal of Operations Research. — 2005. — V. 15, N 1. — P. 53-63.

20. ^d^ov Yu., Kononova P., Paschenko M. Formulation Space Search Approach for the Teacher/Class Timetabling Problem // Yu¬goslav Journal of Operations Research. — 2008. — V. 18, N 1. — P. 1-17.