Свойства вершин релаксаций разрезного многогранника тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Николаев Андрей Валерьевич

СВОЙСТВА ВЕРШИН РЕЛАКСАЦИИ РАЗРЕЗНОГО МНОГОГРАННИКА

Специальность 01.01.09 - дискретная математика и математическая кибернетика

2 4 НОЯ 2011

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

Ярославль - 2011

005001902

Работа выполнена на кафедре дискретного анализа ФГОУ ВПО «Ярославский государственный университет им. П.Г. Демидова»

Научный руководитель - доктор физико-математических наук,

профессор Бондаренко Владимир Александрович

Официальные оппоненты: доктор физико-математических наук,

профессор Дольников Владимир Леонидович

Защита диссертации состоится «16» декабря 2011 года в 14 часов 10 минут на заседании диссертационного совета Д.212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу: 150008, г. Ярославль, ул. Союзная, 144, аудитория 426.

С диссертацией можно ознакомиться научной библиотеке Ярославского государственного университета им. П.Г. Демидова по адресу: 150003, г. Ярославль, Подушкина роща д. 1.

Автореферат разослан «_ ноября 2011 г.

кандидат физико-математических наук Гарбер Алексей Игоревич

Ведущая организация - Институт проблем управления им. В.А.

Трапезникова РАН

Ученый секретарь диссертационного совета

С.И. Яблокова

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

Актуальность темы исследования

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

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

Построением методов более эффективных, чем полный перебор, и определением причин труднорешаемости некоторых задач занимается теория сложности алгоритмов. В этом направлении был получен ряд фундаментальных результатов, в частности теория Кука-Карпа об ЫР-полных задачах.

Одним из подходов к решению задач комбинаторной оптимизации является так называемый «геометрический подход». В его основе лежит представление множества вариантов задачи X в виде множества точек эвклидова пространства Е" и допущении, что функция цели линейна (как правило, это выполнено). Таким образом, задачу комбинаторной оптимизации можно представить как оптимизацию линейной функции на некотором множестве точек в я-мерном пространстве:

/М = Сс<х) шах\ш1п, х & X.

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

заложенной в 1939 году JI. Канторовичем1. Так, Дж. Данциг, Р. Фалкерсон и С. Джонсон опубликовали в 1954 году свою знаменитую работу 2 по альтернативному подходу к решению задачи коммивояжера, используя новую геометрическую конструкцию: многогранник задачи коммивояжера. Семью годами ранее Данциг разработал симплекс-мстод3, который быстро стал основным аппаратом решения задач линейного программирования. На волне воодушевления от бесконечных приложений симплекс-метода, Данциг, Фалкерсон и Джонсон преобразовали задачу коммивояжера к задаче целочисленного линейного программирования и, применив симплекс-метод, решили ее для 49 столиц штатов США, что на тот момент было по-настоящему феноменальным результатом.

Следует отметить, что в строгом смысле симплекс-метод не является эффективным алгоритмом. Действительно, в 1972 году В. Кли и Д. Минти показали, что на незначительно скошенном единичном кубе (куб Кли-Минти) симплекс-метод работает по наихудшему сценарию и требует экспоненциального числа шагов4. Тем не менее, уже в 1978 году JI. Хачиян модифицировал метод эллипсоидов Шора для решения задачи линейного программирования, доказав, что время вычисления будет гарантированно меньше полиномиальной функции от размерности задачи и количества входных данных5. В дальнейшем были описаны и более эффективные алгоритмы решения задачи, в частности, алгоритм внутренней точки Кармаркара, однако, фундаментальность результата Хачияиа заключалась в доказательстве принципиальной полиномиальной разрешимости задачи линейного программирования.

Работы Хачияна и Кармаркара устранили первое препятствие на пути геометрического подхода к решению задач комбинаторной оптимизации. Теперь переход к задаче линейного программирования фактически предлагал эффективный алгоритм решения большинства известных комбинаторных задач.

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

' Канторович, Л.В. Математические методы организации и планирования производства. — ЛГУ. 1939. -56с.

2 Dantzig, G.B., Fulkerson, R, Johnson, S.M. Solution of a large-scale traveling salesman problem // Operations Research. Vol. 2. - 1954. - pp. 393-410

3 Dantzig, G.B. Programming in a linear structure//Econometrica. Vol. 17. -1949. - pp. 73-74.

4 Klee, V., Minty, G.J. How good is the simplex algorithm? // Inequalities. Vol. 3. - Academic Press Inc. 1972.-pp. 159-175.

5 Хачиян, Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМ и МФ. Т. 20, №1. - 1980.-С 51-69.

полупространств, задающих фасеты многогранника (внешнее описание). Задачи комбинаторной оптимизации сводятся к внутренней форме, а все эффективные алгоритмы описаны для внешней, между тем переход от вершин к фасетам является абсолютно нетривиальной задачей. Во-первых, она решена только для некоторых сравнительно «просто устроенных» классов комбинаторных многогранников, в то время как для большинства многогранников полного описания до сих пор не было построено. Во-вторых, зачастую многогранники задач имеют столь сложную структуру, что трудно даже принципиально говорить о возможном описании их фасет. Так, например, JI. Биллера и А. Сарангараджан доказали, что каждый 0/1 многогранник является гранью многогранника задачи коммивояжера6. В-третьих, даже если для некоторого многогранника комбинаторно-оптимизационной задачи построено полное внешнее описание, вероятнее всего оно содержит экспоненциально большое число неравенств и эффективность алгоритмов линейного программирования будет потеряна уже на входных данных.

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

Одним из наиболее ярких примеров характеристик такого рода служит плотность графа многогранника задачи. Напомним, что плотность графа или кликовое число графа равно наибольшему количеству попарно смежных вершин или числу вершин в наибольшей клике. В работах В.А. Бондаренко7 установлено, что плотность графа многогранника служит нижней границей временной трудоемкости задачи в широком классе алгоритмов прямого типа, основанных на линейных сравнениях. К таким алгоритмам в частности относятся алгоритмы сортировки, «жадный» алгоритм, метод ветвей и границ, метод динамического программирования, венгерский алгоритм и другие широко известные комбинаторные методы.

В основе идеи лежит разбиение пространства К" на конусы

6 Billera, L.J., Sarangarajan, А. All 0-1 polytopes аге traveling salesman polytopes. // Combinatorica. Vol. 16.-Springer Berlin. 1996.-pp. 175-188.

7 Бондаренко, В.А. Многогранники с высокой плотностью графа и полиномиальная разрешимость задач комбинаторной оптимизации //Автоматика и телемеханика. №4.-1993. — С. 21-26. Бондаренко, В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. — Ярославль: ЯрГУ, 1995,- 126с.

У КО) = г*.

хех

Каждому элементу х множества X (каждому варианту в задаче оптимизации) ставится в соответствие свой конус

К(х) = {ш: (ш, х) > (ш,у), Уу е X), образованный всеми целевыми векторами ы для которых функция f(t) = (ш, г) на множестве X достигает максимума (или минимума, если в определении множества поменять знак неравенства) в точности на элементе х.

В 1956 году в своей знаменитой работе8 Д. Гейл переоткрыл циклические многогранники, описанные за 50 лет до него К. Каратеодори9. Уже в Е4 циклические многогранники могут иметь как угодно много вершин, причем все они будут смежны. Конусное разбиение, построенное по такому многограннику, обладает тем свойством, что любые два конуса граничат друг с другом по (п — 1) -мерной грани. Алгоритм прямого типа, основанный на линейных сравнениях, отбрасывает часть конусов, деля пространства на два полупространства гиперплоскостью. В результате, для данного разбиения на каждом шаге может быть исключен только один конус, и полного перебора избежать принципиально невозможно.

Таким образом, плотность графа многогранника задачи в некотором роде отвечает на вопрос: «насколько сложна данная задача?». Действительно, для целого ряда известных труднорешаемых задач получена экспоненциальная нижняя оценка плотности графа многогранника, в то время как для полиномиально разрешимых задач установлены, соответственно, полиномиальные (а в некоторых случаях и линейные) верхние и нижние оценки плотности10.

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

8 Gale, D. Neighboring vertices on a convex polyhedron // Linear Inequalities and Related Systems. - Annals of Mathematics Studies. No. 38. - Princeton, New Jersey: Princeton University Press, 1956. - pp. 255-263.

9 Caratheodory, C. Ueber den Variabilitatsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen // Mathematische Annalen. Vol. 64. -1907. - pp. 95-115.

10 Бондаренко, B.A., Максименко, A.H. Геометрические конструкции и сложность в комбинаторной оптимизации. - М. : ЛКИ, 2008. - 184с.

называемые релаксационные многогранники задач, которые возникают, если в ограничениях комбинаторных задач целочисленным (дискретным) переменным разрешить принимать непрерывные значения. В частности к ним относятся рассмотренные в диссертации различные релаксации многогранника известной КР-полной задачи о максимальном разрезе графа, а также связанные с ними релаксации задачи 3-выполнимость булевых формул (3-8АТ).

Цель работы

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

Методы исследования

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

Научная новизна

В диссертации получены следующие новые результаты:

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

2. Установлено, что множество значений координат нецелочисленных вершин релаксационного многогранника задачи 3-8АТ неограниченно: знаменатели координат растут сверхполиномиально с увеличением размерности пространства.

