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

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

МАКСИМЕНКО АЛЕКСАНДР НИКОЛАЕВИЧ

ГРАФЫ МНОГОГРАННИКОВ И СВОДИМОСТЬ ЗАДАЧ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ

СПЕЦИАЛЬНОСТЬ 01.01.09 - ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА

АВТОРЕФЕРАТ

ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

Ярославль - 2004

Работа выполнена в Ярославском государственном университете им. П.Г.Демидова

Научный

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

доктор физико-математических наук, профессор Гришухин Вячеслав Петрович,

кандидат физико-математических наук, профессор Соколов Валерий Анатольевич.

Институт проблем передачи информации РАН.

Защита состоится "25" иЮНЯ 2004 года в часов на заседании диссертационного совета К 212.002.06 при Ярославском государственном университете им. П.Г.Демидова по адресу: 150000, г. Ярославль, ул. Советская, д.14.

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

Автореферат разослан " .ЛСОЭС 2004 года.

руководитель

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

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

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

Яблокова СИ.

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

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

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

В диссертации упоминаются две принципиально различные точки зрения на эту проблему, которые, тем не менее, в целом совпадают в своих выводах. Одна точка зрения принадлежит классической теории сводимости задач, развитой в работах С. Кука, Р. Карпа, Л. Левина (см. монографию Гэри М. и Джонсона Д. "Вычислительные машины и труднорешаемые задачи"). Эта теория предоставляет простой инструмент для сравнения задач по их сложности, избегая непосредственного анализа характеристик задач. Главное достижение этой теории состоит в том, что с ее помощью удается достаточно просто показать, что большинство известных труднорешаемых задач оказываются в определенном смысле самыми сложными.

С другой стороны, в настоящее время активно ведутся исследования геометрических конструкций, ассоциированных с ЗКО и

решающими эти задачи алгоритмами. В частности, наибольшее внимание уделяется изучению свойств многогранников задач. В этой связи отметим работы Белова Ю.А., Бондаренко В.А., Гри-шухина В.П., Деза М.М., Емеличева В.А., Емець О.О., Исаченко А.Н., Ковалева М.М., Кравцова М.К., Леонтьева В.К., Лоран М., Пападимитриу X., Симанчева Р.Ю. Интерес к многогранникам задач комбинаторной оптимизации обусловлен прежде всего тем, что для произвольной задачи ее многогранник строится достаточно простым и естественным образом. Как показывает опыт многих исследователей, комбинаторные характеристики многогранника являются характеристиками сложности соответсвую-щей задачи в том или ином классе алгоритмов. В частности, из работ Бондаренко В.А. известно, что плотность графа многогранника является нижней оценкой сложности задачи в широком классе алгоритмов, включающем в себя известные методы комбинаторной оптимизации. Такой, "геометрический" подход, в отличие от классической теории сводимости, позволяет оценить сложность задачи числом. Главное препятствие для развития этого перспективного направления состоит в принципиальной сложности вычисления характеристик многогранников. На это указывает, например, результат Пападимитриу X. о том, что проблема распознавания смежности вершин многогранника задачи коммивояжера является N P-полной.

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

Методы исследования. При решении поставленных задач использовались методы теории сводимости задач, методы ком-

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

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на научных конференциях:

1) I Международная научно-практическая конференция (заочная) "Фундаментальные и прикладные исследования в системе образования". (Тамбов: ТГУ, 2003 год);

2) IV Международная школа-семинар, посвященная 100-летию

со дня рождения академика А.Н. Колмогорова "Профессионализация предметной подготовки учителя математики в педагогическом вузе." (Ярославль: ЯГПУ, 2003 год);

3) Всероссийская научная конференция, посвященная 200-летию ЯрГУ им. П.Г. Демидова. (Ярославль: ЯрГУ, 2003 год).

Публикации. По результатам исследований было опубликовано 6 печатных работ: 3 статьи и 3 тезиса докладов. Основные результаты вошли в отчеты по грантам РФФИ за 2002 и 2003 гг.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, содержащего 67 наименований. Текст диссертации включает в себя 4 иллюстрирующих рисунка. Общий объем диссертации - 92 страницы.

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

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

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

Первая глава состоит из двух разделов. Название первого раздела, — некоторые сведения из теории сводимости задач. Здесь прежде всего приводятся основная идея и метод исследований классической теории сводимости. Упоминается о том, что эта теория работает прежде всего с задачами распознавания. В качестве примера приводится алгоритм сведения задачи КОММИВОЯЖЕР к задаче о длиннейшем пути. Проводится сравнительный (по сложности) анализ двух задач:

1) Задача оптимизации: Найти аргумент х € X целевой функции на котором она достигает свое максимальное значение.

2) Задача распознавания: Определить, существует ли такой аргумент , при котором целевая функция принимает значение, не меньшее некоторого, наперед заданного числа С: с(я) > С; и если существует, то указать такой аргумент.

Далее внимание читателя обращается на тот факт, что для задач оптимизации тоже можно построить аналогичную теорию сводимости. И в качестве примера приводится алгоритм сведения оптимизационной задачи КОММИВОЯЖЕР к задаче о длиннейшем пути.

Второй раздел называется "Многогранники задач". Начинается этот раздел с описания многогранника задачи КОММИВОЯЖЕР. Пусть G(V, E) — полный реберно взвешенный граф на п вершинах, в котором требуется найти гамильтонов цикл максимальной длины. Рассмотрим множество Хп всех гамильтоно-вых циклов в этом графе. Это множество еще называют множеством допустимых решений задачи. Интерпретируем множество Хп как множество точек в евклидовом пространстве К". Для этого положим т = = "(""*) и каждому ребру et-j € Е поставим в соответствие координату произвольной точки х — (x{j) £ Rm. Теперь для каждого цикла х € Хп рассмотрим его характеристический вектор :

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

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

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

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

Первый носит название "Конусное разбиение" и начинается с определения. Пусть X С Б.т — множество допустимых решений некоторой массовой задачи на максимум. Для каждого рассмотрим множество

К(х) = {с£ В,т : (с, х) > (с, у) для любого у Е X}.

К(х) представляет собой выпуклый многогранный конус. Совокупность всех К(х), где х 6 X, называется конусным разбиением пространства Ят исходных данных по множеству X. Известно, что конусное разбиение и многогранник задачи являются двойственными структурами. Вследствие этого граф G(X) многогранника М(Х) будем также называть графом конусного разбиения пространства Ит по множеству X. В то же время граф конусного разбиения представляет собой более гибкий инструмент для изучения характеристик задачи, чем граф ее многогранника. Дело в том, что многогранник удается построить лишь для задачи без дополнительных ограничений, тогда как свойства конусного разбиения можно исследовать и для тех частных случаев, когда на множество исходных данных задачи накладываются линейные ограничения. И в качестве примера здесь рассматривается задача о кратчайшем пути, для которой обычно вводят ограничение на неотрицательность длин ребер (дуг).

Формальное определение возникающего в связи с этим нового понятия выглядит следующим образом. Рассмотрим частный случай задачи X С Ит дискретной оптимизации, когда множество исходных данных представляет собой многогранное множество (полиэдр) Э С Ят (причем S может быть и меньшей размерности, чем Я.т). Будем обозначать такую массовую задачу (X, 5). В этом случае многогранное разбиение множества 5 по множеству X образуется полиэдрами К(х, 5) = К{х) П Б, где х £ X. Граф (^(Х) такого многогранного разбиения определим по аналогии с графом конусного разбиения всего пространства Нт

Определение. Полиэдр Л'(х,5), где х € X, образует вершину графа Gs{X), если найдется вектор исходных данных в € 5 такой, что х является единственным оптимальным решением индивидуальной задачи [X, я]

Определение. Вершины графа С^Х), соответствующие полиэдрам К(х, 5) и К (у, 5), соединены ребром, если найдется такой вектор э € 3, что для каждого г 6 X отличного от х и от у, выполнено (ж, в) = (у, 5) > (г, в). В таком случае будем говорить, что полиэдры К(х,3) и К(у,Б) смежны.

Свойство. Граф (^(Х) является подграфом графа С?(Х) Обозначение: (^(.АГ) -< С(Х)

Рассмотрим важный пример, когда 5 = (¿т = {х 6 Нт : _ 1 5: хг ^ 1» х = (х1)г2>--чЯт)} — куб с длиной ребра, равной 2, и центром в начале координат.

Теорема. Пусть X С Дт, X — ехИ№(Х) и <3 = (2т1 тогда =

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

Определение. Будем говорить, что задача (X, Б) для многогранного множества исходных данных 5 С К™ аффинно сводится к задаче У = (У,.йп), где тп <п, если найдутся

1) невырожденное аффинное отображение А : 5 —> Т, дей-

ствующее взаимно-однозначно из S в некоторое многогранное множество Т С Rn (В данном случае аффинное отображение можно задать формулой i = ^(s) = Ks + d, где t 6 T, s € S, d G Rn и К — матрица размера п х т, причем rang К = т),

2) и взаимно-однозначное соответствие В : X —> Y' между множеством X и некоторым подмножеством УСУ

такие, что для каждого вектора s € S выполнено следующее условие:

Уо является решением задачи [У, j4(s)], тогда и только тогда, когда уо € Y' и Xq = В~г{уо) — решение задачи [X,s].

Для таких задач введем обозначение: (Л", 5) ОС а Y

Теорема. Пусть (^,5) осл Y и А : S Т, тогда Gs{X) =

GT(y) -с G(Y)

Следствие. Пусть (X,Qm) <хд Y, тогда G(X) -< G{Y) Следствие. Пусть (X,Qm) осд Y, тогда р{Х) < p{Y), где р{) - плотность графа соответствующего многогранника.

С целью пояснения сути сформулированных утверждений тут же приводится следующий факт. Оказывается, оптимизационная задача КОММИВОЯЖЕР {?ín,Q), веса ребер которой могут принимать значения из отрезка [—1,1], аффинно сводится к задаче о длиннейшем пути £„+i. Обозначаем (HntQ) <*А £п+1 . И, опираясь на только что сформулированные свойства аффинной сводимости, получаем следующие утверждения.

Теорема. Граф G(7ín) многогранника задачи коммивояжера изоморфен некоторому подграфу графа многогранника

задачи о длиннейшем пути.

Следствие. Плотность р{Ип) графамногогранника M(7ín) не превосходит по своей величине плотности p(jCn+i) графа многогранника

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

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

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

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

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

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

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

жена "основная" задача КЛИКА.

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

Приведем здесь лишь новые результаты, принадлежащие автору работы.

Следствие. Граф (?(СП) многогранника задачи КЛИКА изоморфен некоторому подграфу графа (7(7^) многогранника задачи 3-СО ЧЕТАНИЕ, где тп =

Следствие. Плотность р{Тт) графа многогранника М(7^п) задачи трехмерное сочетание оценивается снизу экспоненциальной величиной:

Теорема. Граф £7(7^) многогранника задачи 3-СОЧЕТАНИЕ изоморфен некоторому подграфу графа

многогранника задачи о рюкзаке с вектором размеров т и размером рюкзака, равным половине суммарного размера предметов.

Следствие, Плотность графа многогранника задачи

о рюкзаке для т (т > 2) предметов экспоненциальна:

Следствие. Плотность графа конусного разбиения для задачи РАЗБИЕНИЕ оценивается снизу величиной 2(х/"*-2-5)/2, где т — размерность задачи.

Следствие. Граф (7(Сп) многогранника задачи КЛИКА изоморфен некоторому подграфу графа , где , многогранника задачи гамильтонов контур.

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

р{П'к) >

Следствие. Граф многогранника задачи гамильтонов

контур изоморфен некоторому подграфу графа много-

гранника задачи гамильтонов цикл,

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

Следствие. Граф многогранника задачи гамильтонов

цикл в точности совпадает с графом (7д конусного разбиения задачи коммивояжера с условием "неравенство треугольника".

Следствие. Плотность полиэдрального графа задачи ДЛИННЕЙШАЯ ЦЕПЬ на п вершинах экспоненциальна:

Следствие. Граф многогранника задачи гамильто-

нов контур изоморфен некоторому подграфу графа С(Сп) многогранника задачи о длиннейшем пути.

И получаем

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

где [ ] — операция выделения целой части числа.

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

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

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

Впервые поставлена и решена задача изучения графовых характеристик для многогранника задачи РЮКЗАК. Обнаружена возможность изучения комбинаторно-геометрических характеристик сложности для задач с различными линейными ограничениями на множество исходных данных. В числе таких задач изучена задача о кратчайшем пути с ограничением на неотрицательность длин контуров.

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

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

СПИСОКРАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2) Максименко А.Н. Нижняя оценка плотности графа многогранника задачи о паросочетаниях // Фундаментальные и прикладные исследования в системе образования: Материалы 1-й международной научно-практической конференции (заочной). Тамбов: ТГУ им. Г.Р. Державина. 2003. С. 162164.

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

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

5) Максименко А.Н. Сложность задачи о кратчайшем пути и комбинаторные свойства ее многогранника // Материалы всероссийской научной конференции, посвященной 200-летию ЯрГУ им. П.Г. Демидова. Информатика и вычислительная техника. Ярославль: ЯрГУ. 2003. С. 54-56.

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

»10819

Введение

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 "Аффинная сводимость задач", можно заметить, что для корректной работы доказанных утверждений условие аффинности отображения исходных данных не является необходимым и достаточно потребовать, чтобы отображение было непрерывным. Это замечание говорит об универсальности подхода.

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.