Свойства вершин релаксаций разрезного многогранника

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

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

Общая постановка задачи дискретной оптимизации звучит следующим образом: задано конечное дискретное множество 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 1тг неэффективным. При этом первый не представляется возможным реализовать на практике даже при п = 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 году была решена задача коммивояжера для всех 24 978 городов Швеции [27], а текущий рекорд составляет 85 900 городов и известен как 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.

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

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

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

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

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

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

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

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

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

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

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

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

Во второй главе рассмотрение переходит к более общей релаксации разрезного многогранника Рт>&bdquo-, которая в то же время является релаксационным многогранником задачи 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 InstituteThe 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.