Графы многогранников и сводимость задач комбинаторной оптимизации тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Максименко, Александр Николаевич

• Максименко, Александр Николаевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Максименко, Александр Николаевич

Введение

1. Сложность в комбинаторной оптимизации

1.1. Некоторые сведения из теории сводимости задач.

1.2. Многогранники задач.

2. Конусное разбиение и аффинная сводимость

2.1. Конусное разбиение.

2.2. Аффинная сводимость

3. Труднорешаемые задачи

3.1. Задача КЛИКА

3.2. Задача 2-ВЫПОЛНИМОСТЬ.

3.3. Задача РАЗРЕЗ.

3.4. Задача ТРЕХМЕРНОЕ СОЧЕТАНИЕ.

3.5. Задачи РЮКЗАК и РАЗБИЕНИЕ

3.6. Задача КОММИВОЯЖЕР.

3.6.1. Задача гамильтонов контур.

3.6.2. Задача гамильтонов цикл.

3.6.3. Задача коммивояжера с условием "неравенство треугольника".

3.7. Задача ДЛИННЕЙШИЙ ПУТЬ.

4. Полиномиально разрешимые задачи

4.1. Задача о кратчайшем пути

4.2. Задачи о паросочетаниях.

Введение диссертации (часть автореферата) на тему «Графы многогранников и сводимость задач комбинаторной оптимизации»

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

Сформулируем условие задачи дискретной оптимизации следующим образом. Задано конечное множество X и функция с : X —> Л, ставящая в соответствие каждому элементу х множества X некоторое число с{х). Требуется найти такой элемент х* € X, на котором данная функция принимает максимальное (или минимальное) значение, то есть для всех х 6 X выполнено с(х*) > с(я) (или с(х*) < с(х)).

Среди множества всех задач дискретной оптимизации особо выделяются задачи комбинаторной оптимизации. Их отличие проявляется в комбинаторном характере множества X. Следуя совету И. Ньютона "при изучении наук примеры полезнее правил", рассмотрим классический пример — задачу о кратчайшем пути. Наиболее простая ее формулировка выглядит так. Дано: множество из п городов, среди которых выделены два, и расстояния между городами. Требуется найти кратчайший путь между выделенными городами. (Предполагается, что кратчайший путь может проходить через несколько городов.) В этой задаче X — это множество всех возможных маршрутов. Комбинаторный характер множества X проявляется, в частности, в экспоненциальном росте числа |XJ всех допустимых решений при росте размерности задачи. Так, для задачи о кратчайшем пути п—2

Х| = (п — 2)! или5 приближенно, к=0 п- 2)! < |Х| < е(п - 2)1, где е = 2,71828.

И уже для 20 городов число анализируемых маршрутов превышает 1016. Именно поэтому особое значение имеет проблема поиска алгоритмов, существенно более эффективных, чем полный перебор вариантов. К сожалению, число известных эффективных алгоритмов можно пересчитать по пальцам. В частности, для решения рассматриваемой задачи при естественном предположении о неотрицательности расстояний между городами можно воспользоваться алгоритмом Мура-Дейкстры [33,52], или алгоритмом Флойда-Уоршелла [33], каждый из которых имеет полиномиальную трудоемкость. В то же время для большинства известных задач комбинаторной оптимизации эффективные алгоритмы до сих пор не найдены. Примером труднорешаемой задачи может служить все та же задача о кратчайшем пути, в которой расстояния могут принимать отрицательные значения. (Такая задача возникает, если под расстояниями понимать средства, затрачиваемые на передвижение, и предполагать, что передвижение из одного города в другой может быть прибыльным.) Приведенный пример позволяет оценить, насколько порой бывает трудно определить, является ли данная задача труднорешаемой, или же для нее можно построить эффективный алгоритм. Одним из аспектов этой проблемы является вопрос о том, какие свойства той или иной задачи характеризуют ее как труднорешаемую. К настоящему времени сформировались два подхода к поиску ответов на этот вопрос.