3. Построено необходимое условие нсцелочисленности вершин релаксационного многогранника задачи 3-8АТ, позволяющее эффективно описывать вершины.

4. Получены линейные ограничения на целевые функции, при которых задачи целочисленного программирования и распознавания целочисленности полиномиально разрешимы.

5. Построены последовательности вложенных релаксаций Мпк и Р„*п многогранников задач о разрезе и 3-SAT. Обнаружены общие нецелочисленные вершины у различных релаксаций.

6. Установлена связь между классом гиперграфов особого рода и точками многогранника Мп 3, в разложении которых в выпуклые комбинации вершин нет целых. Построены точки многогранников МпЛ и MnS, в любом разложении которых в выпуклые комбинации вершин многогранника Mn 3 нет целых.

Теоретическая и практическая ценность

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

Апробация работы

Результаты работы докладывались на следующих научно-исследовательских семинарах и конференциях:

1. Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (Новосибирск. 2007 и 2008 гг.)

2. V Всероссийская научная конференция «Математическое моделирования и краевые задачи» ММ-2008. Самара, СамГТУ. 2008 г.

3. Научная конференция студентов и аспирантов факультета ИВТ. ЯрГУ 2008 г.

4. IV Международная научно-практическая конференция «Образование и наука в 21 веке». София. 2008 г.

5. Всероссийской научно-практической конференции с международным участием: «Информационные технологии и математическое моделирование» (Анжеро-Судженский филиал КемГУ 2008 и 2010 гг.)

6. Конференция «Математика. Информационные технологии. Образование. - МИТО-2008». ОГУ, Оренбург 2008 г.

7. Шестьдесят вторая региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь. Наука. Инновации - 2009». Ярославль, ЯГТУ 2009г.

8. Общероссийская электронная научная конференция «Актуальные вопросы современной науки и образования» (Красноярск 2009 и 2010 гг.)

9. XVI Международная конференция «Проблемы теоретической кибернетики». Нижний Новгород, 2011 г.

Публикации

По результатам исследования опубликовано 19 работ, в том числе 3 статьи в изданиях, рекомендованных ВАК РФ. Список публикаций приведен в конце автореферата.

Структура и объем работы

Диссертация состоит из введения, четырех глав, двух приложений и списка литературы. Полный объем диссертации - 138 страниц, список литературы содержит 69 наименований.

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

Во введении дается характеристика задач дискретной оптимизации, среди которых особо выделяется подкласс задач комбинаторной оптимизации. На примере задачи коммивояжера обуславливается невозможность применения наиболее простого алгоритма полного перебора. Кратко излагаются основные положения теории сложности вычислений. Приводится исторический обзор развития «геометрического подхода» к решению задач комбинаторной оптимизации. На основании полученных ранее результатов обосновывается интерес к изучению свойств релаксационных многогранников задач с высокой плотностью графа, но простым внешним описанием. Проводится обзор литературы и кратко излагается содержание работы.

Первая глава посвящена обзору свойств «корневого полуметрического» многогранника Мп £ К4"2, внешние ограничения которого имеют вид:

Хи+Уи + Ч] + к) = 1. 0)

хц + Уи - хк.} + Ук.г (2)

хи + 7-и = хи + Чи (3)

хи - */,!< к]= 1и< Уи - га< (4)

Уи = 41 = (5)

Хц > О, уи > О, ги > 0, > 0, (6)

где г',/, к, I независимо пробегают значения 1,...,п.

Рассматривается одна из основных ОТ-полных задач, а именно: задача о максимальном разрезе графа и строится многогранник задачи, известный как разрезной многогранник. Доказывается, что задача о максимальном разрезе сводится к задаче целочисленного программирования на корневом полуметрическом многограннике и, таким образом, Мп также является релаксационным многогранником задачи о разрезе, как впрочем, и ряда других.

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

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

1. Число фасет и задающих их линейных ограничений полиномиально по размерности пространства.

1. Число вершин многогранника Мп , в том числе целочисленных, экспоненциально.

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

4. Все вершины многогранника являются полуцелыми, их координаты

принадлежат множеству lj. Целые и нецелочисленные вершины полностью описаны.

Рассматривается решение двух оптимизационных задач на корневом полуметрическом многограннике: задачи целочисленного программирования (оптимизации линейной функции на множестве целых вершин) и задачи следующего вида: для заданной линейной целевой функции / требуется выяснить, достигается ли тах{/(ы): и 6 М) в целой вершине многогранника M (задача распознавания целочисленности).

В монографии В.Н. Шевченко11 высказывается следующая гипотеза о связи значения функции

Д&4) = шах|В|,

В5А

где В - произвольная квадратная подматрица матрицы А, с решением задачи целочисленного программирования на системе неравенств Ах < Ь. Гипотеза 1.5.2. Если для целочисленной матрицы А известно, что Д(Л) не превосходит фиксированного натурального числа d, то задача целочисленного программирования наАх<Ь полиномиально разрешима.

При d = 1 Гипотеза 1.5.2 превращается в широко известное утверждение о задаче целочисленного программирования на вполне унимодулярных матрицах.

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

' ' Шевченко, В.Н. Качественные вопросы целочисленного программирования. - М.: Физматлит, 1995. - 192с.

Теорема 1.5.3. Для корневых полуметрических многогранников Мп значение максимума миноров матрицы линейных ограничений растет экспоненциально по п (субэкспошнциально по размерности пространства):

Д„ > 2®.

Результат является косвенным подтверждением Гипотезы 1.5.2, а именно: Дп не ограничена и задача целочисленного программирования на многограннике М'-полна.

Объектом исследования во второй главе является многогранник Ртп С Е6тп. Описывающие его внешние ограничения имеют вид:

(7)

+ + ХЦ - Х1Л + хи + х1л> (8)

(9)

4;} о. (Ю)

