Содержание к диссертации
Введение
1 Корневой полуметрический многогранник 16
1.1 Разрезной многогранник 16
1.2 Определение корневого полуметрического многогранника 19
1.3 Некоторые основные свойства корневого полуметрического многогранника 20
1.4 Корневой полуметрический многогранник
как релаксация разрезного многогранника 23
1.5 Минорные характеристики матрицы корневого полуметрического многогранника 26
2 Релаксационный многогранник задачи 3-SAT 31
2.1 Задача 3-ВЫПОЛНИМОСТЬ и ее релаксационный многогранник 31
2.2 Фасеты и целочисленные вершины 38
2.3 Нецелочисленные вершины 40
2.4 Задача целочисленного программирования на Pm,n 52
2.5 Задача распознавания целочисленности 61
3 Последовательности релаксационных многогранников задач о разрезе и 3-SAT 70
3.1 Релаксации многогранника задачи 3-SAT 70
3.2 Релаксации разрезного многогранника 76
4 Гиперграфы специального вида и свойства вершин релаксаций разрезного многогранника 88
4.1 3-однородные смешанные гиперграфы 89
4.2 Гиперграфы точек многогранника Мп,з 93
4.3 Свойства точек релаксаций Мп^ и Мп$ 97
4.4 О классе неинвертируемых гиперграфов 113
Приложение 1 129
- Определение корневого полуметрического многогранника
- Задача 3-ВЫПОЛНИМОСТЬ и ее релаксационный многогранник
- Релаксации многогранника задачи 3-SAT
- 3-однородные смешанные гиперграфы
Введение к работе
Актуальность темы исследования
Одной из основных задач прикладной математики является задача дискретной оптимизации, которая заключается в выборе наилучшего варианта из некоторого конечного набора дискретных альтернатив. Примерами таких задач являются: поиск кратчайшего пути в графе, задача о рюкзаке, оптимальное назначение работников на должности, нахождение минимального остовного дерева, задача коммивояжера. Область применения оптимизационных алгоритмов безгранична: механика и инженерное дело, практически вся экономическая теория, исследование операций и теория управления, криптография, а также многие и многие другие направления.
Наиболее простым методом решения подобных задач является полный перебор всех возможных альтернатив. Однако зачастую в задачах дискретной оптимизации множество вариантов не задается напрямую. Так, например, в задаче коммивояжера исходными данными являются города и расстояния между ними, а множество возможных маршрутов возникает опосредованно. При этом происходит так называемый «экспоненциальный взрыв» и количество вариантов растет экспоненциально быстро в зависимости от входных данных, отчего необходимые для полного перебора затраты времени и памяти делают применение алгоритма на практике невозможным. Подобные задачи составляют подкласс комбинаторной оптимизации.
Построением методов более эффективных, чем полный перебор, и определением причин труднорешаем ости некоторых задач занимается теория сложности алгоритмов. В этом направлении был получен ряд фундаментальных результатов, в частности теория Кука-Карпа об NP-полных задачах.
Одним из подходов к решению задач комбинаторной оптимизации является так называемый «геометрический подход». В его основе лежит представление множества вариантов задачи X в виде множества точек эвклидова пространства Жп и допущении, что функция цели линейна (как правило, это выполнено). Таким образом, задачу комбинаторной оптимизации можно представить как оптимизацию линейной функции на некотором множестве точек в w-мерном пространстве:
f{x) = (с, х) -» max\min, х EX.
В такой форме задача комбинаторной оптимизации напоминает постановку классической задачи линейного программирования. Идея задействовать алгоритмы линейного программирования для решения сложных оптимизационных задач появилась еще на заре развития данной теории,
заложенной в 1939 году Л. Канторовичем . Так, Дж. Данциг, Р. Фалкерсон и С. Джонсон опубликовали в 1954 году свою знаменитую работу по альтернативному подходу к решению задачи коммивояжера, используя новую геометрическую конструкцию: многогранник задачи коммивояжера. Семью годами ранее Данциг разработал симплекс-метод , который быстро стал основным аппаратом решения задач линейного программирования. На волне воодушевления от бесконечных приложений симплекс-метода, Данциг, Фалкерсон и Джонсон преобразовали задачу коммивояжера к задаче целочисленного линейного программирования и, применив симплекс-метод, решили ее для 49 столиц штатов США, что на тот момент было по-настоящему феноменальным результатом.
Следует отметить, что в строгом смысле симплекс-метод не является эффективным алгоритмом. Действительно, в 1972 году В. Кли и Д. Минти показали, что на незначительно скошенном единичном кубе (куб Кли-Минти) симплекс-метод работает по наихудшему сценарию и требует экспоненциального числа шагов . Тем не менее, уже в 1978 году Л. Хачиян модифицировал метод эллипсоидов Шора для решения задачи линейного программирования, доказав, что время вычисления будет гарантированно меньше полиномиальной функции от размерности задачи и количества входных данных . В дальнейшем были описаны и более эффективные алгоритмы решения задачи, в частности, алгоритм внутренней точки Кармаркара, однако, фундаментальность результата Хачияна заключалась в доказательстве принципиальной полиномиальной разрешимости задачи линейного программирования.
Работы Хачияна и Кармаркара устранили первое препятствие на пути геометрического подхода к решению задач комбинаторной оптимизации. Теперь переход к задаче линейного программирования фактически предлагал эффективный алгоритм решения большинства известных комбинаторных задач.
Тонкость, однако, заключается в том, что по теореме Вейля-Минковского произвольный выпуклый многогранник можно определить двумя эквивалентными способами: как выпуклую оболочку его вершин (внутреннее описание) или как систему неравенств, описывающую пересечение некоторых
Канторович, Л.В. Математические методы организации и планирования производства. - ЛГУ. 1939. -56с.
2 Dantzig, G.B., Fulkerson, R., Johnson, S.M. Solution of a large-scale traveling salesman problem
II Operations Research. Vol. 2. - 1954. - pp. 393-410
3 Dantzig, G.B. Programming in a linear structure II Econometrica. Vol. 17. - 1949. - pp. 73-74.
4 Klee, V., Minty, G.J. How good is the simplex algorithm? II Inequalities. Vol. 3. - Academic Press Inc.
1972.-pp. 159-175.
Хачиян, Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМ и МФ. Т. 20, №1. - 1980.-С. 51-69.
полупространств, задающих фасеты многогранника (внешнее описание). Задачи комбинаторной оптимизации сводятся к внутренней форме, а все эффективные алгоритмы описаны для внешней, между тем переход от вершин к фасетам является абсолютно нетривиальной задачей. Во-первых, она решена только для некоторых сравнительно «просто устроенных» классов комбинаторных многогранников, в то время как для большинства многогранников полного описания до сих пор не было построено. Во-вторых, зачастую многогранники задач имеют столь сложную структуру, что трудно даже принципиально говорить о возможном описании их фасет. Так, например, Л. Биллера и А. Сарангараджан доказали, что каждый 0/1 многогранник является гранью многогранника задачи коммивояжера . В-третьих, даже если для некоторого многогранника комбинаторно-оптимизационной задачи построено полное внешнее описание, вероятнее всего оно содержит экспоненциально большое число неравенств и эффективность алгоритмов линейного программирования будет потеряна уже на входных данных.
Кроме непосредственного применения алгоритмов линейного программирования для решения задач комбинаторной оптимизации, геометрический подход предлагает новые конструкции для изучения, а именно: многогранники задач. Объектом исследования является не только полное описание граней многогранников, что необходимо для перехода от вершин к фасетам, но и изучение различных комбинаторных характеристик граничных комплексов многогранников задач и использование этих характеристик, например, для оценки сложности соответствующих задач.
Одним из наиболее ярких примеров характеристик такого рода служит плотность графа многогранника задачи. Напомним, что плотность графа или кликовое число графа равно наибольшему количеству попарно смежных вершин или числу вершин в наибольшей клике. В работах В.А. Бондаренко установлено, что плотность графа многогранника служит нижней границей временной трудоемкости задачи в широком классе алгоритмов прямого типа, основанных на линейных сравнениях. К таким алгоритмам в частности относятся алгоритмы сортировки, «жадный» алгоритм, метод ветвей и границ, метод динамического программирования, венгерский алгоритм и другие широко известные комбинаторные методы.
В основе идеи лежит разбиение пространства Жп на конусы
6 Billera, L.J., Sarangarajan, A. All 0-1 polytopes are traveling salesman polytopes. II Combinatorica. Vol. 16.-Springer Berlin. 1996.-pp. 175-188.
Бондаренко, В.А. Многогранники с высокой плотностью графа и полиномиальная разрешимость задач комбинаторной оптимизации // Автоматика и телемеханика. №4. - 1993. - С. 21-26. Бондаренко, В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. - Ярославль: ЯрГУ, 1995.- 126с.
І) К(х) = Rn. хех Каждому элементу х множества X (каждому варианту в задаче оптимизации) ставится в соответствие свой конус
К(х) = {ш: (а),х) > (a),y),Vy Е X], образованный всеми целевыми векторами а) для которых функция fit) = (ш, t) на множестве X достигает максимума (или минимума, если в определении множества поменять знак неравенства) в точности на элементе х.
В 1956 году в своей знаменитой работе Д. Гейл переоткрыл циклические многогранники, описанные за 50 лет до него К. Каратеодори . Уже в IR4 циклические многогранники могут иметь как угодно много вершин, причем все они будут смежны. Конусное разбиение, построенное по такому многограннику, обладает тем свойством, что любые два конуса граничат друг с другом по (п — 1) -мерной грани. Алгоритм прямого типа, основанный на линейных сравнениях, отбрасывает часть конусов, деля пространства на два полупространства гиперплоскостью. В результате, для данного разбиения на каждом шаге может быть исключен только один конус, и полного перебора избежать принципиально невозможно.
Таким образом, плотность графа многогранника задачи в некотором роде отвечает на вопрос: «насколько сложна данная задача?». Действительно, для целого ряда известных труднорешаемых задач получена экспоненциальная нижняя оценка плотности графа многогранника, в то время как для полиномиально разрешимых задач установлены, соответственно, полиномиальные (а в некоторых случаях и линейные) верхние и нижние оценки
плотности .
Из всего вышесказанного следует, что большой интерес для изучения представляют многогранники с высокой плотностью графа, но простым полиномиальным внешним описанием. С одной стороны высокая плотность графа предполагает, что ассоциированные с многогранником задачи будут труднорешаемыми. С другой стороны, достаточно простая система линейных неравенств, определяющих фасеты многогранника, позволила бы без каких-либо проблем задействовать известные полиномиальные алгоритмы линейного программирования. Примером подобных многогранников могут являться так
Gale, D. Neighboring vertices on a convex polyhedron II Linear Inequalities and Related Systems. - Annals of Mathematics Studies. No. 38. - Princeton, New Jersey: Princeton University Press, 1956. - pp. 255-263. 9 Caratheodory, С Ueber den Variabilitatsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen II Mathematische Annalen. Vol. 64. - 1907. - pp. 95-115.
Бондаренко, B.A., Максименко, A.H. Геометрические конструкции и сложность в комбинаторной оптимизации. - М.: ЛКИ, 2008. - 184с.
называемые релаксационные многогранники задач, которые возникают, если в ограничениях комбинаторных задач целочисленным (дискретным) переменным разрешить принимать непрерывные значения. В частности к ним относятся рассмотренные в диссертации различные релаксации многогранника известной NP-полной задачи о максимальном разрезе графа, а также связанные с ними релаксации задачи 3-выполнимость булевых формул (3-SAT).
Цель работы
Целью работы является исследование и анализ свойств граничных комплексов различных релаксационных многогранников задачи о максимальном разрезе графа и задачи 3-SAT. В частности, рассмотрены вопросы описания и анализа свойств фасет многогранников, множеств целых и нецелочисленных вершин, а также построения эффективных алгоритмов решения частных случаев оптимизационных задач на изучаемых многогранниках.
Методы исследования
При решении поставленных задач использовались методы теории графов, линейного программирования, теории сложности алгоритмов, комбинаторного анализа, выпуклого анализа, в частности теории выпуклых многогранников, линейной алгебры.
Научная новизна
В диссертации получены следующие новые результаты:
Доказан субэкспоненциальный рост миноров матрицы, определяющей корневой полуметрический многогранник, с увеличением размерности пространства.
Установлено, что множество значений координат нецелочисленных вершин релаксационного многогранника задачи 3-SAT неограниченно: знаменатели координат растут сверхполиномиально с увеличением размерности пространства.
Построено необходимое условие нецел очи елейности вершин релаксационного многогранника задачи 3-SAT, позволяющее эффективно описывать вершины.
Получены линейные ограничения на целевые функции, при которых задачи целочисленного программирования и распознавания целочисленности полиномиально разрешимы.
Построены последовательности вложенных релаксаций Мпк и Pm'n многогранников задач о разрезе и 3-SAT. Обнаружены общие нецелочисленные вершины у различных релаксаций.
Установлена связь между классом гипер графов особого рода и точками многогранника Мп3 , в разложении которых в выпуклые комбинации вершин нет целых. Построены точки многогранников Мп4 и Мп5 , в любом разложении которых в выпуклые комбинации вершин многогранника Мп3 нет целых.
Теоретическая и практическая ценность
Работа носит теоретический характер. Полученные результаты могут быть применены для развития идей геометрического подхода к решению и анализу задач комбинаторной оптимизации, а также построению новых эффективных алгоритмов.
Апробация работы
Результаты работы докладывались на следующих научно-исследовательских семинарах и конференциях:
Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (Новосибирск. 2007 и 2008 гг.)
V Всероссийская научная конференция «Математическое моделирования и краевые задачи» ММ-2008. Самара. СамГТУ. 2008 г.
Научная конференция студентов и аспирантов факультета ИВТ. ЯрГУ 2008 г.
IV Международная научно-практическая конференция «Образование и наука в 21 веке». София. 2008 г.
Всероссийской научно-практической конференции с международным участием: «Информационные технологии и математическое моделирование» (Анжеро-Судженский филиал КемГУ 2008 и 2010 гг.)
Конференция «Математика. Информационные технологии. Образование. - МИТО-2008». ОГУ, Оренбург 2008 г.
Шестьдесят вторая региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь. Наука. Инновации - 2009». Ярославль, ЯГТУ 2009г.
Общероссийская электронная научная конференция «Актуальные вопросы современной науки и образования» (Красноярск 2009 и 2010 гг.)
9. XVI Международная конференция «Проблемы теоретической кибернетики». Нижний Новгород, 2011 г.
Публикации
По результатам исследования опубликовано 19 работ, в том числе 3 статьи в изданиях, рекомендованных ВАК РФ. Список публикаций приведен в конце автореферата.
Структура и объем работы
Диссертация состоит из введения, четырех глав, двух приложений и списка литературы. Полный объем диссертации - 138 страниц, список литературы содержит 69 наименований.
Определение корневого полуметрического многогранника
В работе В.А. Бондаренко[7] (см. также [6]) определен класс многогранников Мп С Е4" , п Є N. Позже он был независимо обнаружен Падбергом [60] и в дальнейшем изучался многими авторами, получив название корневой полуметрический многогранник (rooted semimetric polytope) [39] (также в литературе встречается название многогранник Бондаренко - Падберга [10]).
Корневой полуметрический многогранник был объектом многих исследований и достаточно подробно изучен. Основные результаты собраны в монографии Деза и Лоран [39], а также книге [2]. Приведем ряд свойств многогранника Мп, которые представляют интерес в рамках данного исследования.
Утверждение 1.3.5. Все целочисленные вершины многогранника Мп являются попарно смежными. Таким образом, плотность графа корневого полуметрического многогранника, как мера сложности ассоциированных задач, экспоненциальна по п и, как минимум, превосходит число целых вершин 2". Учитывая полиномиальную простоту внешнего описания, многогранник Мп представляет значительный интерес для изучения.
На этом месте следует остановиться и сделать важное замечание. Здесь и далее по ходу диссертации будут появляться экспоненциальные оценки вида 2". При этом размерность корневого полуметрического многогранника Мп равна п(п + 2)/2, размерность исходного пространства 4п2. Соответственно, относительно размерности пространства оценка примет вид 2 з . Строго говоря, это не экспоненциальная функция, так как показатель степени л/х не является полиномом от х. В то же время 2 А очевидным образом превосходит любую полиномиальную функцию. Как правило, подобные функции носят название субэкспоненциальных, хотя название еще не устоялось. Далее в диссертации под субэкспоненциальной будет пониматься сверхполиномиальная, но еще не экспоненциальная функция. Соответственно, плотность графа корневого полуметрического многогранника Мп субэспоненциальна по размерности пространства.
Обратно, для любой нецелочисленной вершины и найдется такое подмножество I QNn, для которого выполняются приведенные выше условия. Таким образом, еще одна причина значительного интереса к корневому полуметрическому многограннику обуславливается тем, что для него удается построить не только полное описание всех фасет, но и всех вершин. Соответственно переход между внутренним и внешним описаниями многогранника выполнен в обе стороны. 1.4 Корневой полуметрический многогранник как релаксация разрезного многогранника
Покажем связь между корневым полуметрическим и разрезным многогранниками через задачу о максимально разрезе. Рассмотрим целевую функцию / = (с,ж). Нетрудно проверить, что значение построенной данным образом функции f(z) в некоторой целой вершине z многогранника Мп в точности равно величине разреза, соответствующего этой вершине. Таким образом, мы свели задачу о максимальном разрезе к оптимизации линейной функции на целых вершинах многогранника Мп. Это задача известна как задача целочисленного линейного программирования (или просто целочисленного программирования).
Многогранник М%, порождаемый целыми вершинами корневого полуметрического многогранника (Mjf = conv(Z), где Z - множество целых вершин Мп) эквивалентен рассмотренному ранее разрезному многограннику. Действительно, число вершин разрезного многогранника CUT{n), по построению, равно 2П. Количество целых вершин корневого полуметрического многогранника Мп, а, соответственно, и всех вершин Mjf, также равно 2п (Утверждение 1.3.4). Вершины CUT(n) и М% однозначно соответствуют различным разрезам полного графа на п вершинах. Откуда, по транзитивности, следует, что существует взаимно однозначное соответствие между вершинами CUT(n) и М%.
Целевая функция / удовлетворяет этому условию, а значит, задача целочисленного программирования для нее сводится к задаче линейного программирования и задача об ориентированном максимальном разрезе полиномиально разрешима. Ранее этот факт был получен иными методами [12].
Как уже было отмечено выше, задача целочисленного программирования на корневом полуметрическом многограннике является iVP-трудной. В то же время в работе [5] был установлен следующий интересный факт, относительно оптимизации линейных функций на целых вершинах корневого полуметрического многогранника.
Задача 3-ВЫПОЛНИМОСТЬ и ее релаксационный многогранник
Многогранник Ртп также является релаксационным многогранником задачи о разрезе или релаксацией разрезного многогранника.
CUT{n) м смпс pmtn. Задача о максимальном разрезе не единственная комбинаторная задача, сводимая к задаче оптимизации линейной целевой функции на многограннике Рт,п. Приведем рассуждения для другой известной iVP-полной задачи: 3-выполнимость.
3-выполнимость (3-satisfiability, 3-SAT) - это частный случай общей задачи выполнимость булевых формул и одна из основных задач в теории Кука-Карпа о NP полноте. Напомним общую постановку задачи.
Условие. Задан набор С трехместных дизъюнкций вида с-, = а3 V Ь3 V с,, где j Є Nn. Логические переменные Oj,&j,Cj принимают свои значения из множества U = {иг,ЇГг : і Є Nm}.
Вопрос. Существует ли для множества U такой набор истинностных значений, при котором выполняются (будут истинны) все дизъюнкции из С?
Многогранник задачи 3-SAT строится по множеству логических переменных U и набору дизъюнкций С, соответствует индивидуальной задаче и обозначается через 3-SAT((7, С). Он представляет собой выпуклую оболочку всех характеристических векторов (наборов истинностных значений множества U) удовлетворяющих набору дизъюнкций С.
Из определения многогранника 3-SAT(/, С) следует, что его построение требует решения индивидуальной задачи 3-SAT и представляет значительное затруднение. Рассматриваемый в данной главе многогранник РШ]П, напротив обладает простым, полиномиальным по размерности пространства, внешним описанием и, как будет показано ниже, может быть использован для решения произвольной задачи 3-SAT.
Рассмотрим индивидуальную задачу 3-SAT. Пусть число дизъюнкций \С\ = п, количество логических переменных - т. Произвольному набору истинностных значений U сопоставим множество целых вершин многогранника -Рт,„, по следующим правилам: 1. если логическая переменная иг равна 1, то Vj : х 1 + х2г + zfj1 = 1; 1 Q ОО 4 0 2. если логическая переменная щ равна 0, то Vj : х + х + х" —\. Аналогично, набору дизъюнкций С сопоставим такой вектор с Є Ш6тп, что: 1. если г-тая переменная входит в j-тую дизъюнкцию на fe-том месте, то все координаты блока i,j равны 1, кроме cf 2, которая равна 0; 2. если отрицание г-той переменной входит в j-тую дизъюнкцию на fe-том месте, то все координаты блока г, j также равны 1, кроме c4j , которая равна 0; 3. все оставшиеся координаты вектора с равны 0.
Рассмотрим целевую функцию / = (с, х). По построению, каждый столбец вектора с содержит ненулевые координаты ровно в трех блоках. Отсюда напрямую следует выполнение следующего неравенства: Vz Є ZP n : f(z) 3n, где Zpmn - множество целых вершин многогранника Рт,п Действительно, у любой целой вершины многогранника Pmn в каждом координатном блоке стоит ровно одна единица, остальные координаты равны нулю, а значит, f{z) не может превосходить утроенного числа столбцов.
Вернемся к набору дизъюнкций С. Если он не выполним, то для любого набора истинностных значений логических переменных из U найдется ложная дизъюнкция сг Без ограничения общности, положим, что дизъюнкция с, не содержит отрицаний (остальные случаи можно рассмотреть аналогично) и, соответственно, входящие в нее переменные принимают значение 0.
Если же набор дизъюнкций выполним, то для любого j Є N„ найдется такое к Є N3, что истинная логическая переменная иг (или ее отрицание) входит в j-тую дизъюнкцию на fe-том месте. Выберем целую вершину z так, чтобы в блоках j-того столбца единица стояла в А;-той строке. Получим, что V? : fjizj) = 3, а значит, имеет место следующее утверждение:
Мы провели сведение задачи 3-SAT к задаче целочисленного программирования на многограннике Рт п Утверждение 2.1.2. Задача целочисленного программирования на многограннике Рт,п является NР-трудной.
Обозначим через РДП - выпуклую оболочку множества целых вершин многогранника Ртп:П, а через 3-SAT(m, п) - класс всех многогранников задачи 3-SAT для m переменных и п уравнений. Нетрудно заметить, что многогранник Р%п в некотором роде подобен классу 3-SAT(m, п), так как он позволяет решать задачу 3-SAT для любого набора дизъюнкций С: CUT in) М%СМпС Pm,n Э РДП 3-SAT(m, п). Многогранник Рто,п назовем релаксационным многогранником задачи 3-SAT.
Тот факт, что -Pm,n является релаксационным многогранником сразу для двух комбинаторно-оптимизационных задач представляется интересным, но не удивительным. Задачи о максимальном разрезе графа и 3-SAT являются JVP-полными и, соответственно, полиномиально сводятся друг к другу. Существование многогранника Рт,п лишь еще раз подтверждает этот известный результат.
Следовательно, для решения задачи 3-SAT не обязательно находить максимум целевой функции / на множестве целых вершин многогранника Рто,п- Достаточно проверить, достигается ли тахжЄрт f(x) в целой вершине. Это задача распознавания целочисленности.
Таким образом, для релаксационного многогранника задачи 3-SAT, в отличие от корневого полуметрического многогранника Мп, являющегося его гранью, не только задача целочисленного программирования, но и более простая задача распознавания целочисленности являются iVP-трудными (а, если представить задачу целочисленного программирования в форме распознавания, то и NР-полными).
Следует отметить, что многогранник РШ;П можно использовать не только при решении общей задачи 3-SAT, но и любых ее вариаций, достаточно построить соответствующую целевую функцию.
Например, рассмотрим задачу точная 3-выполнимостъ или 3-выполнимость при одном истинном литерале (l-in-3 SAT, X3SAT).
Условие. Задан набор С трехместных дизъюнкций вида с3 — а3У Ь3 У с3, где j Є Nn. Логические переменные a-jjbjjCj принимают свои значения из множества U = {иг,щ : г Є yVm}. Вопрос. Существует ли для множества U такой набор истинностных значений, при котором в каждой дизъюнкции из С найдется в точности 1 истинный и 2 ложных литерала?
Приведем некоторые свойства релаксационного многогранника задачи 3-SAT. Принципиальным отличием корневого полуметрического многогранника от разрезного и других многогранников комбинаторных задач является простота внешнего описания. Многогранник Рт,п также удовлетворяет этому условию и описывается полиномиальным числом ограничений.
"Утверждение 2.2.1. Общее число фасет многогранника Рт,п и задающих их линейных ограничений полиномиально по размерности пространства и не превосходит Ютп.
Действительно, число уравнений (7) в точности равно числу блоков в матрице координат: тп. Для каждой из т строк из блоков ровно п — 1 уравнений (8). Для каждого из п столбцов из блоков - 2(т — 1) ограничений (9). Наконец число неравенств (10) в точности равно размерности пространства: Qmn.
В предыдущем разделе было показано, что к задаче целочисленного программирования на многограннике Рто п сводятся iVP-нолная задача 3-SAT и различные ее вариации. Как следствие, множество целых вершин Z многогранника Рт п представляет большой интерес для изучения. В работах [13, 14] подробно описаны свойства графа многогранника Р,п = conv(Z). В частности, в них доказываются 3 следующих свойства:
Релаксации многогранника задачи 3-SAT
Первый раздел третьей главы посвящен построению релаксаций более высоких уровней для многогранника задачи 3-SAT, а также описанию и анализу свойств первой отличной от Рт,п релаксации. Рассмотрен вопрос о наличии общих нецелочисленных вершин у различных релаксаций.
Определим, следуя [39], релаксации более высоких уровней для многогранника задачи 3-SAT. Выберем натуральные s и t (s т, t п) и рассмотрим систему неравенств Q, задающую многогранник РД; обозначим через 0 число этих неравенств. Нетрудно проверить, что Vs Є Nm и Vt Є Nn многогранники РІД, Pljt и Р8д не имеют нецелых вершин и совпадают с Р , Pft и РД соответственно, а значит, и релаксации Р п, Р п и Р п будут совпадать с самим многогранником РШ.
Многогранник Рг - это первый релаксационный многогранник задачи 3-SAT, обладающий нецелочисленными вершинами. Причем, как и для корневого полуметрического многогранника, все вершины Рг,2 являются полуцелыми (все координаты принадлежат множеству {0, ,1}). С точностью до возможных перестановок строк и столбцов внутри блоков общий вид нецелых вершин Р2,2 приведен в Таблице 51. Здесь и далее в третьей главе все вычисления проведены с помощью программного продукта PORTA [63].
Найдем систему неравенств, определяющую многогранник P%fn. По построению многогранника имеем Р2 2 = P2Z2. Отметим, что для нахождения выпуклой оболочки целых вершин Р2]2 необходимо, но не достаточно отсечь все нецелые вершины многогранника, так как дополнительные фасеты при пересечении могут дать новые нецелочисленные вершины.
Отметим, что каждая из 3-х гипотез противоречит двум другим, и только одна из них верна. Если верна Гипотеза 3.1.3, то по аналогии с доказательством Теоремы 2.5.1 можно построить полиномиальный по трудоемкости алгоритм решения задачи распознавания целочисленности на многограннике Рт,п- Так как к этой задаче сводятся задача 3-SAT и ее модификации (Утверждение 2.1.3), прямым следствием Гипотезы 3.1.3 является равенство классов сложности Р и NP.
Гипотезы 3.1.4 и 3.1.5 ставят вопрос о наличии (или отсутствии) общих нецелых вершин у многогранников Рт п и РД;2„. Строго говоря, необходимое условие для нецелочисленных вершин Рт п (Теорема 3.3.2) не противоречит дополнительным ограничениям (21), определяющим многогранник Р%2п- В то же время для небольших значений тип была установлена Теорема 3.1.6. При т и п 4 многогранники Р 2п и Рт:П не имеют общих нецелочисленных вершин. Доказательство. Достаточно проверить, что все нецелые вершины многогранника 4,4 отсекаются дополнительными ограничениями (21) и не принадлежат многограннику Р 2п [63]. Теорема 3.1.6 доказана.
Во втором разделе третьей главы проводится построение последовательности релаксаций более высоких уровней Мп для разрезного многогранника, аналогично рассмотренной для многогранника задачи 3-SAT. Приведены полные описания первых нескольких релаксаций.
Определим, следуя [39], релаксации разрезного многогранника более высоких уровней. С этой целью выберем натуральное к {к п) и рассмотрим систему неравенств S, задающую многогранник Мк; обозначим через в число этих неравенств. Далее для каждого fc-элементного подмножества и — {щ,..., vk} множества N„ рассмотрим систему Sv, получающуюся из системы неравенств S заменой переменных xttJ, ytJ, zhJ и tttJ, соответственно, на xUt l/], y ,, , zUxt„} и tVuU]. Дополним систему (1)-(6) совокупностью всех G С указанных неравенств, а многогранник, который задается расширенной системой ограничений, обозначим через МПік- Таким образом, релаксации Мп к представляют собой последовательность вложенных друг в друга матрешкой многогранников:
3-однородные смешанные гиперграфы
Напомним, что гиперграф - это обобщённый вид графа, в котором ребром могут соединяться не только две вершины, но и любые подмножества вершин, -однородным называется такой гиперграф, каждое ребро которого соединяет ровно к вершин [15, 29].
Аналогично определим операцию инвертирования подмножества вершин гиперграфа G, так, что InvlJtk(G) = Inv Inv Inv G))).
Нетрудно убедиться, что Invt(InVj(G)) = InV](Invt(G)) и операция инвертирования подмножества вершин гиперграфа G не зависит от порядка инвертирования отдельных вершин.
Рассмотрим сужение задачи 3-выполнимость (3-SAT), а именно: задачу монотонная 3-выполнимостъ при различных литералах (monotone not-all-equal 3-SAT, MNAE 3-SAT) [43].
Условие. Заданы множество логических переменных U = {щ, ...,ип} и набор трехместных дизъюнкций С = {cj = ип V ип V и]3; j Є Nn}.
Вопрос. Существует ли для набора С такой выполняющий набор истинностных значений, что в каждой дизъюнкции из С найдется хотя бы один истинный и хотя бы один ложный литерал?
Легко проверяется, что индивидуальная задача Z Є MNAE 3-SAT предполагает ответ «нет» тогда и только тогда, когда связанный с ней гиперграф G(Z) принадлежит классу Gr, поэтому справедлива
Рассмотрим задачу следующего вида: «Для заданного 3 - однородного гиперграфа G = (V, Е) определить, можно ли так раскрасить вершины гиперграфа в два разных цвета, чтобы ни одно ребро не было монохромным (не содержало три вершины одного цвета)?». Эта задача известна как задача о 2-раскрашиваемости 3-однородного гиперграфа [43]. В то врям как для обычных графов задача 2-раскрашивания не представляет затруднений, для fc-однородных гиперграфов было установлено, что задача 2-раскрашивания является NP-полной для любого к 3 [55].
Множество 3-однородных гиперграфов G = (V, Е) является подмножеством множества 3-однородных смешанных гиперграфов G = (V,E,A). Нетрудно заметить, что на нем задача распознавания вида: «Верно ли, что гиперграф G не принадлежит классу G/?» эквивалентна задаче о 2-раскрашиваемости 3-однородного гиперграфа, достаточно сопоставить множества инвертированных и неинвертированных вершин двум различным цветам. Таким образом, рассматриваемая задача распознавания включает задачу о 2-раскрашиваемости 3-однородного гиперграфа в качестве своего частного случая и также является NP-полной.
Отсюда напрямую следует, что класс неинвертируемых гиперграфов не пуст, так как любой 3-однородный не 2-раскрашиваемый гиперграф (как и его произвольная инверсия) принадлежит классу Gj, в частности этому условию удовлетворяют [40, 50, 58]:
Отметим, что идея описывать свойства многогранников задач, через свойства ассоциированные гиперграфов не нова. Так, в некотором роде похожие построения для задачи о максимальном потоке в сети описаны в работе [45] Теорема 4.2.1 подсказывает направление для поиска точек релаксаций Мп в любом разложении которых в выпуклую комбинацию вершин М„і3 нет ни одной целой вершины. Достаточно построить такие точки Мп к, гиперграфы которых принадлежат классу неинвертируемых гиперграфов, который, как было показано выше, не пуст. 4.3 Свойства точек релаксаций Мп и Мп)5
Третий раздел четвертой главы посвящен построению конкретных точек многогранников Мпд и Мп$ в любом разложении которых по вершинам Мп3 нет ни одной целой вершины. Рассуждения будут опираться на Теорему 4.2.1 и класс неинвер-тируемых гиперграфов G/. Прежде всего, отметим следующее свойство релаксации МпЛ: Теорема 4.3.1. Для любого 3-однородного смешанного гиперграфа G рассматриваемого вида найдется такая точка и многогранника МП]4, что G = G(u). Доказательство. Из Теорем 4.2.1 и 4.3.1 следует, что выбрав любой неинверти-руемый гиперграф из класса Gj можно построить точку многогранника Мп в любом разложении которой в выпуклую комбинацию вершин многогранника Мп$ нет ни одной целой вершины.
Доказательство. Предположим противное, найдется такая точка v многогранника МП)5, гиперграф которой G(v) содержит некоторую инверсия полного 3-однородного гиперграфа на 5-ти вершинах. Легко проверить, что перенумеровав и инвертировав часть вершин гиперграфа G(v) и, соответственно, строк координатной матрицы точки v, можно построить точку w многогранника Мп$ подграфом гиперграфа G(w) которой на вершинах с первой по пятую является полный 3-однородный гиперграф. Рассмотрим координаты точки w, стоящие в первых пяти строках и столбцах и выпишем все неравенства (26), которые обращаются в равенства на этих координатах.