Первый (в хронологическом порядке) подход основан на теории эффективной (полиномиальной) сводимости задач распознавания свойств, развитой в работах С. Кука, Р. Карпа, JI. Левина (см. монографию Гэри и Джонсона [13]). Эта теория применима в первую очередь для класса NP всех переборных задач. В их число входят, в частности, и такие задачи распознавания, которые можно сформулировать как "упрощенный" вариант задач комбинаторной оптимизации. А именно, в условие задачи оптимизации вводится некоторое, наперед заданное число С, а цель задачи распознавания заключается в ответе на вопрос: верно ли, что найдется такой элемент х € X, для которого с(х) > С (или с(х) < С для задачи на минимум). Основным достижением этой теории стало открытие Куком [22] так называемых АГР-полных задач, которые в определенном смысле являются самыми сложными в классе NP. Примером здесь может служить задача о кратчайшем пути в варианте распознавания, при условии, что расстояния между городами могут принимать и отрицательные значения: Существует ли такой путь между двумя выделенными городами, длина которого не превышала бы заданного числа С? В результате многочисленных безуспешных попыток поиска эффективных алгоритмов решения таких задач сформировалась гипотеза об их труднорешаемости. И, согласно этой гипотезе, любую задачу, частным случаем которой является iVP-полная, принято считать трудноре-шаемой. Соответственно, если удается показать, что некоторая задача распознавания, допускающая указанную выше формулировку, является труднорешаемой, то и соответствующая оптимизационная задача признается труднорешаемой. В заключение отметим, что список задач, труднорешаемость которых доказана, постоянно пополняется и в настоящее время содержит тысячи задач.

Другой подход к решению поставленной проблемы основан на изучении комбинаторно-геометрических свойств задач и геометрической интерпретации алгоритмов. Первые исследования (см. напр. работу Гей-ла [10]) в этом направлении основаны на представлении множества X допустимых решений как множества точек в вещественном евклидовом пространстве Rm и на предположении, которое обычно выполнено, что функция цели с(х) является линейной: с(х) = (с, х), где с € Rm. Такая интерпретация позволяет ввести понятие многогранника М(Х) задачи X, представляющего собой выпуклую оболочку convX. Дальнейшие исследования прежде всего связаны с изучением различных комбинаторных характеристик граничного комплекса (множества всех граней) многогранников задач и использованием этих характеристик в качестве оценок сложности соответствующих задач в тех или иных классах алгоритмов.

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

Отметим некоторые основные особенности обоих подходов. Заметим, что теория сводимости лишь дает способ сравнения задач по их сложности и указывает "самые сложные" задачи, но ничего не говорит о причине их труднорешаемости. В то же время ее преимуществом является относительная простота. Преимуществом же геометрического подхода является возможность вычисления конкретных числовых характеристик сложности задач. Недостаток его состоит в том, что такие вычисления обычно сопряжены с серьезными трудностями. Так, например, Папади-митриу [61] показал, что для многогранника задачи коммивояжера проблема распознавания смежности двух произвольно выбранных вершин является ЛГР-полной.

Особо выделим следующую, объединяющую указанные подходы особенность. Как правило, изучаемая комбинаторно-геометрическая характеристика признается адекватной (подходящей), если она отвечает современным представлениям о сложности задач. Соответственно, не вызывает удивления тот факт, что для всех признанно труднорешаемых задач, многогранники которых были изучены, получены экспоненциальные нижние оценки плотности полиэдральных графов (см. работы Белошевского [4], Бондаренко [6,9], Грешнева [И], Максименко [28,30], Симанчёва [35], Барахона и Маджуб [42]). В то же время для графов многогранников полиномиально разрешимых задач установлены полиномиальные (а для некоторых задач линейные) верхние и нижние оценки плотности (см. работы Белова [1,2], Бондаренко [5,8,9] и Шуниковой [7], Максименко [26,27]). Это наталкивает на мысль о том, что между теорией сводимости задач и исследованиями комбинаторных характеристик: их многогранников существует некоторая взаимосвязь. Выявление этой взаимосвязи позволило бы объединить указанные подходы в единую теорию и подтвердило бы гипотезу о том, что "адекватные" комбинаторные характеристики многогранников труднорешаемых задач экспоненциальны.

В настоящей работе изучается основа этой взаимосвязи. Ее установление ведется с двух направлений. С одной стороны, при изучении алгоритмов сведения задач комбинаторной оптимизации обнаруживается следующий любопытный факт. Если задача X сводится к задаче У, то, как правило, пространство исходных данных первой задачи аффин-но отображается в, соответственно, аффинное подмножество исходных данных второй задачи. Так появляется новое понятие аффинной сводимости задач комбинаторной оптимизации.

