Геометрия комбинаторных многогранников тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Г » и

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

ВЯЛЫЙ Михаил Николаевич

УДК 519.95

ГЕОМЕТРИЯ КОМБИНАТОРНЫХ МНОГОГРАННИКОВ

(01.01.09 - математическая кибернетика)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1995

Работа выполнена в Вычислительном центре РАН

Научный руководитель:

доктор физико-математических наук В.К. Леонтьев

Официальные оппоненты:

доктор физико-математических наук В.Б. Алексеев кандидат физико-математических наук Ю.Г. Сметанин

Ведущая организация:

Институт системного программирования РАН.

Защита диссертации состоится "... ггттт____199^г. в . 1. .1... ч.

на заседании диссертационного совета К002.32.01 Вычислительного центра РАН по адресу:

117967, Москва ГСП-1, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке МИ РАН. Автореферат разослан "¿иО" .......1995 г.

Ученый секретарь совета

доктор физико-математических наук

.В. Рудаков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации. Многие задачи дискретной оптимизации могут быть представлены как задачи нахождения экстремума линейного функционала на некотором конечном множестве точек п-мерного пространства К.", причем координаты этих точек обычно принимают значения 0,1 в некотором выделенном базисе. К числу этих задач относятся такие классические задачи как задача коммивояжера, задача о назначениях, задача о взвешенных паросо-четаниях, задача о максимальной клике в графе, задача о кратчайшей связывающей сети и др.

Изучение взаимосвязей между комбинаторными и геометрическими свойствами таких задач является одним из важнейших направлений исследования в области дискретной оптимизации.

Простое описание множества граней комбинаторного многогранника дает эффективный способ решения соответствующей комбинаторной задачи с помощью методов линейного программирования. Поэтому граненому описанию комбинаторных многогранников уделялось особое внимание. Однако большинство задач оптимизации линейного функционала на комбинаторных многогранниках являются в вычислительном отношении трудными (в предположении стандартной гипотезы Р ф NP). Для практического их решения в основном используются приближенные алгоритмы, основанные на разнообразных эвристиках. Анализ эффективности таких алгоритмов требует изучения других геометрических характеристик комбинаторных многогранников.

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

Одним из немногих универсальных приемов решения задач дискретной оптимизации является стратегия локального поиска. В последнее время интерес к локальным алгоритмам усилился, главным образом благодаря простоте их реализаций (в том числе и для

устройств параллельных вычислений) и быстроте локального поиска. Хорошо известна геометрическая интерпретация проблемы точности локального поиска (т.е. совпадения локального экстремума с глобальным). Однако, как правило, интересные с практической точки зрения системы окрестностей неточны. Поэтому особую актуальность приобретает построение методов анализа качества различных систем окрестностей.

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

Научная новизна работы.

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

2. Для симметричной задачи коммивояжера с использованием такого описания найден новый подкласс полиномиально разрешимых задач.

3. Построен геометрический объект, описывающий качество системы окрестностей для алгоритмов локального поиска — многогранник доминирования.

4. Исследован вопрос о достижимости среднего значения функционала на любом локальном минимуме (непустота многогранника доминирования) для задачи коммивояжера, задачи о разбиении на клики, задачи квадратичного булева программирования (задача о максимальном разрезе) и задаче о кратчайшем й-пути.

5. Для задачи коммивояжера и задачи квадратичного булева программирования исследовано следующее приближение в оценке качества локального минимума — наличие разрыва между средним значением функционала и максимальным из локальных минимумов (радиус шара, вписанного в многогранник доминирования). Установлена качественная разница между семействами окрестностей относительно 2- и 3-эамен в задаче коммивояжера. Доказано отсутствие разрыва между средним значением функционала и максимальным из локальных минимумов в задаче квадратичного булева программирования.

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

Апробация работы. Основные результаты диссертации докладывались на семинаре по теории сложности ВЦ РАН и МИ РАН, на семинаре по дискретной математике факультета ВМиК МГУ и на Международном симпозиуме по дискретной математике (МГУ, 1995).

Публикации. По материалам диссертационной работы опубликовано 4 печатных работы.

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы. Содержит 86 страниц текста, включая список литературы из 33 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается общая характеристика работы, сформулирована цель исследования и коротко изложено содержание глав диссертации.

Глава 1 носит вспомогательный характер. В §1 вводится класс изучаемых многогранников. Эти многогранники получаются как линеаризация семейства подмножеств п-элементного множества В. Если отождествить базовое множество В с выделенным базисом в пространстве К„, то подмножеству В' С. В соответствует (0-1)-вектор, координаты которого задаются характеристической функцией подмножества В'. Если задано семейство подмножеств, то выпуклая оболочка векторов, соответствующих элементам этого семейства, определяет связанный с данным семейством многогранник. В интересующих нас здесь задачах для элементов множества В задаются веса. Если рассматривать задачу ЛП на таком многограннике, то компоненты вектора, задающего линейный функционал, определяют веса соответствующих элементов базового множества, а значению функционала на некотором (0-1)-векторе соответствует сумма весов элементов В, входящих в соответствующее подмножество.