где к е {1,2,3}, I е {1,2}, ¿,5 е {1,2.....6 {1,2.....п}.

Нетрудно заметить, что корневой полуметрический многогранник Мп изоморфен грани многогранника Рт,п • ^ частности его можно получить проведением 2тп гиперплоскостей вида х^ = 0, где 1 < I < т, 1 < / < п, 1 < I < 2.

Таким образом, многогранник Рт п также является релаксацией разрезного многогранника. Кроме того, в первом разделе приведено сведение другой известной ^-полной задачи: 3-выполнимость (З-ЭАТ) к задачам целочисленного программирования и распознавания целочисленности на Ртп. Соответственно, многогранник Ртп называется релаксационным многогранником задачи З-БАТ.

Основной целью исследования во второй главе является сравнительный анализ свойств релаксационного многогранника задачи 3-8АТ и корневого полуметрического многогранника. Во втором разделе приведены основные известные свойства граничного комплекса многогранника Рт п.

1. Число фасет и задающих их линейных ограничений полиномиально по размерности пространства.

2. Число вершин многогранника Ртп , в том числе целочисленных, экспоненциально.

3. Не все целочисленные вершины многогранника являются попарно смежными, однако многогранник Ртп сохраняет экспоненциальную плотность графа, которая превосходит шш{2т, 3"}.

Третий раздел посвящен изучению множества нецелочисленных вершин релаксационного многогранника задачи 3-SAT. В отличие от корневого полуметрического многогранника, все вершины которого полностью описаны, и координаты которых принимают свои значения только из множества jo,-^, 1 j, ситуация с многогранником fmn оказывается принципиально более сложной. Множество значений координат вершин не только не ограничено, но и растет сверхполиномиально с увеличением размерности многогранника. Следствием является принципиальная сложность построения полного описания всех нецелых вершин Ртп. В диссертации приведено частичное описание этого множества в виде необходимого условия для нецелочисленных вершин многогранника.

Основные результаты раздела сформулированы в виде двух теорем. Теорема 2.3.1. Выполняется неравенство:

Гтш(т,п}1

6(т,п)> 21 2 J, где 8(т,п) равно максимальному значению знаменателей координат вершин многогранника Рт л.

Теорема 2.3.2. Если точка является нецелочисленнои вершинои 7( , то найдутся такие i,j,k,q,r для которых:

jeNn,i,kenm,(i*k), q,r 6 {1,2,3} (q * г): x#>0.xtf> O.xtf+xtf = = О,

6-q-r,l щ 6-q-r,2 _ п 6-ч-гД . 6-g-r,2 _ n xi,j xl,j — u' xk,j xkJ —

Четвертый и пятый разделы посвящены эффективному решению оптимизационных задач на релаксационном многограннике задачи 3-SAT.

Задача целочисленного программирования на Ртп является NP-трудной, так как к ней сводится NP-полная задача 3-SAT (следует отметить, что прямым следствием Теоремы 2.3.1 является тот факт, что величина д(Ртп) - максимум миноров матрицы линейных неравенств, определяющих многогранник, не ограничена сверху). Соответственно интерес представляют возможные дополнительные условия на целевые функции для эффективного решения задачи целочисленного программирования на многограннике. Теорема 2.4.2. I. Если вектор с £ K6mn имеет вид:

V/ е N„,3a,.fi,.y, е {-1.1}, Vi е Мт:

то на многограннике Рт п линейная целевая функция f — (с,х) достигает максимума в целой вершине.

2. Если в ограничениях на вектор с все неравенства заменить на строгие, то среди вершин, на которых целевая функция f = (с, х) принимает максимальное значение, не будет ни одной нецеяочисленной.

Известно, что для релаксационного многогранника задачи 3-SAT задача распознавания целочисленности является NP-полной. В то же время для корневого полуметрического многогранника, изоморфного грани Ртп , установлена полиномиальная разрешимость задачи.

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

Введем вектор с е R6mn:

Vj е Nn,3a,b е {1,2,3} (а Ф b),Vi е Nm:

а,г , Ь.2 _ а,2 , ЬД

CU + ct,j ~ ci,l + сц • Соответствующую ему целевую функцию обозначим f(x) = (с, х). Теорема 2.5.1. Для класса многогранников Ртп и целевой функции fix) задача распознавания целочисленности является полиномиально разрешимой.

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

Многогранники Мп и Рт п являются релаксационными многогранниками задач о максимальном разрезе и 3-SAT соответственно. Выпуклые оболочки множеств их целых вершин и изоморфны многогранникам этих задач и описываются, по-видимому, сверхэкпоненциальным числом ограничений, которые до сих пор не были найдены в общем случае. Однако если разбить дополнительные ограничения на классы, то можно построить промежуточные релаксации X и Y , такие что QXC Ртп и М* с у с Мп , которые представляют значительный интерес для изучения.

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

Для многогранника Рт п определим, релаксации более высоких уровней. Выберем натуральные 5 и £ (ж < т, £ < п) и рассмотрим систему неравенств (?, задающую многогранник Р/г; обозначим через 0 число этих неравенств. Далее для каждого 5 — элементного подмножества V = {уг,множества Мт и каждого I- элементного подмножества ы = [сог,..., множества ГЯП рассмотрим систему получающуюся из системы неравенств (} заменой переменных на соответственно. Дополним систему (7)-(10)

совокупностью всех 0 ■ • указанных неравенств, а многогранник, который задается расширенной системой ограничений, обозначим как Р^п с рт п.

Многогранники Р1Д , Ри и Р5Л ( V* 6 и 6 ) не имеют нецелочисленных вершин и совпадают с Р?л, Р^ и РД соответственно, а, значит, и релаксации , Р^ и Р^'.п совпадают с самим многогранником рт,п- Таким образом - это первая отличная от Рт „ релаксация. Теорема 3.1.1. Многогранник Р^'Д задается системой (7)-(10) и дополнительными ограничениями вида:

41,}, /с, £: 1<Ц<т,1< / < п, Уа 6 {1,2}, Уб, с, й, е е {1,2,3} (ЬФс.й* е),

г6,а , гс,а , д.Г , а,Г в,/ л,а , *(,/ +ХЦ + + х1.1 1,1 +ХЦ + гЬ,а , с.а , д./ , а,а , е.а , М ,

где / = 3- а, д = В — Ь — с, д = 6 — й — е.

В общем случае, многогранники Р£*п представляют собой набор вложенных друг в друга релаксаций многогранника задачи З-БАТ:

3-5АТ(т, п) ~ РДП = с с с = />£ = = рт п. Если дополнительно принять 5 = С , то можно получить строгую последовательность вложений для релаксаций многогранника задачи З-вАТ. Теорема 3.1.2. Для любых 5 £ и {в М„ множества целых вершин многогранников и Рт п равны между собой.

Следствие из Теоремы 3.1.2. Для любых ЕМт и С, V Е Мп множества целых вершин многогранников Р^п и совпадают.

Ситуация с нецелыми вершинами релаксаций многогранника задачи З-БАТ значительно сложнее. Даже наиболее простой случай с вершинами Р%2п остается не проясненным. Только для небольших значений тип была установлена

Теорема 3.1.6. При т и п< 4 многогранники Р^2п и Рт п не имеют общих нецелочисленных вершин.

Вопрос с общими нецелыми вершинами Ртп и большей размерности остается открытым.

Относительно общих вершин промежуточных релаксаций все еще более запутано. Так в диссертации приведены точки из пространства К54, являющиеся общими нецелыми вершинами для многогранников Р^, Р^ и

гз,з -

Однако если зафиксировать п = 2 ситуация оказывается иной Теорема 3.1.7. Многогранники Р^ и Р^22 не имеют общих нецелых вершин, по меньшей мере, для всех т < 5.

Опираясь на это и Теорему 3.1.6 можно предположить, что многогранники 2 и Рп+г '2 не имеют совместных нецелочисленных вершин, однако это не так, и в диссертации приведены общие нецелые вершины для многогранников

5,2 И 5,2 •

Таким образом, несмотря на то, что нецелые вершины релаксаций Р^п были рассмотрены достаточно фрагментарно, принципиальная сложность их свойств хорошо видна из приведенных в разделе фактов и предполагает дальнейшее изучение.

Во втором разделе третьей главы проводится построение последовательности релаксаций более высоких уровней Мп к для разрезного многогранника, аналогично рассмотренной для многогранника задачи 3-8АТ:

СиТ(п) = Мп>п с Мпл.г £ - £ Мп,к с с МпЛ с МпЛ = М^ = Мп. Приведены полные описания первых нескольких релаксаций.

Многогранники М1 и М2 не имеет нецелочисленных вершин и совпадают с и М/ соответственно, а, значит, и релаксации Мп1 и Мп 2 будут совпадать с самим многогранником Мп. Таким образом Мп3 ~ это первая отличная от Мп релаксация.

Известно, что многогранник Мп<3 определяется системой (1)-(6) и дополнительными ограничениями вида:

ХЦ + си + Чк + кк + У],к + Щл £ 2, хи + к] + У1.к + Чк + х!,к + к" ^ 2, Уц + Ч] + Чк + кк + х),к + кк < 2, У 1,1 + ги + У'.к + Чк + У).к + Чк - 2< для каждой тройки I,), к, где 1 <1<}<к<п.

Введя новые обозначения для координат:

V _ „1Д Л, _ _ гд . _ 2.2

хи ~~ хи • У',1 ~ ¡.1 ' ' 1,у ' ьг,у ~ х!,у

можно получить альтернативное описание многогранника Мп 3.

15

Теорема 3.2.1. Многогранник МП;3 определяется системой (1)-(б) и дополнительными ограничениями вида:

, гVI , ла _ . /Й _ /И х < п

для каждой тройки индексов £,/',&, где 1 < I <]'< к <п, и всех векторов а е [1,2]"

Следует отметить, что многогранник Мп3 в некотором роде подобен корневому полуметрическому многограннику. Рассмотрим многогранник М* 6 К4л2+4Сп , определяемый системой (1)-(6) и дополнительными ограничениями

\/1,),к,р^,г (1 <1<р<)<ц<к<г<п): Уц + Чк + У],к + хц,к = 1-хц + У\.к + С;,к + У и л = г> 41 + Чк + х1,к + Чик ~ Ч] + Чк + Чк + к],к ~ 1-хи,к + У Ц,к + Ч!.к + 4>,к ~ 1' хЦ,к + Уц,к ~ х1д,к + У 1,ч,к' хЦ,к + 21.1,к ~ х1,),г + Ч).г' х1.1.к + Ч,],к ~ хр,),к +

Теорема 3.2.2. Многогранники М„ и Мп 3 равны.

Далее в третьей главе рассматриваются последующие релаксации разрезного многогранника.

Теорема 3.2.3. Многогранник Л/п4 определяется системой (1)-(6), (11) и дополнительными ограничениями вида:

ЛЦ т к,к "ГЛ(,(

Х1.1 ¡,к Х],1 к,1 - Vй)

для каждой четверки индексов 1,},к, I, где l<i<j<k<L<n, и всех векторов а 6 [1,2]п.

Теорема 3.2.4. а) Многогранник Мпк задается системой (1)-(б) и дополнительными ограничениями, среди которых присутствуют ограничения вида:

у,а»га"1 , , , _ av2.iv! _ <Ь,гА,г _ _ Oj.-i.Ovp

для каждого р-элементного подмножества V = ... множества Мп, для любого натурального р: (3 < р < к), и всех векторов а € [1,2]". Ь) Точка с координатами:

З-а.-.З-а, _ к-1 _

ХЦ ~ к • хц -и.

к-1 £ '

= 0,

<3ля «сг* (,/, г<)<? 1 < I <) < п, и для всех векторов а е [1,2]™ является вершиной многогранника Мп к.

Теорема 3.2.4 полностью описывает многогранники Мп3 и Мп4, но не произвольный Мпк , так уже релаксация содержит дополнительные линейные ограничения, не подпадающие под условия теоремы. Теорема 3.2.9. Многогранник Мп5 задается системой (1)-(б), (II), (12) и дополнительными ограничениями вида:

VI,у, к,1,р:1<1<)<к<1<р<п,Уа,Ье [1,2]":

Хи + + х*:,к + Х1.1 + хр,р х1,1 х1,к ХЦ Х1,р ~ ак,а, _ а,А1 _ ар,а, _ а,,ак ор.а* арД1 ].к ]Х ].Р Хк,1 хк,р Х1,р - 1>