С другой стороны, исследуются свойства относительно мало изученной геометрической конструкции — конусного разбиения пространства исходных данных задачи. Отметим, что это понятие было использовано Бондаренко [5,6] при установлении взаимосвязи между плотностью графа многогранника и сложностью соответствующей задачи. Проявление интереса к исследованию свойств этой геометрической конструкции прежде всего связано с известным фактом о том, что конусное разбиение — двойственная к многограннику задачи конструкция. Оказывается, конусное разбиение является более гибким и мощным инструментом для исследования свойств задач, чем их многогранники. Так, с помощью конусного разбиения можно изучать комбинаторно-геометрические характеристики сложности для частных случаев задач, в то время как свойства многогранника характеризуют только общую задачу. Впервые это было обнаружено в работе [28] при исследовании классической задачи о кратчайшем пути, в которой, как известно, накладываются ограничения неотрицательности расстояний.

Далее, на основании изложенных фактов делается вывод о том, что при аффинном сведении задачи X к задаче Y конусное разбиение множества исходных данных первой задачи аффинно преобразуется в некоторую часть конусного разбиения множества исходных данных второй задачи. При детальном изучении этого явления обнаруживается, что при аффинном сведении задач граф многогранника М(Х) первой задачи оказывается изоморфным некоторому подграфу графа многогранника M(Y) второй задачи. Таким образом доказывается гипотеза о том, что граф многогранника "более сложной" задачи конструктивно сложнее графа многогранника "простой" задачи. В частности, следствием этого утверждения является соответствующее соотношение плотностей р(Х) и p(Y) графов многогранников задач: р(Х) < p(Y).

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

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

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

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

В третьей, наиболее емкой главе приводятся многочисленные "экспериментальные данные", подтверждающие работоспособность предлагаемой теории. Глава начинается с непосредственного изучения свойств многогранника "основной" задачи — оптимизационной задачи КЛИКА. Доказывается, что плотность графа этого многогранника совпадает с числом вершин и равна 2", где п — размерность задачи.

Дальнейшее развитие теории аффинной сводимости происходит по классическому сценарию. Конструируется алгоритм сведения "первой" задачи к "еще не изученной" задаче и доказывается, что он удовлетворяет условиям аффинности. Таким образом пополняется список задач с экспоненциальной плотностью полиэдрального графа. Процесс пополнения этого списка существенно облегчается за счет схожести оптимизационных задач и задач распознавания. Это позволяет при конструировании алгоритмов сведения оптимизационных задач пользоваться идеями алгоритмов сведения задач распознавания, известными из классической теории [13]. Тем не менее, некоторые алгоритмы аффинной сводимости в настоящей работе предложены впервые.

Структуру этой главы удобно изобразить в виде ориентированного дерева (см. рис. 1). Каждая стрелка на рисунке символизирует алгоритм, сводящий задачу, расположенную в начале стрелки, к задаче, находящейся в конце. В корне дерева расположена "основная" задача КЛИКА. В список исследуемых задач в первую очередь вошли наиболее известные классические задачи. В их числе оптимизационные варианты пяти из шести задач, фигурирующих в [13] как основные NP-полные задачи.

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

Рис. 1. Диаграмма сведения труднорешаемых задач.

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

1. Понятие сложности в комбинаторной оптимизации

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Максименко, Александр Николаевич

Заключение

За последние два - три десятилетия накопилось большое число результатов, касающихся свойств многогранников задач комбинаторной оптимизации. Прежде всего это связано с тем, что, как известно, комбинаторно-геометрические свойства многогранника являются характеристиками сложности соответствующей задачи в том или ином классе алгоритмов. К сожалению, многогранник ассоциируется только с общей задачей, в которой отсутствуют какие либо ограничения на множество исходных данных. Тем не менее, изучение на предмет сложности частных случаев задачи нередко представляет гораздо больший интерес. Именно это послужило причиной появления новой геометрической конструкции — многогранного разбиения пространства исходных данных задачи. Эта структура позволяет исследовать комбинаторно-геометрические свойства таких задач, для которых построение многогранника в явном виде невозможно.

Изучение свойств этой конструкции позволило по новому взглянуть на классическую теорию сводимости задач. Оказалось, что при сведении задачи X к задаче Y множество исходных данных первой задачи, как правило, аффинно отображается в множество исходных данных второй задачи. Так появляется новый тип сводимости — аффинная сводимость задач комбинаторной оптимизации. Одним из замечательных свойств которой является то, что если X осд У, то многогранное разбиение пространства исходных данных первой задачи аффинно отображается в некоторую часть многогранного разбиения прстранства исходных данных второй задачи. Как следствие, граф G(X) многогранника М(Х) оказывается изоморфным некоторому подграфу графа G(Y) многогранника второй задачи.