Если на множестве В действует некоторая группа, то ее действие естественно продолжается на множество всех подмножеств. Большинство известных многогранников комбинаторной оптимизации получается при выборе в качестве семейства подмножеств орбит этого продолжения (неприводимый случай) или объединения таких орбит (приводимый случай). Примеры таких многогранников даны в §2. Именно эти примеры и будут являться главным объектом изучения в последующих частях работы. Основным примером является многогранник 72.-3адачи, которая определяется так. Зафиксируем некоторый набор 11 = {7^1,... ,71п> ■ ■ •} графов. Задача ГС-ПОДГРАФ НАИМЕНЬШЕГО ВЕСА (сокращенно — 7?-задача) состоит в отыскании подграфа наименьшего веса среди всех подграфов, изоморфных графам из набора 72п, в заданном полном тг-вершинном взвешенном графе. Вес подграфа равен по определению сумме весов входящих в него ребер.

Как правило, размерность комбинаторных многогранников не совпадает с размерностью пространства, в котором их естественно определять описанной выше конструкцией. В §3 для изучаемых в данной работе многогранников вычисляются размерности аффинных оболочек и порождающие множества для ортогональных дополнений к аффинным оболочкам. В этом же параграфе при вычислении размерности многогранника задачи квадратичного булева программирования (или задачи о максимальном разрезе) доказана важная в техническом отношении лемма 3.4. Найден спектр линейного оператора на пространстве полных взвешенных графов, матричные элементы которого имеют вид

(Э(е,е) = о,

Ф(ех, 62) = Ь для пары ребер с общей вершиной, , . <5(еьег) = с для пары ребер, все вершины ко- ' ' торых различны.

Его собственные значения определяются как

До = а+с-2Ь, (2)

А1 = а + (п - 4)6 - (п - 3)с, (3)

А2 = а + 2(п-2)6+ ("¡"2)с- (4)

В главе 2 изучается множество возможных значений функционала комбинаторной задачи оптимизации. При геометрической интерпретации ему соответствуют 1-мерные проекции многогранников. Значение функционала на некоторой вершине комбинаторного многогранника (подмножестве базового множества) естественно интерпретировать как вес этого подмножества, равный сумме весов элементов.

Задача нахождения набора весов некоторого конкретного семейства подмножеств по заданному вектору весов вычислительно сложна уже хотя бы потому, что искомое множество может иметь экспоненциально большой размер по сравнению с длиной записи набора векторов. Однако трудными оказываются и такие ее варианты, когда мощность набора весов гарантировано невелика. В частности, стандартная ОТ-полная задача ГАМИЛЬТОНОВ ЦИКЛ легко сводится к проверке принадлежности числа вершин графа к набору весов гамильтоновых циклов в полном графе, если в качестве весов ребер полного графа мы используем характеристическую функцию множества ребер графа, проверяемого на гамильтоновость.

Алгоритмическая сложность (по модулю ожидаемого неравенства Р^^Р) задачи нахождения набора весов показывает, по-видимому, на сильную нерегулярность соответствующего отображения: (вектор весов, семейство подмножеств) (набор весов семейства). Интерес при этом вызывают оценки, которые можно получить для таких задач; частные случаи, когда можно строить набор весов, и возможность анализа специфики данного семейства по возможным наборам весов.

Важный частный случай рассматриваемой задачи о наборе весов получается, если рассмотреть множество всех частичных сумм весов элементов базового множества, что соответствует выбору в качестве семейства подмножеств всех подмножеств базового множества. Соответствующий многогранник является п-мерным единичным кубом. Оптимизационная задача на таком семействе легко решается по очевидным соображениям, однако задача определения принадлежности некоторого числа к набору весов (т.е. представление числа в виде частичной суммы некоторого подмножества чисел) является NP-пoлнoй. Если, однако, рассматривать зависимость времени работы соответствующего алгоритма не только от длины входа, но и от длины выхода, то для этой задачи легко строится

полиномиальный (в данном смысле) алгоритм порождения набора весов, являющийся вариантом хорошо известного метода динамического программирования.

В §4 рассматриваются свойства множества частичных сумм. Основное внимание уделено решению обратной задачи: по информации о наборе весов установить некоторые свойства вектора весов, породившего данный набор весов.

В §5 рассматривается общая структура набора весов в случае произвольной системы подмножеств.

Далее в этой главе изучается набор весов для специального класса задач: графовых траекторных задач. Траекторная задача порождается некоторым остовным регулярным подграфом полного графа или полного двудольного графа Вершины многогранника траекторной задачи соответствуют подграфам, изоморфным тЦ.

Рассматривается структура графовых траекторных задач с небольшой относительно п мощностью набора весов е. Множество таких задач обозначим с-1(Т, в). Оно, как показано в §5, является объединением подпространств с вырезанными пространствами меньшей размерности. Анализ особенностей таких задач позволяет описать комбинаторную структуру элементов множества с-1(Т,в). Основным результатом этой главы является теорема 6.1, описывающая свойства задач с малым набором весов, на ее основе строится полное описание множеств с-1(Т, 2) и с_1(Т, 3).

В силу линейной зависимости длины траектории от вектора длин (весов) ребер, множество с"*1 (7", в) инвариантно относительно сдвигов на вектора из множества с_1(7", 1), что задает естественную эквивалентность на пространстве КК„.

Вводится основное для дальнейшей классификации понятие канонической функции.

Определение. Функция а называется «-канонической (или просто канонической, когда в ясно из контекста,), если:

1. для любого паросоиетания ж содержащегося в ее носителе найдется траектория г = г* , такая что

т П эирр а = 7Г (5)

2. число вершинного покрытия ао(вирра) < 2А(г + 1)(в — 1), где

г = А = 1 б обычном случае и А = 2 в двудольном

случае.

Имеют место следующие свойства канонических функций.

Свойство 1. Размер у (и) максимального паросочетания в носителе канонической функции меньше е.

Свойство 2. Число различных весов ребер в а не больше е.

Свойство 3. Число различных ненулевых весов ребер, неинцидентных данному ребру е из носителя канонической функции, меньше в — 1.

Зафиксируем степень г графа-траектории . Будем считать, что параметры в, п имеют указанный выше смысл. Обозначим N = 2(г + 1)(з — 1). Даваемая ниже характеризация множеств с_1(«) справедлива при достаточно большом (относительно других параметров) числе вершин. Для точной формулировки введем следующие условия:

Определим функцию пх(г,«) как минимальное п, при котором выполняются (6-8), а функцию гс2(г,«) — как минимальное п, при котором выполняются (6,7,9).

Теорема 6.1. Пусть а £ с-1 (в). Если не содержит чиклов длины 3, то из п > п^г, в) следует, что имеется эквивалентная а каноническая функция ю. Если же имеет циклы длины 3, то существование эквивалентной канонической функции следует из п > "2(1*, в).