7 (-Л'6' + + гЪк'Ьк 4- гЬ,'Ь' 4- гЬр,ЬЛ - у"^' УЬ''Ь'"

^ V £.£ у,;' Г Ar.iT + х1,1 + хр,р ) хц ~ х1,к ~ х1,1 ~~

1,р ],к ХЦ х],р кХ хк,р х1,р -

VI,/, к,1:1 < I < ]' < к < I < п, Vp £ ЛГ„\{/,/, А:, г}, с 6 [1,2]п:

хр,р + ХР,1 +хр.к +хр.1 )

_уС/'С( _ уСЬС1 _ уС1'С1- _ ГС*'С/ _ уС''С/ _ <- О

"Чу л1,(с У.Л х1,1 к,1 — ■5-

Относительно общих нецелочисленных вершин у различных релаксаций Мп к разрезного многогранника ситуация не менее сложная, чем для релаксаций многогранника задачи З-ЙАТ. Известно, что

Утверждение 3.2.10. Многогранник Мп3 и корневой полуметрический многогранник Мп не имеют общих нецелочисленных вершин.

Однако, уже для псцелочисленных вершин Мп 3 и Мп 4 вопрос остается открытым, несмотря на описание всех фасет МпЛ (Теорема 3.2.3). Полным перебором вершин установлена

Теорема 3.2.11. Многогранник Мп 3 и Мп4 не имеют общих нецелочисленных вершин, по меньшей мере, для всех п < 6.

Дня корневого полуметричсского многогранника известно, что задача распознавания целочисленности на нем полиномиально разрешима, что принципиально отличает его от других многогранников, в том числе подробно рассмотренного во второй главе релаксационного многогранника задачи 3-БАТ, для которого задача распознавания целочисленности №-пална. В основе этого

результата лежит следующее свойство первой отличной от Мп релаксации разрезного многогранника12:

Утверждение 4.1. Каждая точка многогранника Мп3 является выпуклой комбинацией вершин многогранника Мп, среди которых есть хотя бы одна целая.

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

Рассматривается множество 3-однородных смешанных гиперграфов вида С = (V, Е, А), где

• V - множество вершин, V —

• Е - множество неориентированных ребер, Е = (0',/, к)} £ йл х х

• А - множество ориентированных ребер, А = {((£,;), &)} 5 х К!„ х М„, где пара вершин (¿.у) - начало ребра, вершина к - конец ребра.

Вводится операцию инвертирования /-той вершины гиперграфа С = (У,Е,А) , которая преобразует все ребра, инцидентные этой вершине, следующим образом:

а .у.«-> (О'.ю.О, (а.«. О а №.

((.иЛ,к) -» ((¿, &),/).

Результатом операции инвертирования является новый 3-однородный смешанный гиперграф С' = /ти^б = (У,Е',А').

Аналогично определяется операция инвертирования подмножества

вершин гиперграфа С, так, что = /пи; (/т'Д/т^Сб))). Нетрудно

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

(/пУуСС)) = /пиД/пг^СС)).

Рассматривается класс С/ гиперграфов б? = (У,Е,А) , для которых множество неориентированных ребер Е не пусто и остается непустым при всех возможных инверсиях. Класс С/ называется классом неинвертируемых гиперграфов рассматриваемого вида. Для С/ известно

12 Бондаренго, В.А., Урываев, Б.В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика, - 2007, №6. - С. 18-23.

Теорема 4.1.1. Задача распознавания вида: «Верно ли, что гиперграф G не принадлежит классу G/?» является NP-полной.

К данной задаче сводится сужение задачи 3-SAT, а именно: монотонная 3-выполнимость при различных литералах (monotone not-all-equal 3-SAT). Кроме того, частный случай задачи распознавания принадлежности классу С, для гиперграфов G = (V, Е, 0) без ориентированных ребер эквивалентен известной задаче о 2-раскрашиваемости 3-однородного гиперграфа, которая также является NP-полной.

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

1) полный 3-однородный гиперграф на п вершинах, где п > 5;

2) плоскость Фано (7 вершин и 7 ребер);

3) аффинная плоскость 3-го порядка (9 вершин и 12 ребер) и многие другие.

В последующих разделах четвертой главы гиперграфы приведенного вида

используются для описания свойств точек релаксаций разрезного многогранника Mnt.

Каждой точке и многогранника Мп3 сопоставляется 3-однородный смешанный гиперграф рассматриваемого вида, который называется гиперграфом точки G (и), по следующим правилам:

1) V = Мп;

2) (i,j, k) е Е(и) тогда и только тогда, когда

Уц + + У;,к + ziik + yjk + z)л = 2;

3) ((с,/), /с) е А(и) тогда и только тогда, когда

УU + zi.i + Чк + кк + xi.k + tj,k = 2.

Каждому из дополнительных ограничений (11) соответствует фасета многогранника Мп 3 и ребро гиперграфа G (и) . Геометрический смысл гиперграфа G (и) заключается в том, что он показывает, каким из «новых» фасет Мп 3 принадлежит точка и.

Теорема 4.2.1. Если для некоторой точки и е Мп ?1 ее гиперграф G (il) принадлежит классу С/, то в любом разложении и в виде выпуклой комбинации вершин Мп з нет пи одной целой вершины.

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

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

Теорема 4.3.1. Для любого 3-однородного смешанного гиперграфа G рассматриваемого вида найдется такая точка и многогранника Мп4, что G = С (и).

Теорема 4.3.2. Для любых п > 5 найдутся точки многогранника Мп 4 , гиперграфы которых неивертируемы и в любом разложении которых в выпуклую комбинацию вершин многогранника Мп 3 нет ни одной целой.

Относительно следующей релаксации Мп5 все не так просто. Многогранник описывается значительно более сложными ограничениями (Теорема 3.2.9) и далеко не каждому 3-однородному смешанному гиперграфу G можно сопоставить такую точку и е Мп 5, что G(u) = G. В частности, имеет место

Теорема 4.3.3. Не существует ни одной точки многогранника AfnS, гиперграф которой содержит в качестве подграфа полный 3-однородный гиперграф на 5-ти вершинах или его произвольную инверсию.

В то же время для многогранника Мя5 имеет место Теорема 4.3.4. Для любого п > 19 S cyufecmeyem точка и 6 Mn S с мпА в любом разложении которой в виде выпуклой комбинации вершин Мп 2 нет ни одной целой вершины.

Вопрос с наличием подобных точек у релаксаций Мп 6 и далее остается открытым. Предположительно имеет место

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

В четвертом разделе четвертой главы проводится анализ основного утверждения главы - Теоремы 4.2.1. Рассматривается следующий вопрос: является ли данная теорема также и необходимым условием для отсутствия целых вершин в любом разложении точки многогранника М%3 в выпуклую комбинацию вершин. Устанавливается, что это не так, в том числе и для точек МпА . Доказывается более общее утверждение, которое является как достаточным, так и необходимым условием.