Практическая целесообразность введения этого нового типа сводимости задач комбинаторной оптимизации подтверждается описанными в настоящей работе многочисленными экспериментальными данными. Так, на основе классических алгоритмов сведения удалось показать, что наиболее простой для изучения граф многогранника задачи КЛИКА изоморфен графу многогранника задачи максимальная 2-ВЫПОЛНИМОСТЬ и графу многогранника задачи максимальный РАЗРЕЗ. Также упомянутый граф оказывается изоморфным некоторым подграфам графов многогранников таких труднорешаемых задач как 3-СОЧЕТАНИЕ, РЮКЗАК, КОММИВОЯЖЕР и ДЛИННЕЙШИЙ ПУТЬ. Кроме того, структура конусного разбиения для задачи КЛИКА оказалась изоморфна некоторой части конусного разбиения задачи РАЗБИЕНИЕ и задачи коммивояжера для длин ребер (дуг) которой выполнено условие "неравенства треугольника".

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

1) Граф многогранника задачи максимальная 2-ВЫПОЛНИМОСТЬ является полным.

2) Граф многогранника задачи максимальный РАЗРЕЗ полный.

3) Для плотности графа многогранника задачи 3-СОЧЕТАНИЕ справедлива оценка р(Тп) > 2V^"~3/2. В то время как ранее известная [9] оценка р(Тп) >

4) Для графа "наиболее сложного" многогранника задачи РЮКЗАК оценка плотности получена впервые: р(/С„) >2 i .

5) Доказано, что плотность графа многогранника задачи ГАМИЛЬТОНОВ КОНТУР оценивается снизу величиной Ранее [6] плотность оценивалась величиной 2*?~9/2.

6) Плотность графа многогранника задачи ГАМИЛЬТОНОВ ЦИКЛ в настоящей работе оценивается снизу величиной 21^-3/2. Ранее [9] плотность оценивалась величиной

7) Для графов многогранников М(С'п) и М(Сп) задач ДЛИННЕЙШИЙ ПУТЬ и ДЛИННЕЙШАЯ ЦЕПЬ впервые получены экспоненциальные нижние оценки плотности: р(С'п) > 2V4n-1)/2-1 и р(Сп) >

8) Кроме того, были исследованы графы конусных разбиений задачи РАЗБИЕНИЕ и задачи КОММИВОЯЖЕР с условием "неравенство треугольника". Оказалось, что граф для первой задачи совпадает с графом многогранника задачи РЮКЗАК, а граф для второй задачи идентичен графу многогранника задачи КОММИВОЯЖЕР.

Наряду с этим, в работе изучены комбинаторно-геометрические свойства таких полиномиально разрешимых задач как классическая задача о кратчайшем пути (ЗКП), задача о назначениях (ЗН) и задача о паросочетаниях (ЗП) в произвольном графе. Оказалось, что классическая ЗКП аффинно сводится к ЗН. Отсюда следует, в частности, что плотности графов многогранников ЗН и ЗП оцениваются снизу величиной ], где п — число работников в ЗН. Плотность графа конусного разбиения классической ЗКП вычисляется в настоящей работе непосредственно и оказывается равной

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

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

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

3) Внимательно ознакомившись с доказательствами свойств аффинной сводимости в разделе 2.2 "Аффинная сводимость задач", можно заметить, что для корректной работы доказанных утверждений условие аффинности отображения исходных данных не является необходимым и достаточно потребовать, чтобы отображение было непрерывным. Это замечание говорит об универсальности подхода.

Список литературы диссертационного исследования кандидат физико-математических наук Максименко, Александр Николаевич, 2004 год

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

2. Белов Ю.А. О ребрах многогранника диэдральной группы // Труды семинара по дискретной математике и ее приложениям. Москва: МГУ. 1989. С. 263.

3. Белов Ю.А. Об одном классе специальных перестановочных многогранников // Моделирование и анализ информационных систем. 1996. №3. С. 78-84.

4. Белошевский М.И. Многогранник задачи о максимальном разрезе // Модели и алгоритмы математического обеспечения ЭВМ. Ярославль. 1986. С. 12-20.

