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