Теорема 4.4.1. В любом разложении точки и многогранника Мпг в виде выпуклой комбинации вершин Мп 3 нет ни одной целой вершины тогда и только тогда, когда точка и удовлетворяет следующим условиям Vu = 1пуи(и) (У S 3i,j, к 6 Nn: Ху = О ИЛИ yU + Z(j + у1Л + zUk + yJ¡k + zj¡k = 2.

Теорема 4.4.2. При любом п > 33 найдется точка многогранника МпЛ в любом разложении которой в виде выпуклой комбинации вершин Мп 3 нет ни одной целой вершины, но гиперграф которой не принадлежит классу неипвертируемых гиперграфов G¡.

Публикации автора в изданиях, рекомендованных ВАК РФ

1. Николаев, A.B. О нецелочисленных вершинах релаксаций многогранника задачи З-Выполнимость / A.B. Николаев И Моделирование и анализ информационных систем. - 2010. - Т. 17, № 2. - С. 99-111.

2. Николаев, A.B. Некоторые свойства релаксаций разрезного многогранника / В.А. Бондаренко, A.B. Николаев // .Ярославский педагогический всстник. - 2011. - Т.З (Естественные науки), №2. - С. 2329.

3. Николаев, A.B. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника / A.B. Николаев // Моделирование и анализ информационных систем. - 2011. - Т. 18, № 3. - С. 82-100.

Другие публикации автора

4. Николаев, A.B. Некоторые свойства релаксационного многогранника задачи 3-выполнимость / O.A. Дунаева, A.B. Николаев // Студенческие заметки по информатике и математике. Яросл. гос. университет. 2007. -С. 7-9.

5. Николаев, A.B. Свойства релаксационного многогранника задачи 3-выполкимость / O.A. Дунаева, A.B. Николаев // VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. Программа и тезисы докладов. Новосибирск. 2007. - С. 19.

6. Николаев, A.B. Некоторые свойства релаксационного многогранника задачи 3-выполнимость / O.A. Дунаева, A.B. Николаев // Математическое моделирование и краевые задачи. Труды пятой Всероссийской научной конференции с международным участием. 4.2: Моделирование и оптимизация динамических систем и систем с распределенными параметрами. Самара. СамГТУ. 2008. - С. 37-43.

7. Николаев, A.B. Ограничения на целевые функции для эффективного решения задачи целочисленного программирования на многограннике, ассоциированном с задачей 3-выполнимость / A.B. Николаев // Студенческие заметки по информатике и математике. Материалы

научной конференции студентов и аспирантов факультета ИВТ. -Ярославль. ЯрГУ. 2008. - Вып. 2. - С. 85-87.

8. Николаев, А.В. Об эффективном решении задачи целочисленного программирования на многограннике, связанном с задачей 3-выполнимость / Л.В. Николаев // Материалы IV международной научно-практической конференции, «Образование и наука в 21 веке». София. «Бял ГРАД-БГ» ООД. 2008. - С. 32-37.

9. Николаев, А.В. О двух многогранниках, связанных с задачей 3-выполнимость / А.В. Николаев // IX Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. Программа и тезисы докладов. Новосибирск. 2008. - С. 23-24.

Ю.Николаев, А.В. Необходимое условие для нецелочисленных вершин релаксационного многогранника задачи 3-выполнимость / А.В. Николаев // Информационные технологии и математическое моделирование (ИТММ-2008). Материалы VII Всероссийской научно-практической конференции с международным участием. Томск. Изд-во Том. ун-та, 2008.-Ч. 2.-С. 163-166.

П.Николаев, А.В. О двух многогранниках, связанных с задачей 3-выполнимость / А.В. Николаев // Математика. Информационные технологии. Образование. Сборник научных трудов. - Оренбург: ОГУ, 2008. -С.91-95.

12.Николаев, А.В. О нецелочисленных вершинах релаксационного многогранника задачи 3-выполнимость / А.В. Николаев // Современные проблемы математики и информатики. Сборник научных трудов молодых ученых, аспирантов и студентов. Яросл. гос. ун-т., Ярославль, 2008. Вып. 9. - С. 38-45.

13.Николаев, А.В. О релаксационном многограннике задачи 3-выполнимость / А.В. Николаев // Шестьдесят вторая региональная научно-техническая конференция студентов, магистрантов и аспирантов высших учебных заведений с международным участием «Молодежь. Наука. Инновации -2009». Тезисы докладов. Ярославль, ЯГТУ 2009. - С. 215-216.

14-Николаев, А.В. Об общих границах некоторых релаксаций корневого полуметрического многогранника / А.В. Николаев // Materialy V mezinarodni vedecko - prakticka conférence «Vedecky prumysl evropskeho kontinentu - 2009». - Dil 14. Technicke vedy. Vystavba a architektura. Matematika. Moderni informacni technologie: Praha. Publishing House «Education and Science» s.r.o. - 2009. -S.49-52.

15. Николаев, A.B. О граничных комплексах некоторых релаксаций разрезного многогранника / A.B. Николаев // Заметки по информатике и математике. Яросл. гос. ун-т. им. П.Г. Демидова. Ярославль, ЯрГУ, 2009. Вып. 2.-С. 96-102.

16.Николаев, A.B. О некоторых релаксациях корневого полуметрического многогранника и их граничных комплексах / A.B. Николаев // Актуальные вопросы современной науки и образования: Материалы L Общероссийской электронной научной конференции (декабрь, 2009 г.) -Красноярск: Издательство ООО «Научно-инновационный центр», 2010. -С. 909-917.

17.Николаев, A.B. О некоторых релаксациях разрезного многогранника / A.B. Николаев // Актуальные вопросы современной науки и образования: Материалы Общероссийской электронной научной конференции (сентябрь, 2010 г.). Выпуск 2. - Красноярск: Научно-инновационный центр, 2010.-С. 330-336.

18.Николаев, A.B. Релаксации разрезного многогранника и геометрический подход к задачам дискретной оптимизации / A.B. Николаев // Информационные технологии и математическое моделирование ИТММ-2010. Материалы IX Всероссийской научно-практической конференции с международным участием. Томск: Изд. Том. ун-та, 2010, 4.2. - С. 167172.

19.Николаев, A.B. О связи между классом гиперграфов специального вида и свойствами вершин релаксаций разрезного многогранника / В.А. Бондаренко, A.B. Николаев // Проблемы теоретической кибернетики. Материалы XVI Международной конференции. - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. - С. 58-62.

Подписано в печать 7.11.11. Формат 60x84/16. Бумага оф. Отпечатано на ризографе.

Тираж 100 экз. Заказ 35/11. Отдел оперативной полиграфии ЯрГУ 150000, Ярославль, ул. Советская ,14.

Введение

1 Корневой полуметрический многогранник

1.1 Разрезной многогранник.

1.2 Определение корневого полуметрического многохранника.

1.3 Некоторые основные свойства корневого полуметрического многогранника.

1.4 Корневой полуметрический многогранник как релаксация разрезного многогранника.

1.5 Минорные характеристики матрицы корневого полуметрического многогранника.

2 Релаксационный многогранник задачи З-БАТ

2.1 Задача 3-ВЫПОЛНИМОСТЬ и ее релаксационный многогранник.

2.2 Фасеты и целочисленные вершины.

2.3 Нецелочисленные вершины.

2.4 Задача целочисленного программирования на Рт,п.

2.5 Задача распознавания целочисленности

3 Последовательности релаксационных многогранников задач о разрезе и З-ЭАТ

3.1 Релаксации многогранника задачи З-ЭАТ.

3.2 Релаксации разрезного многогранника.

4 Гиперграфы специального вида и свойства вершин релаксаций разрезного многогранника ~

4.1 3-однородные смешанные гиперграфы

4.2 Гиперграфы точек многогранника Мп,з.

4.3 Свойства точек релаксаций Мп^ и Мп^.

4.4 О классе неинвертируемых гиперграфов.

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

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

Общая постановка задачи дискретной оптимизации звучит следующим образом: задано конечное дискретное множество X и функция /, определенная на этом множестве и принимающая действительные значения. Требуется найти такой элемент х* € X, для которого fix*) > f(x) для любого х 6 X (задача максимизации), или f{%) < f{x) (задача минимизации).

На первый взгляд, решение задачи дискретной оптимизация не представляет никакой математической трудности. Достаточно проверить все элементы множества X (перебрать все варианты) и выбрать оптимальный. В силу конечности и дискретности множества X это всегда возможно. Такой алгоритм носит название полного перебора и для некоторых простых задач, как, например, поиск наибольшего простого двухзначного числа, он вполне допустим. Однако, дискретные задачи часто имеют комбинаторную природу, ибо элементы множества X, среди которых ищут подходящие варианты, задаются комбинационно. Рассмотрим, для примера, широко известную и одну из наиболее популярных комбинаторно-оптимизационных задач: задачу коммивояжера [43].

Условие. Задано конечное множество С = {ci,c2,. •., Cm} «городов» и функция ¿(сг, с^) е Z+ каждой паре городов сг,с3 Е С сопоставляющая «расстояние между городами» (стоимость проезда или любую другую величину для оптимизации).

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

Данными для задачи коммивояжера считаются города и расстояния, а множество X возможных маршрутов возникает опосредованно. При этом происходит, так называемый «экспоненциальный взрыв», когда число вариантов растет неимоверно быстро. Так, задача коммивояжера на п городах предполагает возможных маршрутов, что при всего лишь 61 городе дает Щ- ~ 4.16 • 1081 обходов, что превосходит примерную оценку числа атомов в наблюдаемой Вселенной [66].

Более того, ситуация усугубляется непрямым определением множества X, когда поиск даже одного его элемента может вызвать значительное затруднение. Так, например, если рассмотреть задачу коммивояжера не на полном, а на произвольном графе (когда любые два города г и ] не обязательно соединены прямой дорогой), то нахождение хотя бы одного маршрута посещения каждого города ровно один раз -это задача по сложности сама не уступающая задаче коммивояжера (она известна как Гамильтонов цикл) [43].

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

В то же время среди задач комбинаторной оптимизации существуют свои аномалии. Например, рассмотрим задачу о минимальном остовном дереве.

Условие. Заданы неориентированный граф С = (V, Е) и некоторая функция С : Е —> каждому ребру е £ Е сопоставляющая неотрицательное целое число С(е), называемое весом ребра.

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

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

Общее количество остовных деревьев полного графа на п вершинах равно пп~2. что превосходит даже число гамильтоновых циклов в задаче коммивояжера. Однако, задача легко решается так называемым «жадным алгоритмом». Достаточно на каждом шаге выбирать лучшее (самое легкое / дешевое) ребро среди оставшихся, не образующее цикла с уже выбранными. На этом принципе основаны алгоритмы Прима и Краскала, решающие задачу о минимальном остовном дереве за 0(п2) действий. Кроме того можно выделить алгоритм Дийкстры нахождения кратчайшего пути в графе (также 0(п2) действий), алгоритм Форда-Фалкерсона вычисления максимального потока в сети (0(т2 • п) действий, где т - число дуг, п - число вершин) и ряд других.

В 1965 году Джек Эдмондс разработал метод решения задачи о максимальном паросочетании в графе [36], который сам автор изящно назвал «paths, trees, and flowers method», однако в литературе закрепилось более простое название: алгоритм Эдмондса. Эта статья получила большую популярность, не столько из-за самого метода, сколько благодаря предложению Эдмондса именовать алгоритмы, временную трудоемкость которых можно оценить сверху полиномом от длины входа, полиномиальными или «эффективными» (сам Эдмнондс также использовал термин «хорошие алгоритмы»).

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

