Введение к работе
Актуальность темы диссертации. Многие задачи дискретной оптимизации могут быть представлены как задачи нахождения экстремума линейного функционала на некотором конечном множестве точек n-мерного пространства Ж", причем координаты этих точек обычно принимают значения 0,1 в некотором выделенном базисе. К числу этих задач относятся такие классические задачи как задача коммивояжера, задача о назначениях, задача о взвешенных паросо-четаниях, задача о максимальной клике в графе, задача о кратчайшей связывающей сети и др.
Изучение взаимосвязей между комбинаторными и геометрическими свойствами таких задач является одним из важнейших направлений исследования в области дискретной оптимизации.
Простое описание множества граней комбинаторного многогранника дает эффективный способ решения соответствующей комбинаторной задачи с помощью методов линейного программирования. Поэтому граненому описанию комбинаторных многогранников уделялось особое внимание. Однако большинство задач оптимизации линейного функционала на комбинаторных многогранниках являются в вычислительном отношении трудными (в предположении стандартной гипотезы Р ф NP). Для практического их решения в основном используются приближенные алгоритмы, основанные на разнообразных эвристиках. Анализ эффективности таких алгоритмов требует изучения других геометрических характеристик комбинаторных многогранников.
Среди возможных характеристик многогранника непосредственную оптимизационную интерпретацию имеют одномерные проекции, которым можно сопоставить множества значений линейного функционала на многограннике. Одним из объектов исследования в данной работе выбраны проекции вершин многогранника, иначе говоря, множества значений функционала в вершинах многогранника. Особый интерес при этом представляют случаи сильного вырождения, когда множество значений функционала мало.
Одним из немногих универсальных приемов решения задач дискретной оптимизации является стратегия локального поиска. В последнее время интерес к локальным алгоритмам усилился, главным образом благодаря простоте их реализаций (в том числе и для
устройств параллельных вычислений) и быстроте локального поиска. Хорошо известна геометрическая интерпретация проблемы точности локального поиска (т.е. совпадения локального экстремума с глобальным). Однако, как правило, интересные с практической точки зрения системы окрестностей неточны. Поэтому особую актуальность приобретает построение методов анализа качества различных систем окрестностей.
Цели диссертационной работы. Описание линейных функционалов с небольшим по мощности множеством значений. Построение геометрических характеристик для сравнения локальных алгоритмов, использующих разные системы окрестностей, и исследование с их помощью эффективности локального поиска в классических задачах дискретной оптимизации.
Научная новизна работы.
-
Для класса траекторных задач дискретной оптимизации дано описание тех задач, у которых множество значений функционала имеет небольшую мощность.
-
Для симметричной задачи коммивояжера с использованием такого описания найден новый подкласс полиномиально разрешимых задач.
-
Построен геометрический объект, описывающий качество системы окрестностей для алгоритмов локального поиска — многогранник доминирования.
-
Исследован вопрос о достижимости среднего значения функционала на любом локальном минимуме (непустота многогранника доминирования) для задачи коммивояжера, задачи о разбиении на клики, задачи квадратичного булева программирования (задача о максимальном разрезе) и задаче о кратчайшем ft-пути.
-
Для задачи коммивояжера и задачи квадратичного булева программирования исследовано следующее приближение в оценке качества локального минимума — наличие разрыва между средним значением функционала и максимальным из локальных минимумов (радиус шара, вписанного в многогранник доминирования). Установлена качественная разница между семействами окрестностей относительно 2- и 3-эамен в задаче коммивояжера. Доказано отсутствие разрыва между средним значением функционала и максимальным из локальных минимумов в задаче квадратичного булева программирования.
Практическая ценность работы. Полученные в диссертации результаты могут быть использованы для анализа точности алгоритмов локальной оптимизации. Описанные в работе сильно вырожденные функционалы могут быть использованы в качестве тестовых примеров для экспериментального и теоретического исследования алгоритмов решения соответствующих задач оптимизации.
Апробация работы. Основные результаты диссертации докладывались на семинаре по теории сложности ВЦ РАН и МИ РАН, на семинаре по дискретной математике факультета ВМиК МГУ и на Международном симпозиуме по дискретной математике (МГУ, 1995).
Публикации. По материалам диссертационной работы опубликовано 4 печатных работы.
Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы. Содержит 86 страниц текста, включая список литературы из 33 наименований.