5. Бондаренко В.А. Соседние вершины многогранников, порождаемых матроидами // Вопросы теории групп и гомологической алгебры. Ярославль. 1982. С. 66-68.

6. Бондаренко В.А. Неполиномиальная нижняя оценка сложности задачи коммивояжера в одном классе алгоритмов // Автоматика и телемеханика. 1983. №9. С. 45-50.

7. Бондаренко В.А., Шуникова Е.В. Обобщенные перестановочные многогранники и свойства алгоритмов сортировки // Модели исследования операций в вычислительных системах. Ярославль. 1985. С. 105-113.

8. Бондаренко В.А. Полиномиальная верхняя оценка плотности графа многогранника бистохастических матриц // Тезисы межд. конф. "Математич. методы в исследовании операций". София. 1987. С. 11.

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

10. Гейл Д. Соседние вершины на выпуклом многограннике // Линейные неравенства и смежные вопросы. М.: ИЛ. 1959. С. 355-362.

11. Грешенев С.Н. Многогранник задачи о m-вершинном подграфе полного графа // Вычислительная математика и математическая физика. 1984. №5. С. 790-793.

12. Гришухин В.П. All facets of the cut cone Cn for n = 7 are known // European Journal of Combinatorics, 11. 1990. pp. 115-117.

13. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

14. Деза М.М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. — 736 с.

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

16. Емец О.А., Барболина Т.Н. Классы лексикографической эквивалентности в евклидовой комбинаторной оптимизации на размещениях // Полт. нац. техн. ун-т. Полтава. 2002. 8с. Деп. в ГНТБ Украины 10.06.2002, №90-Ук2002.

17. Емець О.О., Роскладка О.В., Недобачш C.I. Незвана система об-межень для загального многогранника розмпцень // Укр. мат. ж. 2003. 55, №1, с. 3-11.

18. Иванов В.В. О трехиндексной задаче назначения // Экономика и математические методы. 1974. Т. 10, N 2. С. 336-339.

19. Исаченко А.Н. On the structure of the quadratic boolean problem poly-tope // Combinatorics and Graph Theory. Vol. 25 of Banach Center Publications. P. W. N. Warszawa. 1989. pp. 87-91.

20. Карп P.M. Сводимость комбинаторных проблем // Сб.: Кибернетический сборник, новая серия. М.: Мир. 1975. Вып. 12. С. 16-38.

21. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432с.

22. Кук С.А. Сложность процедур вывода теорем // Сб.: Кибернетический сборник, новая серия. М.: Мир. 1975. Вып. 12. С. 5-15.

23. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9, №3. С. 115-116.

24. Леонтьев В.К. Устойчивость в комбинаторных задачах выбора // Докл. АН СССР. 1976. Т. 228. №1. С. 23-25.

25. Леонтьев В.К. Дискретные экстремальные задачи // Итоги науки и техники. М.: ВИНИТИ, 1979, N 31.

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

27. Максименко А.Н. Комбинаторные свойства многогранника задачи о кратчайшем пути // Труды школы-семинара по проблемам фундирования профессиональной подготовки учителя математики. Ярославль: ЯГПУ. 2003. С. 15-17.

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

29. Максименко А.Н. Многогранник задачи о рюкзаке // Вопросы теории групп и гомологической алгебры: Сб. науч. тр. Ярославль: ЯрГУ. 2003. С. 163-172.

30. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. №9. С. 3-33.

31. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985. 512с.

32. Сарванов В.И. О многогранниках, связанных с оптимизацией на подстановках. Минск. 1977. 14 с. (Препринт / ИМ АН БССР; №7).

33. Симанчёв Р.Ю. К вопросу о смежности вершин многогранника к-факторов // Международная конференция "Дискретный анализ и исследование операций", Новосибирск, 26 июня 1 июля, 2000: Материалы конференции. Новосибирск: ИМ СО РАН. 2000. С. 156.

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

35. Шенмайер В.В. Анализ алгоритма покоординатного подъема для задач дискретной оптимизации: Автореф. дис. на соискание уч. степ, канд. ф.-м. наук // Ин-т мат. СО РАН, Новосибирск, 2001, 14 с.

36. Alfakih Abdo Y., Yi. Tongnyoul, Murty Katta G. Facets of an assignment problem with 0-1 side constraint // J. Combin. Optimiz. 2000. 4, №. P. 365-388.