Окончательно это разбиение было зафиксировано в утверждении, получившем название тезиса Кобхэма-Эдмондса: вычислительная задача может быть решена на некотором вычислительном устройстве только в том случае, если ее трудоемкость оценивается сверху полиномиальной функцией [32]. Следует отметить, что данное положение не бесспорно: алгоритм с трудоемкостью Ю100п считается эффективным, так как это линейная функция, а алгоритм с экспоненциальной сложностью 20 00001тг неэффективным. При этом первый не представляется возможным реализовать на практике даже при п = 1, в то время как трудоемкость второго и при п = 106 составляет всего лишь 1024 операции. Тем не менее, в общем случае отождествление эффективных алгоритмов с полиномиальными представляется верным и такое представление закрепилось.

Современную теорию сложности алгоритмов можно условно разделить на два направления исследования: практическое и фундаментально-теоретическое. С практической точки зрения рассматриваются такие вопросы как (на примере задачи коммивояжера) :

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

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

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

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

Прорывом в этом направлении стала появившаяся в 70-ые годы прошлого века теория Кука-Карпа о iVP-полных задачах.

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

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

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

Теория Кука-Карпа выделяет три основных класса задач распознавания: Р (polynomial), NP (non-deterministic polynomial) и N PC (non-deterministic polynomial complete, или ./VP-полные задачи). Позднее классификация задач в теории сложности была многократно расширена и дополнена, однако, она не являются объектом изучения в данной работе и в дальнейшем речь в основном пойдет о Р и NPC (а также классе ./VP-hard).

Класс Р образован совокупностью задач распознавания, для решения которых существуют полиномиальные алгоритмы по длине входа («хорошие алгоритмы» в терминологии Эдмондса), например, приведенная выше, задача о минимальном остов-ном дереве.

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

Вложенность Р С NP прямо следует из определения классов. Вопрос равенства Р = NP (или неравенства) является одним из основных вопросов современной математики и назван математическим институтом Клея одной из семи проблем тысячелетия [34].

Фундаментальным прорывом в работах Кука и Карпа было открытие еще одного класса сложности NPC. Задача называется iVP-полной (./VP-complete), если к ней можно свести любую другую задачу из класса NP за полиномиальное время. Первой доказанной NP-полной задачей стала задача о выполнимости булевых формул (satisfiability или SAT) [33]. Ричард Карп расширил список до 21 задачи [49], и в дальнейшем было показано, что подавляющее большинство известных труднорешае-мых задач распознавания входят в класс NPC. Исключениями являются, например, такие задачи как изоморфизм графов, факторизация целых чисел и дискретное логарифмирование (интересно, что именно две последних задачи получили широкое распространение в шифровании), для которых было показано [53], что в случае Р ф NP они не принадлежат ни Р ни NPC (и образуют класс NPI или iVP-intermediate).

Отметим, что оптимизационная задача коммивояжера входит в еще один класс сложности, так называемых, /VP-трудных задач (/VP-hard), состоящий из задач не уступающих по сложности iVP-полным задачам, но не входящих в класс NP (класс задач распознавания).

Таким образом, построив эффективный алгоритм решения произвольной /VP-полной задачи (например, задачи коммивояжера) можно перекинуть мостик на любую другую задачу распознавания и решить ее за достаточно быстрое (полиномиальное) время. Подобный вариант равенства классов сложности Р и NP перевернул бы картину современной математики и открыл безграничные области применения, скажем, положив конец всей современной криптографии. Более того, Стивен Кук в работе [34] показал, что при Р — NP компьютер сможет построить формальное доказательство абсолютно любой теоремы (разумной длины), так как формальное доказательство легко проверить за полиномиальное время. Однако, вопрос так и остается открытым.

Кроме того, по-прежнему не ясно чем труднорешаемые (на данный момент) задачи отличаются от нетруднорешаемых. Какие их свойства препятствуют построению эффективных алгоритмов этих задач. Одним из подходов, проливающих определенный свет на проблему, является так называемый «геометрический подход к задачам комбинаторной оптимизации». В основе лежит представление множества вариантов задачи X в виде множества точек эвклидова пространства Rn и допущении, что функция цели линейна (как правило, выполнено). Таким образом, задачу комбинаторной оптимизации можно представить как оптимизацию линейной функции на некотором множестве точек в n-мерном пространстве: f(x) = (с, х) —> min / max, х G X.

В данной форме задача комбинаторной оптимизации напоминает постановку классической задачи линейного программирования. Идея задействовать алгоритмы линейного программирования для решения сложных оптимизационных задач появилась еще на заре развития данной теории. Так Джордж Данциг, Рэй Фалкерсон и Се л мер Джонсон опубликовали в 1954 году свою знаменитую работу по альтернативному подходу к решению задачи коммивояжера [38], задействовав новую геометрическую конструкцию: многогранник задачи коммивояжера, первые исследования которого были проведены Хеллером и Куном [46, 52]. Семью годами ранее Данциг разработал симплекс-метод [37], который быстро стал основным аппаратом решения задач линейного программирования и был назван Джоном Нэшем в журнале Computing in Science and Engineering одним из 10 основных алгоритмов 20-го века I

59]. На волне воодушевления от бесконечных приложений симплекс-метода Данциг, Фалкерсон и Джонсон преобразовали задачу коммивояжера к задаче целочисленного линейного программирования и, применив симплекс-метод, решили задачу для 49 столиц штатов США (штат Гавайи был образован только в 1959 году), что на тот момент было феноменальным результатом. Напомним, что общее число маршрутов для 49 городов составляет ^ ^ 6.2 • Ю60, что не представляется возможным просчитать полным перебором даже на современных суперкомпьютерах.

В 1960 году Ленд и Дойг предложили оптимизированный алгоритм решения задачи целочисленного программирования, получивший название метода ветвей и границ 154]. С тех пор в этом направлении наблюдался заметный прогресс, так в 2004 году была решена задача коммивояжера для всех 24978 городов Швеции [27], а текущий рекорд составляет 85900 городов и известен как pla85900, это наибольший пример из библиотеки TSPLIB [26].

Окончательно геометрический подход к задачам комбинаторной оптимизации сложился в 60-ые годы прошлого века в работах Эдмондса, Форда и Фалкерсона, а также Хофмана [35, 41, 47], и получил название «polyhedral combinatorics» (или полиэдральная комбинаторика). Если множество вариантов X представить в виде множества точек эвклидова пространства М" и перейти к выпуклой оболочке conv(X), тогда min{(c, х) | х € X} = min{(c, х) | х G conv(X)}.

Выпуклая оболочка конечного множества X представляет собой выпуклый многогранник и правая часть равенства - это классическая постановка задачи линейного программирования: min fix) = (с, х) : Ах < Ь.

Одним из препятствий на пути развития идеи решения задач комбинаторной оптимизации алгоритмами линейного программирования стала трудоемкость симплекс-метода Данцига. В 1972 году Виктор Кли и Джордж Минти показали, что на незначительно скошенном единичном кубе (куб Кли-Минти) симплекс-метод работает по наихудшему сценарию и требует экспоненциального числа шагов [51]. Таким образом, с теоретической точки зрения, симплекс-метод потерял звание «эффективного алгоритма». Тем, не менее, уже в 1978 году Леонид Хачиян модифицировал метод эллипсоидов Шора для решения задачи линейного программирования [22], доказав, что время вычисления будет гарантированно меньше, чем полиномиальная функция размерности задачи и количества входных данных. Однако, степень полинома, которую он установил, оказалась слишком высокой для того, чтобы этот алгоритм можно было использовать при решении практических задач. На первый взгляд, здесь имеет место математический парадокс: полиномиальный, а значит, эффективный метод эллипсоидов на практике почти всегда проигрывает «неэффективному» симплекс-методу, кроме некоторых частных случаев. В действительности, это достаточно важный момент, так как речь идет о самом определении трудоемкости. В классическом смысле под трудоемкостью алгоритма понимают число действий (или время работы) в худшем случае. Это не лишено смысла, так как при «лучшем раскладе» и полный перебор может закончиться уже на первом проверенном варианте. И в таком понимании алгоритм Хачияна «эффективнее» симплекс метода, так как никогда не превратится в полный перебор. Однако симплекс-метод Данцига моментально выигрывает, если за трудоемкость принять время работы в среднем. Тем не менее, результат Хачияна имел фундаментальное значение, так как показал, что задача линейного программирования принадлежит сравнительно узкому классу Р полиномиально разрешимых задач. Развитием идеи стал описанный всего шестью годами позже в 1984 году алгоритм Кармаркара [48], эффективный не только теоретически, ■ но и практически.

Учитывая фундаментальный результат Хачияна и тот факт, что основоположником самой теории линейного программирования был другой выдающийся советский математик Леонид Канторович, опубликовавший основные ее положения еще в 1939 году [18], можно сказать, что данная теория была весьма востребована в Советском Союзе (хотя далеко и не сразу). Сам Канторович в своей нобелевской лекции в 1975 году объяснил это тем, что государственная программа развития Госплана фактически сводилась к тому, чтобы закодировать всю экономику СССР в виде огромной задачи линейного программирования, а потом решить ее и получить оптимальный план [19].