Доказательство теоремы 6.1 приводится в §7, а в §8 приводятся следствия полученных результатов для задачи коммивояжера.

В главе 3 геометрический анализ применяется к алгоритмам локальной оптимизации на комбинаторных многогранниках.

При этом рассматриваются метрические системы окрестностей, для которых отношение соседства имеет простой геометрический

п>в + 1 + (г+1)(7\Г + 1), п > 2ЛГ (1 + 2(г - 1)(1 - г + г2)) /г, п > ЛГ(вг + 1),

(6)

(7)

(8)

смысл: соседями данной вершины являются все вершины, удаленные от данной на расстояние, не превосходящее некоторого числа г.

В §9 рассматривается следующий способ оценки качества локального поиска: достигнутое в результате локального поиска значение сравнивается с некоторой верхней оценкой минимального значения функционала. Систему окрестностей для локального поиска разумно считать качественной относительно данной оценки, если значение функционала в любом локальном оптимуме не превосходит этой оценки.

Очевидным способом построения таких оценок является усреднение функционала по некоторой мере на множестве допустимых решений. Такое усреднение имеет простой геометрический смысл. Любая точка многогранника есть выпуклая комбинация его вершин, т.е. среднее его вершин по некоторому распределению. Значение функционала в любой точке многогранника является верхней оценкой оптимального значения. Если можно построить тело, лежащее целиком внутри многогранника, для которого задача оптимизации решается эффективно, то вместо значения в некоторой точке можно использовать более точную верхнюю оценку: решение задачи ЛП на этом теле.

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

В простейшем случае в качестве точки, дающей оценку, берется барицентр многогранника. Его координаты для комбинаторных многогранников находятся просто. Более общий случай соответствует полиномиальным распределениям, т.е. таким распределениям, когда вес вершины многогранника полиномиально зависит от значения функционала в данной точке.

Далее рассматривается общий вопрос о достижимости средних на любом локальном минимуме. Вводится система локальных конусов и доказана теорема 9.1, которая сводит ответ на этот вопрос к проверке принадлежности вектора средних пересечению локальных конусов (многограннику доминирования).

Пусть задана некоторая система окрестностей А/. По ней определим систему локальных конусов С(У) = {С„|г; £ V}, где С„ — конус с вершиной V и образующими вида и — V, где и £ ]У(и).

Определение. Многогранником доминирования 0(М) для си-

стемы окрестностей N назовем пересечение всех локальных конусов С„.