37. Bai'ou Mourad, Mahjoub Ali Ridha. Steiner 2-edge connected subgraph polytopes on series-parallel graphs // SIAM J. Discrete Math. 1997. 10, №. P. 505-514.

38. Balinski M.L., Russakoff A. On the assignment polytope // SIAM Rev. 1974. V. 16, №4. P. 516-525.

39. Barahona F., Mahjoub A.R. On the cut polytope // Mathematical Programming, 36, 1986. pp. 157-173.

40. Barahona F., Junger M. and Reinelt G. Experiments in quadratic 0-1 programming // Mathematical Programming, 44. 1989. pp. 127-137.

41. Boros E. and Hammer P.L. The max-cut problem and quadratic 0-1 optimization: polyhedral aspects, relaxations and bounds // Annals of Operations Research, 33. 1991. pp. 151-180.

42. Bool G. An Investigation of the Laws Thought on Wich Are Founded the Mathematical Theories of Logic and Probabilities. Dover Publications. New York, original edition. 1854.

43. Canovas Lazaro, Landete Mercedes, Marin Alfredo. New facets for the set packing polytope // Oper. Res. Lett. 2000. 27, №4, P.153-161.

44. Christof T. and Reinelt G. Combinatorial optimization and small poly-topes // TOP (Spanish Statistical and Operation Research Society), 4. 1996. pp. 1-64.

45. Dantzig G.B., Blattner W.O., Rao M.R. "All shortest routes from a fixed origin in a graph", in Theory of Graphs: International Symposium, Gordon and Breach, NY, 1967. 85-90.

46. Deo N., Pang C. Shortest-path algorithms: taxonomy and annotation // Networks. 1984. V. 14, №2. P. 275-329

47. De Simone C. The cut polytope and the boolean quadric polytope // Discrete Mathematics, 79. 1989-1990. pp. 71-75.

48. Deza M. Matrices des formes quadratiques non negatives pour des arguments binaires // Comptes Rendus de l'Academie des Sciences de Paris, 227(A), 1973. pp. 873-885.

49. Dijkstra E.W. A note on two problems in connexion with graphs // Numerishe Mathematik. 1959. №1. P. 269-271.

50. Edmonds J. Paths, trees and flowers // Canad. J. Math. 1965. V. 17. P. 449-467.

51. Edmonds J. Maximum matching and polyhedron of 0,1-vertices // J. Res. Bur. Stand. 1965. B. 69. №1-2. P. 125-130.

52. Hammer P.L. Some network flow problems solved with pseudo-boolean programming // Operations Research, 13, 1965. pp. 388-399.

53. Karmarkar N.A. A new polinomial-time algorithm for linear programming // Combinatorica. 1984. №4. P. 373-395.

54. Karp R.M. and Papadimitriou C.H. On linear characterization of combinatorial optimization problem // SIAM Journal on Computing, 11, 1982. pp. 620-632.

55. Kuhn H.W. The Hungarial Method for the Assignment Problem // Naval Research Logistics Quarterly. 1955. №1,2. P. 83-97.

56. Magalhaes Macambira Elder, Carvalho de Souza Cid. The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations // Eur. J. Oper. Res. 2000. 123, №2. P. 346-371.

57. Marchand Hugues, Martin Alexander, Weismantel Robert, Wolsey Laurence. Cutting planes in integer and mixed integer programming // Discrete Appl. Math. 2002. 123, №1-3, P. 397-446.

58. Papadimitriou С. H. The adjancency relation on the traveling salesman polytope is NP-complete // Math. Prog. 1978. P. 312-324.

59. Padberg M.W. The boolean quadric polytope: some characteristics, facets and relatives // Mathematical Programming, 45. 1989. pp. 139172.

60. Pitowsky I. The range of quntum probability // Journal of Mathematical Physics, 27. 1986. pp. 1556-1565.

61. Salazar-Gonzalez J.-J. The Steiner cycle polytope // Eur. J. Oper. Res. 2003. 147, №3, p. 671-679.

62. Sarangarajan A. A Lower bound for adjacencies on the travelling salesman polytope // SIAM J. Discrete Math. 1997. 10, №3. P. 431-435.

63. Schrijver F. Polyhedral combinatorics — some recent developments and results // Proc. Int. Congr. Math., Berkeley, California. 1986. V. 2. P. 1431-1443.