Работы Хачияна и Кармаркара устранили первое препятствие на пути геометрического подхода к решению задач комбинаторной оптимизации. Теперь переход к задаче линейного программирования фактически предлагал эффективный алгоритм решения практически любой комбинаторной задачи.

Тонкость, однако, заключается в том, что по теореме Вейля-Минковского произвольный выпуклый многогранник можно определить двумя эквивалентными способами: как выпуклую оболочку его вершин (внутреннее описание) или как систему неравенств, описывающую пересечение некоторых полупространств, задающих фасеты многогранника (внешнее описание). Задачи комбинаторной оптимизации сводятся к внутренней форме, а все эффективные алгоритмы описаны для внешней, между тем переход от вершин к фасетам является абсолютно нетривиальной задачей. Во-первых, она решена только для некоторых сравнительно «просто устроенных» классов комбинаторных многогранников, в то время как для большинства многогранников полного описания до сих пор не было построено. Во-вторых, зачастую многогранники задач имеют столь сложную структуру, что трудно даже принципиально говорить о возможном описании их фасет. Так, например, Л. Биллера и А.

Сарангаджан доказали, что каждый 0/1 многогранник является гранью многогранника задачи коммивояжера [30]. В-третьих, даже если для некоторого многогранника комбинаторно-оптимизационной задачи построено полное внешнее описание, вероятнее всего оно содержит экспоненциально большое число неравенств и эффективность алгоритмов линейного программирования будет потеряна уже на входных данных.

Следует отметить, что последнее замечание не столь безнадежно и экспоненциальный размер задачи не обязательно означает ее труднорешаемость. Так, Гретчел, Ловаш и Шрайвер показали, что трудоемкость метода эллипсоидов Хачияна зависит от числа переменных и размера коэффициентов, но не от числа уравнений [44]. Этот факт позволил им построить полиномиальные алгоритмы решения задач о вершинной упаковке для совершенного графа, задачи о пересечении матроидов и ряда других. Но и здесь есть подводные камни. Алгоритм Хачияна не зависит напрямую от числа неравенств, но очень чувствителен к коэффициентам в линейных ограничениях. Некоторое представление о возможной величине этих коэффициентов можно составить по следующей оценке Гюнтера Циглера для соей(с/) - наибольшего целого коэффициента в описании фасет «¿-мерного 0/1 многогранника [67]: соеЩ)< Л*

22d+o(d) — v ' — 2<i-l'

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

Одним из наиболее ярких примеров характеристик такого рода служит плотность графа многогранника задачи. Напомним, что плотность графа или кликовое число графа равно наибольшему количеству попарно смежных вершин или числу вершин в наибольшей клике. В работах В.А. Бондаренко [2, 3, 8] установлено, что плотность графа многогранника служит нижней границей временной трудоемкости задачи в широком классе алгоритмов прямого типа, основанных на линейных сравнениях. К таким алгоритмам в частности относятся алгоритмы сортировки, «жадный» алгоритм, метод ветвей и границ, метод динамического программирования, венгерский алгоритм и другие широко известные комбинаторные методы. В основе идеи лежит разбиение пространства Еп на конусы

У К(х) = мп. жеХ

Каждому элементу х множества X (каждому варианту в задаче оптимизации) ставится в соответствие свой конус образованный всеми целевыми векторами и для которых функция /(¿) = на множестве X достигает максимума (или минимума, если в определении множества поменять знак неравенства) в точности на элементе х.

В 1956 году в своей знаменитой работе [42] Дэвид Гейл переоткрыл циклические многогранники, описанные за 50 лет до него Константином Каратеодори [31]. Уже в М4 циклические многогранники могут иметь как угодно много вершин, причем все они будут смежны. Конусное разбиение, построенное по такому многограннику, обладает тем свойством, что любые два конуса граничат друг с другом по (п — 1)-мерной грани. Алгоритм прямого типа, основанный на линейных сравнениях, отбрасывает часть конусов, деля пространства на два полупространства гиперплоскостью. В результате, для данного разбиения на каждом шаге может быть исключен только один конус, и полного перебора избежать принципиально невозможно.

Следует отметить, что циклические многогранники не являются уникальными. Напротив, при больших размерностях данная «аномалия» становится скорее правилом. Так, известно, что выбрав случайным образом с равномерным распределением вероятностей к вершин единичного п-мерного куба (такая конструкция называется случайным 0/1 многогранником), с вероятностью получим многогранник, все вершины которого окажутся попарно смежными [8]. Соответственно, выбранные случайным образом 50000 вершин единичного 100-мерного куба образуют 2-смежностной многогранник с вероятностью превышающей 0,99.

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

К(х) = {и : (ш,х)> (и,у), УувХ} плотности графа многогранника [8, 20, 28], в то время как для полиномиально разрешимых задач установлены, соответственно, полиномиальные (а в некоторых случаях и линейные) верхние и нижние оценки плотности [1, 8, 21].

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

Данная работа посвящена изучению различных релаксаций многогранника задачи о максимальном разрезе графа. Также рассмотрены связанные с ними релаксационные многогранники другой известной NР-полной задачи 3-выполнимость. Объектами исследования, прежде всего, являются множества нецелочисленных вершин соответствующих многогранников, которые непременно появляются при переходе от многогранника задачи к его релаксациям.

Структурно диссертация разбита на 4 главы.

Первая глава посвящена обзору известных результатов, лежащих в основе данного исследования. Проводится построение разрезного многогранника СиТ{п) и релаксационного многогранника задачи о разрезе Мп, известного в литературе как корневой полу метрический многогранник. Представлены основные известные свойства многогранника Мп. Кроме того, установлен новый факт относительно сверхполиномиального по размерности пространства роста максимума миноров матрицы линейных ограничений корневого полуметрического многогранника.

Во второй главе рассмотрение переходит к более общей релаксации разрезного многогранника Рт>„, которая в то же время является релаксационным многогранником задачи 3-выполнимость (З-ЭАТ). Для этого многогранника устанавливаются новые свойства, и проводится их сравнительный анализ со свойствами корневого полуметрического многогранника, являющегося гранью Рт п. Также для релаксационного многогранника задачи З-ЭАТ рассмотрен вопрос о возможных ограничениях на целевые функции для эффективного решения задач целочисленного программирования и распознавания целочисленности.

В третьей главе проводится исследование релаксаций более высоких уровней и Р^п Для многогранников задач о разрезе и З-БАТ. Частично изучен вопрос о наличии общих нецелых вершин у различных релаксаций. Для некоторых конкретных релаксаций построено полное внешнее описание (приведены все фасеты).

В основе известного утверждения о полиномиальной разрешимости задачи распознавания целочисленности на корневом полуметрическом многограннике лежит тот факт, что любая точка релаксации Мп 3 представляет собой выпуклую комбинацию вершин Мп хотя бы одна из которых целая [5]. В четвертой главе рассмотрен вопрос о сохранении этого свойства при переходе к более сильным релаксациям. Доказано, что при достаточно больших п в многогранниках Мп,4 и Мп>5 имеются точки, в любом разложении которых по вершинам многогранника МП]3 нет ни одной целой вершины. Устанавливается связь между свойствами точек релаксаций Мп^ разрезного многогранника и классом гиперграфов специального вида.

1. Белов Ю. А. О плотности графа матроида // Модели исследования операций в вычислительных системах. — Ярославль: Яросл. гос. ун-т., 1985. — С. 95-100.

2. Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. — М.: ЛКИ, 2008. —184 с.

3. Бондаренко В. А. Многогранники с высокой плотностью графа и полиномиальная разрешимость задач комбинаторной оптимизации / / Автоматика и телемеханика. 1993. №4. С. 21-26.

4. Бондаренко В. А. О релаксационном многограннике варианта задачи 3-выполнимость // Международная конференция „ Математика, кибернетика, информатика", посвященная памяти профессора А.Ю. Левина. Сборник тезисов конференции. — Ярославль, 2008.

5. Бондаренко В. А., Урываев Б. В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика, —2007 №6. — С. 18-23.

6. Бондаренко В. А. Об одном классе многогранников и их использовании в комбинаторной оптимизации // ДАН СССР. 1993. Т. 328, №3. С. 303-304.

7. Бондаренко В. А. Об одном комбинаторном многограннике // Моделирование и анализ вычислительных систем. Сб. науч. тр. — Ярославль: Яросл. гос. ун-т., 1987.-С. 133-134.

8. Бондаренко В. А. Полиэдральные графы и сложность в комбинаторной оптимизации. — Ярославль: ЯрГУ, 1995. — 126 с.

9. Босс В. Лекции по математике. Том 10. Перебор и эффективные алгоритмы. — М.: ЛКИ, 2008.-216 с.

10. Веселое СИ., Чирков А. Ю. О задаче целочисленного программирования с би-модулярной матрицей.Комбинаторно-алгебраические и вероятностные методы и их применение. — Горький, 1990.-С. 107-110.

11. Гришу хин В П. Субмодулярные задачи, алгоритмы их решения и смежные вопросы / В.П. Гришухин, Б.А. Папернов. —М., 1982, —66 с. (Препринт / ЦЭМИ АН СССР).