Поскольку любой локальный конус содержится в опорном конусе к многограннику в данной вершине, то £)(ЛГ) С М, причем равенство достигается лишь в случае точной системы окрестностей.

Теорема 9.1. Пусть заданы система окрестностей Я и распределение р. Если £ 0(Я), то .АЛ локальный минимум для любого функционала не превосходит р-среднего для этого функционала. В противном случае найдется функционал, для которого существует такой N-локальный минимум V, что значение функционала на V больше р-среднего.

Если среднее достижимо на любом локальном оптимуме, то естественно задаться вопросом: верно ли, что значение в любом локальном минимуме меньше среднего на определенную величину? Ответ на этот вопрос дает теорема 9.2, которая утверждает, что разрыв имеется тогда и только тогда, когда вектор средних является внутренним вектором мног огранника доминирования.

Теорема 9.2. Если барицентр является внутренней точкой многогранника доминирования, то существует некоторая константа с такая, что для любого функционала а и любого локального минимума значение барицентрического среднего превосходит значение минимума по крайней мере на с||а||. В противном случае всегда найдется функционал, для которого значение некоторого локального минимума совпадает с барицентрическим средним.

Оценка величины этого разрыва возможна через оценку радиуса вписанного в многогранник доминирования шара. Для построения такой оценки используются линейные распределения. В качестве примера рассмотрен многогранник задачи квадратичного булева программирования (КБП). Локальные алгоритмы решения задачи квадратичного булева программирования представляют особый интерес. Дело в том, что модель нейронных вычислений Хопфилда может быть описана как локальная оптимизация квадратичного булева функционала. Поэтому оценки качества локальных минимумов в этой задаче могут прояснить вопрос об эффективности вычислений в модели Хопфилда. КБП является частным случаем 7£-задачи. При этом многогранник доминирования для КБП оказывается вы-

рожденным. Это дает основания полагать, что нейронные вычисления могут оказаться не слишком эффективными по сравнению с известными в теории локального поиска методами. Например, известный метод поиска переменной глубины может оказаться более эффективным (при большой длине последовательности замен) чем оптимизация, использующая асинхронный принцип Хопфилда.

Дальнейшее изложение построено следующим образом. В §10 описывается построение полиномиально вычислимых оценок качества локальных оптимумов для 72-задач (т.е. верхних оценок минимального значения функционала). Построены два класса таких оценок: ¿-фиксированные барицентры (т.е. среднее арифметическое по тем вершинам многогранника, которые имеют фиксированные значения некоторых выбранных к координат) и средние по полиномиальным распределениям при степени полинома к. В обоих случаях к = 0(1). В §9 показано, что вычисление средних по полиномиальным распределениям сводится к вычислению моментов равномерного распределения. Теорема 10.2 утверждает, что если порядок группы автоморфизмов графов И„, по которым строится 72,-задача, вычисляется за полиномиальное время, то моменты равномерного распределения также вычисляются за полиномиальное время.

Проверка принадлежности барицентрического среднего многограннику доминирования для конкретных TJ-задач производится в §11. Для задачи коммивояжера и задачи о разбиении на клики доказана достижимость барицентрического среднего в любом локальном минимуме

Локальные конусы для задачи коммивояжера рассмотрены в § 12. Исследованы,в основном две системы окрестностей: относительно 2-замен и 3-замен. Для первой из них доказана вырожденность многогранника доминирования при четном числе вершин и невырожденность при нечетном числе вершин. Многогранник доминирования для системы окрестностей относительно 3-замен оказывается невырожденным при любом числе вершин. Эти результаты можно считать теоретическим объяснением эмпирически наблюдаемого соотношения силы этих систем окрестностей.

Основные результаты диссертации опубликованы в работах:

1. М.Н. Вялый. Об одномерных проекциях многогранников задач дискретной оптимизации. // Дискретная математика. 1991. Т.З. №3. С.35-45.

2. М.Н. Вялый. Алгоритмы локальной оптимизации и геометрия многогранников. В сб. „Комбинаторные модели и методы". ВЦ РАН, 1995. С. 15-26.

3. М.Н. Вялый. Об оценках значений функционала в многогранниках задачи ПОДГРАФ НАИМЕНЬШЕГО ВЕСА. В сб. „Комбинаторные модели и методы". ВЦ РАН, 1995. С. 27-43.

4. М.Н. Вялый. О неразложимых графах. В сб. „Комбинаторные модели и методы". ВЦ РАН, 1995. С. 61-66.

М.Н. Вялый Геометрия комбинаторных многогранников

Подписано в печать 30. 10 .95 Формат бумаги 60 х 84 1/16 Тираж 100 экз. Заказ 7 7. Бесплатно

Отпечатано на ротапринтах в ВЦ РАН 117967, Москва, ул. Вавилова, 40