12. Дунаева О. А., Николаев А. В. Некоторые свойства релаксационного многогранника задачи 3-выполнимость // Студенческие заметки по информатике и математике. Яросл. гос. ун-т. — Ярославль, 2007. — С. 7-9.

13. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. —М.: Наука, 1990.— 384 с.

14. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. — М.: Наука, 1981. —344 с.

15. Ильичев А П., Шевченко В. Н. О крайних точках многогранников многоиндексных транспортных задач. // Комбинаторно-алгебраические методы в прикладной математике. — Горький: Изд-во ГГУ, 1981. — С. 66 72.

16. Канторович Л. В. Математические методы организации и планирования производства. — ЛГУ. 1939. —56 с.

17. Канторович В. Л., Кутателадзе С. С., Фет Я. И. Леонид Витальевич Канторович: человек и ученый. В 2 т. // Т. 1. Новосибирск: Изд-во СО РАН. Филиал «Гео» 2002. —542 с.

18. Максименко А. Н. Сводимость задач дискретной оптимизации и соотношение плотностей их полиэральных графов. // Современные проблемы математики и информатики: Сб. науч. трудов. Вып. 4 —Ярославль: ЯрГУ. 2001. —С. 157-161.

19. Максименко А. Н. Нижняя оценка плотности графа многогранника задачи о па-росочетаниях // Моделирование и анализ информационных систем. — Ярославль: ЯрГУ. Т. 10 №. 2. 2003.-С. 3-10.

20. Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // ЖВМ и МФ. Т. 20, №1.-1980.-С. 51-69.

21. Шевченко В Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. — 192 с.

22. Шевченко В. Н., Ильичев А. П. О минорах и перманентах некоторых (0,1)-матриц // Дискретная математика, —1991, Т. 3, №2, —С. 96-102.

23. Allender Е., Bauland М., Immerman N., Schnoor Н., Vollmer Н. The Complexity of Satisfiability Problems: Refining Schaefer's Theorem // Journal of Computer and System Sciences V. 75 I. 4. Elsevier. — 2009. pp. 245-254.

24. Applegate D. L., Bixby R. E., Chvatal V., Cook W. J., Espinoza D. G., Goycoolea M., Helsgaun K. Certification of an optimal TSP tour through 85,900 cities // Operations Research Letters. Vol. 37, Issue 1, —Elsevier. 2009. —pp. 11—15.

25. Applegate D. L., Bixby R. E., Chvatal V., Cook W. J. The traveling salesman problem: a computational study // Princeton University Press, 2006 — 593 p.

26. Barahona F., Mahjoub A. R. On the cut polytope // Mathematical programming Vol. 36, No. 2. 1986-pp. 157-173

27. Berge С. Hypergraphs. Combinatorics of finite sets. — North-Holland Mathematical Library, v. 45. Amsterdam, North-Holland Publishing Co. 1989. —287 p.

28. Billera L. J., Sarangarajan A. All 0-1 polytopes are traveling salesman polytopes. // Combinatorica. Vol. 16, —Springer Berlin. 1996. —pp. 175—188.

29. Caratheodory C. Ueber den Variabilitatsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen // Mathematische Annalen. Vol. 64.— 1907.— pp. 95-115.

30. Cobham A. The intrinsic computational difficulty of functions // Proc. Logic, Methodology, and Philosophy of Science II. North Holland —1965.— pp. 24—30.

31. Cook S. The Complexity of Theorem Proving Procedures. // Proceedings of the third annual ACM symposium on Theory of computing. — 1971. — pp. 151—158.

32. Cook S. The P versus NP problem. //Clay Mathematical Institute; The Millennium Prize Problem. 2000.

33. Edmonds J. R. Maximum matching and a polyhedron with 0,1 vertices. // Journal of Research. National Bureau of Standards. Section B. Mathematical Sciences. Vol. 69 —National Bureau of Standards, Washington D.C., USA. 1965. —pp. 125-130.

34. Edmonds J. R. Paths, trees, and flowers. // The Canadian Journal of Mathematics. Vol. 17 —Canadian Mathematical Society. 1965. pp. 449-467.

35. Dantzig G. B. Programming in a linear structure // Econometrica. Vol. 17. —1949. — pp. 73-74.

36. Dantzig G. В., Fulkerson D. R., Johnson S. M. Solution of a large-scale traveling salesman problem // Operations Research. Vol. 2, No. 4.— 1954.— pp. 393-410.

37. Deza M. M., Laurent M. Geometry of Cuts and Metrics (Algorithms and Combinatorics). — Springer. 1997, — 599 c.Имеется русский перевод: Деза М. М., Лоран М. Геометрия разрезов и метрик. — М.: МЦНМО, 2001.-736 с.

38. Dinur /., Regev О., Smyth С. The Hardness of 3-Uniform Hypergraph Coloring // FOCS '02 Proceedings of the 43rd Symposium on Foundations of Computer Science — IEEE Computer Society Washington, DC.— 2002. pp. 23-32.

39. FordL.R., Fulkerson D. R. Flows in networks. // Prinston University Press. Prinston N.J., USA. 1962.-208 p.

40. Groetschel M., Lovasz L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization // Combinatorica. Vol. 1, No. 2. — Springer Berlin. 1984. — pp. 169—197.

41. Groetschel M., Lovasz L., Schrijver A. Geometric Algorithms and Combinatorial Optimization // Springer-Verlag Berlin Heidelberg, 1988.— 564 p.

42. Heller I. The travelling salesman's problem: part 1 basic facts. Research Report // George Washington University Logistics Reserch Project. 1954.— 88 p.

43. Hoffman A. J. Some recent applications of the theory of linear inequalities of extrenal combinatorial analysis. // Proceedings of Symposia in Applied Mathematics, Vol. 10.—American Mathematical Society, Providence, R.I., USA. 1960.— pp. 113-127.

44. Karmarkar N. A New Polynomial Time Algorithm for Linear Programming. // Combinatorica. Vol. 4, No. 4.— Springer Berlin. 1984.— pp. 373—195.

45. KeevashP., Sudakov В. The Turan Number Of The Fano Plane // Journal Combinatorica. V. 25. I. 5.— Springer-Verlag New York, Inc.— 2005. pp. 561-574.

46. Klee V., Minty G. J. How good is the simplex algorithm? 11 Inequalities. Vol. 3.— Academic Press Inc. 1972. —pp. 159—175.

47. Kuhn H. W. On certain convex polyhedra // Bulletin of the American Mathematical Society. Vol. 61. -1955.-pp. 557-558.

48. Ladner R. E. On the Structure of Polynomial Time Reducibility // Journal of the ACM (JACM). Vol. 22 Issue l.-ACM New York, NY, USA. 1975.-pp. 155-171.

49. Land A. H., DoigA.G. An automatic method of solving discrete programming problems // Econometrica. Vol. 28, No. 3. —1960, —pp. 497-520.

50. LovaszL. Coverings and colorings of hypergraphs. // Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing. (Florida Atlantic Univ., Boca Raton, Fla., 1973), 1973 —pp. 3-12.

51. Maple 15, Waterloo Maple Inc., Waterloo, Ontario, Canada, http: / / www.maplesoft.com.

52. MATLAB R2011a, The MathWorks, Inc., Natick, Massachusetts, United States, http: / / www.mathworks.com.

53. Molloy M., Reed В. Near Optimal List Colourings // Proceedings of the Ninth International Conference "Random Structures and Algorithms". V. 17, I. 3-4, 2000.— pp. 376-402.

54. Nash J. C. The (Dantzig) Simplex Method for Linear Programming // Computing in Science and Engineering. Vol. 2, No. 1, —ACM New York, NY, USA. 2000. —pp. 29-31.

55. Padberg M. V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. V. 45. — 1989.— pp. 139-172.

56. Papadimitriou С. Н. Yannakakis М. Optimization, approximation and complexity classes // Journal of Computer and System Sciences. Vol. 43, No. 3 —Elsevier Inc., 1991.-pp. 425-440.

57. PORTA: POlyhedron Representation Transformation Algorithm 1.4.0. Thomas Christof, Andreas Loebel. The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, http: / / www.zib.de / Optimization/Software/Porta/

58. Schaefer T. J. The complexity of satisfiability problems // Proc. 10th Ann. ACM Symp. on Theory of Computing. — New York: Association for Computing Machinery, 1978.-pp. 216-226.

59. Veselov SI., Chirkov A. J. Integer program with bimodular matrix. Discrete Optimization. V. 6. —2009. pp. 220-222.

60. The Wilkinson Microwave Anisotropy Probe (WMAP) NASA // http://wmap.gsfc.nasa.gov/

61. Ziegler G. M. Lectures on 0-1 polytopes // Polytopes Combinatorics and Computation (G. Kalai and G.M. Ziegler, eds.), DMV Seminars Series. — Birkh"auser Basel. 2000.-45 p.

62. Ziegler G. M. Lectures on polytopes 11 Volume 152 of Graduate texts in mathematics — Springer Science, 2006 — 373 p.

63. Zuckerman D. On Unapproximable Versions of NP-Complete Problems // SIAM Journal on Computing. Vol. 25, Issue 6 —Society for Industrial and Applied Mathematics Philadelphia, PA, USA 1996.—pp. 1293-1304.