Приближенные алгоритмы решения некоторых многоиндексных задач о назначениях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Приближенные алгоритмы решения многоиндексной аксиальной задачи о назначениях

1.1 Многоиндексная аксиальная задача о назначениях.

1.1.1 Постановка задачи.

1.1.2 Нриближенный алгоритм.

1.2 Трехиндексные аксиальные задачи о назначениях с одной од-ноциклической подстановкой.

1.2.1 Постановка задачи.

1.2.2 Приближенный алгоритм.

1.3 Трехиндексные аксиальные задачи о назначениях с двумя од-ноциклическими подстановками

1.3.1 Постановка задачи.

1.3.2 Приближенный алгоритм.

1.4 Трехиндексная аксиальная задача о назначениях на одноцик-лических подстановках на минимум.

1.4.1 Постановка задачи.

1.4.2 Приближенный алгоритм.

1.4.3 Корректность работы алгоритма.

1.4.4 Анализ оценок качества алгоритма.

1.5 Трехиндексная аксиальная задача о назначениях на одноциклических подстановках на максимум.

1.5.1 Постановка задачи.

1.5.2 Приближенный алгоритм.

1.5.3 Анализ корректности работы и оценок качества алгоритма

1.6 Разрешимость многоиндексной аксиальной задачи о назначе

1% ниях на одноциклических подстановках.

1.6.1 Постановка задачи.

1.6.2 Предварительные замечания и необходимый признак разрешимости задачи

1.6.3 Критерий разрешимости 7-индексной задачи.

1.6.4 Заключительные замечания о разрешимости многоиндексной задачи.

2 Приближенные алгоритмы решения трехиндексной планарной задачи о назначениях

2.1 m-слойная планарная задача о назначениях.

2.1.1 Постановка задачи.

2.1.2 Приближенный алгоритм для случая т < п/

2.1.3 Анализ работы алгоритма.

2.2 Двухслойная планарная задача о назначениях с одной одно-циклической подстановкой

2.2.1 Постановка задачи.

2.2.2 Приближенный алгоритм.

2.3 Двухслойная планарная задача о назначениях на одноцикли-ческих подстановках.

2.3.1 Постановка задачи.

2.3.2 Приближенный алгоритм.

2.3.3 Постановка задачи в терминах теории графов

2.3.4 Алгоритм с оценкой точности 9/4 + 0(1/п) для метрической задачи с одинаковой весовой функцией

2.3.5 Обоснование оценок точности алгоритма. м 2.3.6 Алгоритм с оценкой точности 12/5 + 0(1 /тт.) для метрической задачи с разными весовыми функциями

2.3.7 Обоснование оценок точности алгоритма.

2.4 Двухслойная планарная задача о назначениях на одиоцикли-ческих подстановках на максимум.

2.4.1 Постановка задачи.

2.4.2 Приближенный алгоритм с константной оценкой точности 3/4.

2.4.3 Обоснование оценок точности алгоритма.

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

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

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

Среди дискретных задач оптимизации принято выделять класс задач Р, разрешимых за полиномиальное время (в зависимости от длины входа) и класс ИР-трудных задач, для которых построение полиномиальных алгоритмов проблематично (если только № не равно Р) [8]. К сожалению, многие естественные и интересные задачи дискретной оптимизации являются ИР-трудными. Доказано, что если найдется быстрый алгоритм (число действий которого зависит полиномиально от размерности задачи) хотя бы для одной ИР-трудной проблемы, то такие алгоритмы можно будет построить для всех задач из этого класса. Одной из самых фундаментальных проблем современной математики является вопрос: существует ли такой быстрый алгоритм для КР-трудных задач? Многие исследователи склоняются к отрицательному ответу на этот вопрос.

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

Одной из самых известных является задача о назначении. Выделяют несколько основных классов задачи о назначениях: классическая линейная задача о назначении, квадратичная задача о назначении, многоиндекспая задача о назначении, трехиндексная аксиальная и планарная задачи о назначениях и т.д. Более полно и подробно о задаче о назначениях можно ознакомиться, например, в [41, 42, 43, 49, 101, 106].

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

Приведем несколько примеров. Допустим, некий популярный музыкальный коллектив "АБВГД" планирует гастрольное турне. "АБВГД" отправляется на гастроли из своего родного города, собирается объехать п городов, каждый вечер давая концерт в новом городе, и вернуться обратно. Стоимость переезда из города в город зависит от времени поездки (различные расписания для различных видов транспорта, различия в тарифах для разных видов транспорта и внутри одного вида и т.д.). Менеджер группы "АБВГД" хочет минимизировать затраты, связанные с передвижением. Одним из путей достижения его цели является решение трехиндексной аксиальной задачи о назначениях с одной одноциклической подстановкой.

Допустим, что в рамках технологического или управленческого процесса некого крупного сырье-добывающего предприятия "O/L2" п пунктов добычи посещаются двумя видами транспорта при условии, что оба транспортных средства посещают каждый пункт один раз, оба маршрута начинаются и заканчиваются в одной точке (на аэродроме, в гараже, в ангаре). Каждый пункт несет затраты, связанные с посещением (например, обеспечение транспортных средств горючо-смазочными материалами). Цель менеджера компании "OIL2", отвечающего за транспорт, минимизировать суммарные затраты. Если затраты каждого предприятия не являются аддитивной функцией от вида транспорта (что само по себе не редкость для практических задач), то решение трехиндексной аксиальной задачи о назначениях с двумя одноциклическими подстановками является одним из вариантов достижения поставленной цели.

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

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

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

Задача коммивояжера является одной из самых известной задачи в исследовании операций. Выделяют несколько основных классов задачи о коммивояжере: симметричная задача о коммивояжере, асимметричная задача о коммивояжере, метрическая задача о коммивояжере, задача о коммивояжере на максимум и т. д. Имеется большое число работ, посвященных данной проблеме, например [88, 104, 110, 111, 131].

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

Многоиндексная задача о назначениях (МЗН) является естественным обобщением классической линейной задачи о назначении. Первой работой, посвященной многоиндексной версии задачи о назначениях, можно считать работу Pierskalla [126], вышедшую в 1968 году. Наиболее известны две разновидности МЗН: аксиальная и планарная трехиндексная задача о назначении.

Трехиндексная аксиальная задача о назначениях (З-АЗН) может быть сформулирована следующим образом. п п п bjkXijk min г=1 j=1 к=1 при условии, что п п ^ ^ ] %ijk = lj г = 1,2,., 71, j=1 к=1 п п з = 1,2,.,я, п п ^ ^ ] xijk = 1; & = 1, 2, . . ., 72, i=l j=l

Xijk = 1 для 1 < г, j, А; < тг, где Cijk ~ заданные вещественные числа, 1 < г, j, к < п.

Другими словами З-АЗН состоит в таком выборе п элементов в кубической матрице (сук) порядка п, что в каждом ее сечении выбран ровно один элемент и сумма выбранных элементов минимальна. (Под сечением матрицы понимается множество п2 ее элементов с фиксированным значением одного из индексов 1 < г, j, к <п).

З-АЗН можно записать в алгебраической форме: п

У^ сгтг(г>тг(г) —'" min г=1 по всем подстановкам 7Г, а степени п.

Кагр первым показал, что З-АЗН NP-трудна [99].

Трехиндексная планарная задача о назначении (З-ПЗН) формулируется следующим образом: п п п

S CijkXijk min г=1 j=l k=l при условии, что п ^ %ijk = 1, 3 = 1 j • • • , П., fc = 1, . . . , 71, г=1 п ^ %ijk = 1, 2 = 1, . . . , 72, /? = 1, . . . , 72, J=1 п ] ■Eyfc = 1, 2 == 1, . . . , 71, J — 1, . . . , 72, к=\ ijk € {0, 1}, ij,k=l,.,n.

Трехиндексная планарная задача о назначении NP-трудна [73]. В общем случае m-индексная аксиальная задача о назначениях (МАЗН) формулируется следующим образом: п п

Ch.imXh.im min

1 = 1 tm=1 при условии, что п п ^ • • • ^ ^ xi\.im = 1} ¿1 = 1, . . . , 77,

2 = 1 ¿т = 1 п п тг п

•• -¿ш=

1 = 1 ¿/с-1=1 ¿fc+l = l ¿fc-l=l для к — 2,., m — 1, и %k~ 1,2,., 71, п п

У ] • • • ^ ^ == 1» im = * • ■ 1

1 = 1 ¿т—1 = 1

ХЧ.Лт G {0> !} ДЛЯ 1 < ¿1, ¿2, • • • , «ГО < Ш

Здесь через Cj^.^ обозначены элементы прямоугольной п х ■ - • х п матрицы - заданные вещественные числа, 1 < ik < п, к = 1,., га. Будем называть матрицу {ciii2.tm) матрицей коэффициентов стоимости.

Для МАЗН удобно использовать более компактную форму ее записи с помощью подстановок из симметрической группы Sn порядка п: п

7Га(г),.,7Гта1(г) где 7ri(z),.,7Tmi(i) € Sn.

В общем случае МАЗН является NP-трудной [73]. В случае, когда матрица коэффициентов стоимости является матрицей Monge [44], решением задачи является набор тождественных подстановок iti{j) = j, для г = 1,.,m — 1, j = 1 ,.,тг. Burkard, Rudolf и Woeginger [46] показали, что МАЗН остается NP-трудной для m > 3 в случае когда матрица коэффициентов стоимости является обратной матрице Monge.

Классическая задача коммивояжера (ЗК) (в англоязычной литературе The Traveling Salesman Problem (TSP)) состоит в нахождении обхода п городов, имеющего минимальную общую длину. Считаются заданными расстояния между всеми парами городов. Обходом считается замкнутый маршрут, проходящий через каждый город ровно один раз. И хотя современный коммивояжеры не руководствуются в выборе маршрута столь жесткими ограничениями, ЗК является типичной "трудной" задачей комбинаторной оптимизации.

ЗК известна под разными именами. В начале тридцатых годов прошлого века Karl Menger исследовал разновидность ЗК, называемую задачей курьера (messenger problem или Botenproblem) [39, 112]. Работа Menger [112] является первой публикацией на тему ЗК. В 1955 Morton и Land [116] заметили, что ЗК может быть знакома статистикам как задача средних минимальных расстояний (the mean minimum distances problem). Они ссылаются на работы [77, 109]. Сам термин "задача коммивояжера" родился, по-видимому, в США. Первая работа, в которой используется именно этот термин, вышла в свет в 1949 году [133]. Тем не менее, точкой отсчета начала систематическое исследования ЗК как задачи комбинаторной оптимизации следует считать работу Dantzig, Fulkerson и Johnson [59]. За дальнейшей эволюцией ЗК можно проследить в обзорах [110, 111] а также в книгах [104] и [131]. Одна из последних книг, посвященная современному состоянию исследований по ЗК, вышла в 2002 году под редакцией Gutin G. и Punnen А. Р. [88].

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

Как уже отмечалось выше, МАЗН полиномиально разрешима, когда матрица коэффициентов стоимости является матрицей Monge [44]. Однако, максимизационная версия МАЗН в случае, когда матрица коэффициентов стоимости является матрицей Monge, остается NP-трудиой.

Burkard, Rudolf и Woeginger [46] исследовали случай З-АЗН с мультипликативными коэффициентами, когда Cijk = u{VjWk, где щ, vj, Wk > 0. Они показали, что максимизационная версия такой З-АЗН полиномиально разрешима, а минимизационная версия остается NP-трудной. В той же работе приводится еще несколько полиномиально разрешимых классов З-АЗН.

Можно привести целый ряд работ, в которых ЗК также рассматривалась с точки зрения выявления полиномиально разрешимых подклассов. Первый нетривиальный полиномиально разрешимый случай метрической ЗК исследовал Flood [70]. Он исследовал случаи, когда оптимальный тур определяется простым (т.е. не имеющим самопересечений) многоугольником на плоскости. Один из наиболее известных полиномиально разрешимых случаев, имеющих большое практическое применение, представлен Gilmore-Gomory ЗК [78]. Разновидности ЗК, полиномиально разрешимые с помощью Gilmore-Gomory схемы [78], можно найти в [11, 31, 37, 40, 51, 79 , 98, 124].

Работы по выявлению полиномиальной разрешимости классов ЗК можно найти [32, 51, 60, 61].

Перейдем к переборным способам нахождения точного решения многоиндексной аксиальной задачи о назначениях. В 1994 году был предложен алгоритм для МАЗН, использующий Лагранжевую релаксацию [127, 128].

Pierskalla [125] был первым, кто предложил эвристику для З-АЗН. Применение метода ветвей и границ давно уже стало классикой. Как правило, исходная задача разделяется на две подзадачи фиксированием значения переменной x^k {х^ь полагается либо 0, либо 1). Balas и Saltzman [36] предложили стратегию ветвления, которая позволяет фиксировать несколько переменных на каждом этапе. Burkard и Rudolf [45] исследовали различные схемы ветвления. Hansen и Kaufman [89] предложили прямодвойствен-ный метод решения З-АЗН. В [43] в качестве нижних границ для метода ветвей и границ используют Лагранжеву релаксацию. Другая субградиентная процедура для решения Лагранжевой релаксации З-АЗН описана Frieze и Yadegar [74]. Burkard и Rudolf [45] получили хорошие результаты вычислительных экспериментов для алгоритма, использующего классические правила ветвления в сочетании со специальным шагом упрощения в каждой вершине. Модификация метода ветвей и границ, предложенная Balas и Saltzman [36], использует другую Лагранжеву релаксацию для вычисления нижних границ. Для решения граничных неравенств, составляющих данную релаксацию, используется субградиентная процедура.

Для З-ПЗН первым метод ветвей и границ предложил Vlach в 1967 году [140]. Другую модификацию этого классического метода предложили Magos и Miliotis [108]. В 1996 году Magos предложил алгоритм поиска с запретами [107].

Далее мы коснемся переборных способов нахождения точного решения задачи коммивояжера. Существует огромное количество работ, посвященных данному подходу. Прежде всего выделим метод динамического программирования, предложенный Held и Кагр в 1962 году [91], и, независимо от них, Коробковым В. К. и Кричевским Р. Е. в 1966 году [10] (с временной сложностью п2п). Также отметим алгоритм Лагранжевой релаксации, базирующийся на 1-дереве, предложенный Held и Кагр в 1970 году [92, 93]. По сей день оба подхода имеют серьезные ограничения на размерность задач, к которой они применяются. Наилучшие результаты с применением Лагранжевого подхода были получены Belloni и Lucena в 2000 году [38].

Считается, что хорошие результаты в этом направлении дает применение метода ветвей и сечений (The Branch-and-Cut method) [59] к двух индексной (double index) формулировке ЗК [122].

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

Модели целочисленного линейного программирования для ЗК можно найти в [25, 26, 27, 50, 122]

Коснемся способов расширения модели целочисленного линейного программирования дополнительными неравенствами. Широко рассматриваются: монотонная релаксация (the monotone relaxation) [33, 54, 85, 86], релаксация гамильтонова пути (Hamiltonian path relaxation) [129], графическая релаксация (the graphical relaxation) [56] и множество других [54, 56, 58, 71, 83, 85, 87, 117, 118, 119, 120].

Для описанных выше моделей используются различные модификации метода ветвей и границ, в качестве нижней оценки берутся всевозможные линейные релаксации (см., например, [55, 141]). Описание модификаций метода ветвей и границ можно найти в [52, 97, 121].

Кстати, впервые метод ветвей и границ был предложен Land и Doig [102] для задачи многомерного рюкзака. Определение этого метода можно найти в книге Береснева, Гимади, Дементьева [1]. Вообще говоря, метод ветвей и границ не гарантирует избежания полного перебора. Но практическая реализация этого метода в ряде случаев дает хорошие апостериорные оценки времени работы метода. Подробный обзор применения этого метода к ЗК можно найти в работе Balas и Toth [34].

Для асимметричной ЗК (когда расстояние между двумя городами зависит от направления движения) в качестве оценок снизу для метода ветвей и границ для ЗК можно брать решение задачи о назначении или ее специальной модификации [34, 47, 64, 65, 113, 114, 138]. В 1989 году более сложную процедуру поиска оценок снизу предложил Toth [66, 67]. Он развил идею работы Carpaneto и Toth [48]. Метод ветвей и сечений также был рассмотрен для асимметричной ЗК в 2000 году Ascheuer [28], Ascheuer, Juenger и Reinelt [30] и в 1995 году Ascheuer, Fischetti и Groetschel [29].

Существует огромное количество эвристик для ЗК. Условно все эвристики для ЗК можно разделить на два класса: эвристики, конструирующие тур (такие эвристики строят тур, добавляя по вершине на каждом этапе), и эвристики, улучшающие тур (такие эвристики начинают свою работу с уже имеющего тура, улучшая его шаг за шагом). Также существует огромное количество алгоритмов, комбинирующих эти два класса. Более подробного данное направление освещено в [80, 81, 82, 92, 93, 94, 105, 130].

Как было сказано выше, построение точных эффективных алгоритмов для NP-трудных задач является проблематичным (дискуссия по этому вопросу содержится в работе Гэри и Джонсона [8]).

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

Общепринято считать, что известная работа Graham [84] по теории расписаний послужила началом для подобных исследований. В работе Johnson [96] вводятся понятия приближенного алгоритма и его точности в худшем случае.

В конце семидесятых годов вышло много интересных работ по приближенным алгоритмам и, как следствие этого, появилось несколько обзоров [68, 132, 134], в которых суммируются результаты, полученные за эти годы. Хорошим введением в эту область исследований являются диссертация Агога [22] и обзор Arora, Lund [23], работа Papadimitrou, Yannakakis [123], а также обзор [136].

Напомним определения основных понятий теории приближенных решений [96]. Пусть имеется приближенный алгоритм А для решения оптимизационной задачи. Пусть / - индивидуальная оптимизационная задача, Za{I) ~ значение приближенного решения, полученного алгоритмом А, Z*(I) - точное значение задачи. Есть несколько способов измерения точности приближенного алгоритма. Наиболее распространенной и используемой величиной, характеризующей точность приближенного алгоритма, является так называемая относительная точность, под которой понимается функция тд(/) = Za{I)/Z*{I). Априорной оценкой относительной точности приближенного алгоритма А решения оптимизационной задачи на максимум (минимум) является величина Ra такая, что для любой индивидуальной задачи / выполняется неравенство тА{1) > Ra (ta(I) < Ra) •

Такую оценку Ra, не зависящую от размерности индивидуальной задачи /, называют константной.

В 1976 году Sahni и Gargles [135] показали, что нахождение даже 2п-приближенного решения ЗК является NP-трудной задачей. Под полиномиальной приближенной схемой (PTAS) будем понимать последовательность полиномиальных приближенных алгоритмов, которые для любого фиксированного е > 0 находит (1 + £)-приближенное решение. Последние исследования показали, что если Р^ NP, то для ЗК (в общем случае) невозможно построить PTAS.

Для метрической ЗК (когда расстояния между городами удовлетворяют неравенству треугольника) известен полиномиальный алгоритм с оценкой точности 3/2 (публикации: Christofides в техническом отчете [53], Сердюков в работе [16]). Отметим, что хотя в англоязычной литературе данный алгоритм известен, как алгоритм Кристофидеса, А. И. Сердюков открыл его совершенно независимо и практически одновременно. В настоящее время ряд исследователей используют название алгоритм Christofides and Serdyukov (см., например, Дейнеко). На протяжении многих лет он оставался лучшим результатом для данной задачи. В 1998 году Агога [24] предложил PTAS для метрической ЗК. Вначале алгоритм имел пвременную сложность, которая затем была улучшена до n(logn)°^/£^ (Несколькими месяцами позже Mitchell независимо предложил подобную схему, выполняемую за пО( 1/е) [115]). Схему можно применять и для ЗК в Rm для любой константы га. Если m не является константой, но зависит от п как m = O(logn), то число вершин, при котором алгоритм работает за время, превышающее полиномиальное, растет экспоненциально от га. Подобная зависимость от размерности прекрасно согласуется с широко известным результатом Trevisan [139]: метрическая ЗК MAX-SNP-трудна в R°(lozn).

Для ЗК на максимум с неотрицательными расстояниями между городами получены следующие результаты: в 1979 году получен алгоритм с оценкой точности 1/2 [69], в 1986 году получен алгоритм с оценкой точности 4/7 [13], в 1994 году алгоритм с оценкой точности 38/63 [100].

Для симметричной ЗК на максимум получены следующие результаты: в 1979 году получен алгоритм с оценкой точности 2/3 [69], в 1984 году получен алгоритм с оценкой точности 13/18 [12], в 1998 году получен алгоритм с оценкой точности 5/7 в [90], и лучший на сегодняшний день, полученный в 1984 году, алгоритм с оценкой точности 3/4 Сердюкова с временной сложностью 0(п3) [17].

Отметим, что Сердюковым получены интересные результаты и по целому ряду других классов ЗК [14, 18, 19, 21].

В 1992 году Crama и Spieksma [57] рассмотрели специальный класс 3-АЗН, сформулированной в терминах теории графов. Длины ребер должны удовлетворять неравенству треугольника, а сумма ребер треугольника определяется либо как сумма длин его сторон (обозначим такую задачу как ТА) либо как сумма двух наиболее коротких сторон (обозначим такую задачу как SA). В [57] показано, что обе задачи являются NP-трудными и приводятся алгоритм с оценкой точности 3/2 для ТА и алгоритм с оценкой точности 4/3 для SA.

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

Здесь мы изложим идею построения алгоритма с оценками {sn,Sn), впервые предложенную Гимади, Глебовым, Перепелицей в работе [3]. Данный подход являлся в своем роде революционным для исследования NP-трудных проблем. А впервые этот метод был реализован Гимади, Перепелица [5]. Работа [137] дает хорошую библиографию по данной тематике. Данный подход также будет использован при получении результатов диссертации.

Пусть К - некоторый класс задач. Через Z(S) обозначим оптимальное значение целевой функции для задачи S Е К. Будем считать, что рассматриваются задачи на минимум и Z(S) > 0 для всех S Е К.

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

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

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

В подобной ситуации можно пытаться использовать различные возможности косвенного описания, находить какие-то нетривиальные характеристики этих множеств. В качестве таких характеристик можно, например, рассматривать меры множеств КеА относительно различных вероятностных распределений на классе К, что и осуществлено одним из возможных способов в [3].

Пусть заданы класс задач К и некоторое семейство Р вероятностных мер, определенных на классе К. Говорят, что алгоритм А имеет тип (£, 6) относительно Р, если для всех р € Р.

В этом случае также говорят, что алгоритм А имеет оценки (е, 6) относительно Р .

Алгоритм А называется асимптотически точным на классе задач К, если существуют такие последовательности (гп), (¿и), что для любого п алгоритм А удовлетворяет оценкам (£п,£п) на подмножестве Кп С К задач размерности п и при этом еп —» 0, 5п —> 0 при п —> оо.

Заметим, что алгоритм будет точным в том и только в том случае, если он имеет оценки (0,0) относительно любого семейства вероятностных мер.

Нетрудно представить ситуацию, в которой величины £ и <5 действительно могут трактоваться как оценки вероятностного характера для относительных погрешностей получаемых с помощью алгоритма А решений. В самом деле, пусть алгоритм А имеет тип (£, 6) относительно Р и он используется для решения задач класса К, которые поступают из некоторого случайного источника, имеющего распределение р 6 Р. Тогда можно быть уверенным, что вероятность не получить алгоритмом А решение с приемлемой относительной погрешностью - не более 6. При этом само распределение Р мы можем и не знать, лишь бы было известно, что оно принадлежит семейству Р.

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

Для З-АЗН этот подход был реализован Гимади и Сердюковым в работе

71

Для классической ЗК этот подход был реализован в статьях [5, б]. Для ЗК на максимум данный подход был реализован работе [2, 4, 20].

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

В первой главе рассматриваются различные модификации многоиндексной аксиальной задачи о назначениях. Основываясь на идее построения быстрых приближенных алгоритмов с оценками качества [3], для классической многоиндексной аксиальной задачи о назначениях предлагается приближенный алгоритм, имеющий временную сложность 0(п3). Для решения задач на случайных входах приводятся условия его асимптотической точности. Рассмотрена трехиндексная аксиальная задача о назначениях на подстановках специального вида. Исследуются случаи, когда одна подстановка является одноциклической, обе подстановки являются одно-циклическими и случай, когда обе подстановки и их произведение являются одноциклическими. Для первых двух задач предлагаются приближенные алгоритмы, являющиеся модификациями ранее известных алгоритмов [б, 7]. Для решения задач на случайных входах указываются условия их асимптотической точности. Для третьей задачи показывается, что необходимым и достаточным условием разрешимости является нечетность п. Для минимизационной и максимизационной версий задачи предлагаются полиномиальные приближенные алгоритмы. Алгоритм для задачи на минимум имеет временную сложность 0(п2) и использует лишь незначительную часть исходной информации, а именно п2 элементов из общего числа п3 элементов исходной матрицы входных данных {сцк)- Формируя из исходной матрицы входных данных (с^к) множество подматриц {От} размера п х п, не имеющих общих элементов, можно получить несколько независимых решений, из которых выбирается наилучшее. Такая модификация имеет несколько большую трудоемкость, а именно 0(п2к^2п), но существенно лучшие оценки вероятности несрабатывания и относительной погрешности. Данный подход реализуется для максимизационной версии задачи. Проводится обоснование условий на входные данные, гарантирующих асимптотическую точность алгоритмов. Рассматривается многоиндексная аксиальная задача о назначении на одноциклических подстановках. Начиная с числа индексов, равного трем, существуют входы, на который задача не имеет решения. Приводится необходимое условие разрешимости задачи. Показывается достаточность этого условия для числа индексов, меньшего восьми.

Во второй главе рассматривается трехиндексная (п-слойная) планар-ная задача о назначениях. Для ш-слойной планарной задачи о назначениях, 2 < т < тг, описывается полиномиальный приближенный алгоритм. Получены условия асимптотической точности алгоритма для задач на случайных входах. Исследуются двухслойная планарная задача о назначениях с одной одноциклической подстановкой и двухслойная планарная задача о назначениях на одноциклических подстановках (случай, когда обе подстановки являются одноциклическими). Отмечается, что последняя задача представляет из себя задачу отыскания в графе двух реберно непересекающихся гамильтоновых контуров экстремального суммарного веса. Для двухслойной планарной задачи о назначениях с одной подстановкой и двухслойной планарной задачи о назначениях на одноциклических подстановках предлагаются приближенные алгоритмы, использующие идеи ранее известных алгоритмов [6, 7]. Отмечается, что для решения задач на случайных входах алгоритмы имеют условия асимптотической точности аналогичного [6, 7] вида. Исследуются метрический случай задачи отыскания в графе двух реберно непересекающихся гамильтоновых циклов минимального суммарного веса. Для задачи с одинаковой весовой функцией предлагается приближенный алгоритм с оценкой точности 9/4+0(1/п), имеющий временную сложность 0(п3). Для задачи с разными весовыми функциями строится приближенный алгоритм с оценкой точности 12/5-}-0(1/п), имеющий временную сложность 0(п3). Для задачи отыскания в графе двух реберно непересекающихся гамильтоновых циклов максимального суммарного веса с одинаковыми весовыми функциями предлагается приближенный алгоритм с константной оценкой точности 3/4, имеющий временную сложность 0(п3).

Основные результаты диссертации докладывались на Международной научной студенческой конференции (Новосибирск, 2000), Международной конференции "Дискретный анализ и исследование операций" (Новосибирск, 2000), на 12-ой Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, 2001), на Европейской конференции по комбинаторике, теории графов и их приложениях СОМВ2001 (Барселона, 2001), на международной конференции "Новые технологии и автоматизация производства" 8th IEEE (Франция, 2001), на Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003), на Международной конференции по исследованию операций OR2003 (Гейдельберг, 2003), на научных семинарах Института математики СО РАН.

Заключение

Сформулируем основные результаты проведенных исследований.

1. Рассмотрена многоиндексная аксиальная задача о назначениях. Для решения задачи предложен приближенный алгоритм, имеющий временную сложность 0(гг3). Для решения задачи на случайных входах указаны условия его асимптотической точности. Рассмотрена трехиндексная аксиальная задача о назначениях на подстановках специального вида. Исследованы случаи, когда одна подстановка является одноциклической, обе подстановки являются одноциклическими и случай, когда обе подстановки и их произведение являются одноциклическими. Для первых двух задач предложены приближенные алгоритмы, являющиеся модификациями ранее известных алгоритмов [6, 7]. Для решения задач на случайных входах приведены условия их асимптотической точности. Для третьей задачи показано, что необходимым и достаточным условием разрешимости является нечетность п. Для минимизационной и максимизационной версий задачи предлагаются полиномиальные приближенные алгоритмы. Алгоритм для задачи на минимум имеет временную сложность 0(п2) и использует лишь незначительную часть исходной информации, а именно п2 элементов из общего числа п3 элементов исходной матрицы входных данных (с^д). Формируя из исходной матрицы входных данных {сцк) множество подматриц {1)т} размера п х гс, не имеющих общих элементов, можно получить несколько независимых решений, из которых выбирается наилучшее. Такая модификация имеет несколько большую трудоемкость, а именно 0{п2\о£2п)> по существенно лучшие оценки вероятности несрабатывания и относительной погрешности. Данный подход реализован для максимизационной версии задачи. Проведено обоснование условий на входные данные, гарантирующих асимптотическую точность алгоритмов. Рассмотрена многоиндексная аксиальная задача о назначении на одноциклических подстановках. Начиная с числа индексов, равного трем, существуют входы, на который задача не имеет решения. Приведено необходимое условие разрешимости задачи. Показана достаточность этого условия для числа индексов, меньшего восьми.

2. Рассмотрена трехиндексная (п-елойная) планарная задача о назначениях. Для ш-слойной планарной задачи о назначениях, 2 < т < п, предложен полиномиальный приближенный алгоритм. Получены условия асимптотической точности алгоритма для задач на случайных входах. Исследованы двухслойная планарная задача о назначениях с одной одноцик-лической подстановкой и двухслойная планарная задача о назначениях на одноциклических подстановках (случай, когда обе подстановки являются одноциклическими). Отмечено, что последняя задача представляет из себя задачу отыскания двух реберно непересекающихся гамильтоновых контуров экстремального веса. Для двухслойной планарной задачи о назначениях с одной подстановкой и двухслойной планарной задачи о назначениях на одноциклических подстановках представлены приближенные алгоритмы, использующие идеи ранее известных алгоритмов [6, 7]. Отмечено, что для решения задач на случайных входах алгоритмы имеют условия асимптотической точности аналогичного [б, 7] вида. Исследован метрический случай задачи отыскания двух реберно непересекающихся гамильтоновых циклов минимального веса. Для задачи с одинаковой весовой функцией представлен приближенный алгоритм с оценкой точности 9/4 4-0(1/п), имеющий временную сложность 0(п3). Для задачи с разными весовыми функциями представлен приближенный алгоритм с оценкой точности 12/5 + 0(1/п), имеющий временную сложность 0(п3). Для задачи отыскания двух реберно непересекающихся гамильтоновых циклов максимального веса с одинаковыми весовыми функциями построен приближенный алгоритм с константной оценкой точности 3/4, имеющий временную сложность 0(тг3).

Список публикаций автора по теме диссертации

1. Гимади Э. X., Кайран Н. М. (Коркишко Н. М.), Сердюков

А. И. О разрешимости многоиндексной аксиальной задачи о назначениях на одноциклических подстановках // Известия высших учебных заведений, Математика, 2000, No. 12, С. 26-31.

2. Гимади Э. X., Коркишко Н. М. Об одном алгоритме решения трехиндексной аксиальной задачи о назначениях на одноциклических подстановках // Дискретный анализ и исследование операций, Сер.1, 2003, Т. 10, №2, С. 35-45.

3. Коркишко Н. М. Трехиндексная аксиальная задача о назначениях на одноциклических подстановках на максимум // Препринт института математики № ИЗ, 2003, С. 17.

4. Ageev A. A., Baburin A. Y. Gimadi Е., Korkishko N. А 3/4~ Approximation Algorithm for Finding Two Disjoint Hamiltonian Cycles of Maximum Total Weight // Annual International Conference of the German Operations Research Society, 2003, P. 122.

5. Baburin A. Y., Gimadi E., Korkishko N. An Approximation Algorithm for a Metric Problem of Finding Two Disjoint Hamiltonian Cycles of Minimum Weight // Annual International Conference of the German

Operations Research Society, 2003, P. 126.

6. Gimadi E., Kairan N. (Korkishko N.) Multi-Index Axial Assignment Problem on Single-Cyclic Permutations // EuroConference on Combinatorics, Graph Theory and Applications, 2001, P. 148-151.

7. Gimadi E., Kairan N. (Korkishko N.) Multi-Index Assignment Problem: an Asymptotically Optimal Approach f/ 8th IEEE International Conference on Emerging Technologies and Factory Automation, Proceedings, 2001, P. 707-709.

8. Gimadi E. Kh., Kairan N. M. (Korkishko N. M.), Serdyukov

A. I. Resolvability of Multi-Index Axial Assignment Problem on one-single Solution // Russian Mathematics (Iz. Vuz.), Allerton Press Inc., V. 44, No. 12, 2000, P. 19-24.

9. Korkishko N. Three-Index Axial Assignment Problem on Single-Cyclic Permutations: Feasible Solutions and Approximation Algorithms // Annual International Conference of the German Operations Research Society, 2003, P. 129.

Благодарности

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

1. Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации // Новосибирск: Наука, 1978.

2. Гимади Э. X. Задача коммивояжера на максимум: условие асим-тотической точности алгоритма "Иди в самый удаленный город" // Управляемые системы: Сб. науч. тр., Вып. 29, Новосибирск: Ин-т математики СО АН СССР, 1989, С. 11-15.

3. Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики, Москва: Наука, 1975, С. 35-42.

4. Гимади Э. X., Перепелица В. А. К задаче нахоэ/сдения минимального гамильтонового контура на графе со взвешенными дугами // Дискретный анализ, Новосибирск, Ин-т математики СО АН СССР, 1969, Вып. 15, С. 57-65.

5. Гимади Э. X., Перепелица В. А. Асимптотический подход к решению задач коммивояжера // Управляемые системы. Сб. науч. трудов, Вып. 12, Новосибирск: Ин-т математики СО АН СССР, 1974, С. 35-45.

6. Гимади Э. X., Сердюков А. И. Аксиальные трехиндекспые задачи о назначении и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ // Известия высших учебных заведений. Математика, 1999, № 12(451), С. 19-25.

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

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

9. Коробков В. К., Кричевский Р. Е. Некоторые алгоритмы для решения задачи коммивояжера // Математические модели и методы оптимального планирования, Новосибирск, Наука, 1966.

10. Кляус П. С. Обобщение тестовых задач для задачи коммивояжера // Препринт № 16, Институт математики академии наук БССР, Минск, 1976.

11. Ковалев М. М., Котов В. М. Анализ алгоритмов, конструирующих гамильтонов цикл максимального веса // Вести Академии наук БССР, Серия физ-мат. наук, 1984, № 4, С. 45-50.

12. Ковалев М. М., Котов В. М. Оценка ошибки серий приближенных алгоритмов // Вестник Белорусского государственного университета, Серия I, Физика, Математика, Механика, 1986, № 3, С. 44-48.

13. Косточка А. В., Сердюков А. И. Полиномиальные алгоритмы с оценками 3/4 и 5/6 для задачи коммивояжера на максимум // Управляемые системы. Сб. науч. тр. Вып. 26. Новосибирск: Ин-т математики СО АН СССР, 1985, С. 54-59.

14. Оре О. Теория графов // Москва, Наука, 1980.

15. Сердюков А. И. О некоторых экстремальных обходах в графах // Управляемые системы. Сб. науч. тр. Вып. 17 Новосибирск: Ин-т математики СО АН СССР, 1978, С. 76-79.

16. Сердюков А. И. Алгоритм с оценкой для задачи коммивояжера на максимум // Управляемые системы. Сб. науч. тр. Вып. 25. Новосибирск: Ин-т математики СО АН СССР, 1984, С. 80-86.

17. Сердюков А. И. Сложность решения задачи коммивояжера с предписанием на графах с малыми степенями вершин // Управляемые системы. Сб. науч. тр. Вып. 26. Новосибирск: Ин-т математики СО АН СССР, 1985, С. 73-82.

18. Сердюков А. И. Асимтотически точный алгоритм для задачи коммивояжера на максимум в евклидовом пространстве // Управляемые системы. Сб. науч. тр. Вып. 25. Новосибирск: Ин-т математики СО АН СССР, 1987, С. 79-87.

19. Сердюков А. И. Задача коммивояжера на максимум в конечномерных вещественных пространствах // Дискретный анализ и исследование операций, №1(2), 1995, С. 50-56.

20. Arora S. Probabilistic checking of proofs and the hardness of approximation problems // PhD thesis, U. C. Berkeley, 1994.

21. Arora S., Lund C. Hardness of approximation //In Approximation algorithms for NP-hard Problems, PWS Publishing, 1996.

22. Arora S., Lund C., Motwani R., Sudan M., Szegedy M. Proof verification and hardness of approximation problems // J. Assoc. Comput. Mach., 1998, no. 45, P. 501-555.

23. Arthanari T. S. On the traveling salesman problem // Communic. XI Symp. Math. Program., Bonn, 1982.

24. Arthanari T. S., Usha M. An alternative formulation of the symmetric traveling salesman problem and its properties // Discrete Appl. Math., 2000, no. 98, P. 173-190.

25. Arthanari T. S., Usha M. On the equivalence of multistage-insertion and cycle-shrink formulation for the symmetric traveling salesman problem // Oper. Res. Lett., 2001, no. 29, P. 129-139.

26. Ascheuer N. Hamiltonian Path Problem in the On-line Optimization of Flexible Manufacturing Systems // PhD thesis, Technische Universitaet Berlin, 1995.

27. Ascheuer N., Fischetti M., Groetschel M. A polyhedral study of the asymmetric traveling salesman problem with time windows // Networks, 1995, no. 36, P. 69-79.

28. Ascheuer N., Juenger M., Reinelt G. A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints // Comput. Optim. Appl., 2000, no. 17, P. 61-84.

29. Baki M. F. Solvable cases of the traveling salesman problem // Oper. Res., 1964, no. 12, P. 665-679.

30. Baki M. F., Kabadi S. N. A note of recognition of Dernidenko matrices 11 Working paper, Department of Management Sciences, University of Waterloo, 1997.

31. Balas E., Fischetti M. On the monotonization of polyhedra // Math. Program. Ser. A, 1997, no. 78, P. 59-84.

32. Balas E., Toth P. Branch and Bound Methods //In The traveling Salesman Problem: Guide Tour of Combinatorial Optimization, Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Shmoys D. B., eds., Wiley, Chichester, 1985, P. 361-401.

33. Balas E., Saltzman M. J. Facets of the three-index assignment polytope 11 Discrete Appl. Math., 1989, V. 23, no.3, P. 201-229.

34. Balas E., Saltzman M. J. An algorithm for the three-index assignment problem // Oper. Res., 1991, V. 39, no.l, P. 150-161.

35. Ball M., Magazine M. Sequencing of insertion in printed circuit board assembly // MBA thesis, Faculty of Administration, University of New Brunswick, Canada, 1995.

36. Beloni A., Lucena A. A relax and cut algorithm for the traveling salesman problem // Technical report, Laboratorio de Metodos Quantitativos, Departamento de Administracao, Universidade Federal do Rio de Janeiro, 2000.

37. Bock F. Mathematical programming solution of traveling salesman examples // Recent Advances in Mathematical Programming, McGraw-Hill, New York, 1963.

38. Burdyuk V. Y., Trofimov V. N. Generalization of the results of Gilmore and Gomory on the solution of the traveling salesman problem 11 Engg. Cybernetics, 1976, no. 11, P. 12-18.

39. Burkard R. E., Cela E. Linear assignment problem and extensions // Optimierung und Controlle, Karl-Franzens-Universitaet Gras and Technische Universitaet Graz, 1998.

40. Burkard R. E., Cela E., Pardalos P. M., Pitsoulis L. S.

41. The quadratic assignment problem // Optimierung und Controlle, Karl-Franzens-Universitaet Gras and Technische Universitaet Graz, 1998.

42. Burkard R. E., Froehlich K., Sigal I. Kh. Some remarks on 3-dimensional assignment problem // Methods of Operations Research, 1980, no.36, R 31-36.

43. Burkard R. E., Klinz F., Rudolf R. Perspective of Monge properties in optimization // Discrete Appl. Math., 1996, no. 70, P. 95-96.

44. Burkard R. E., Rudolf R., Woeginger G. J. Computational investigation on 3-dimensional axial assignment problems // Belgian J. of Oper. Res., 1993, no. 32, P. 85-98.

45. Burkard R. E., Rudolf R., Woeginger G. J. Tree dimensional axial assignment problems with decomposable cost coefficients // Discrete Appl. Math., 1996, no. 65, P. 123-169.

46. Camerini P. M., Flatta L., Maffioli F. A note of finding optimum branching // Networks, 1979, no. 9, P. 309-312.

47. Carpaneto G., Toth P. Some new branching and bounding criteria for the asymmetric traveling salesman problem ]] Manafe. Sci., 1980, no. 26, P. 736-743.

48. Carpaneto G., Toth P. Solution of the assignment problem // ACM Transactions on Math. Software, 1980, no. 6, P. 104-111.

49. Carr R. D. Polynomial separation procedures and facet determination for inequalities of the traveling salesman polytope // PhD thesis, Department of Mathematics, Carnegie Mellon University, 1995.

50. Chandrasekaran R. Recognition of Gilmore-Gomore traveling salesman problem // Discrete Appl. Math., 1986, no. 28, P. 2133-2149.

51. Chekuri C., Goldberg A., Kaeger D., Levine M., Stein C.

52. Experimental study of minimum cut algorithms j/ Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA'97), 1997, P. 324-333.

53. Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem // Technical Report CS-93-13, Carnegie Mellon University, 1976.

54. Chvatal V. Edmonds polytopes and weakly hamiltonian graphs // Math. Program., 1973, no. 5, P. 29-40.

55. Cook W. J., Cunnunghan W. H., Pulleyblank W. R., Schrijver

56. A. Combinatorial Optimization j j John Wiley and Sons, New York, 1998.

57. Cornuejols G., Fonlupt J., Naddef D. The traveling salesman problem on a graph and some related polyhedra // Math. Program., 1985, no. 33, P. 1-27.

58. Crama Y., Spieksma F. C. R. Approximation algorithms for three-dimensional assignment problems with triangle inequalities // European J. of Oper. Res., 1992, no. 60, P. 273-279.

59. Cunningham W. H., Wang Y. Restricted 2-factor polytopes // Math. Program. Ser. A, 2000, no. 87, P. 87-111.

60. Dantzig G. B., Fulkerson D. R., Jonson S. M. Solution of a large scale traveling salesman problem // Oper. Res., 1954, no. 2, P. 393-410.

61. Deineko V. G., Rudolf R., Woeginger R. E. On the recognition of permuted Supnick and incomplete Monge matrices // Acta Inform., 1996, no. 33, P. 559-569.

62. Deineko V. G., Rudolf R., Woeginger R. E. Sometimes traveling is easy: the master tour problem // SIAM J. Discrete Math., 1998, no. 11, P. 81-93.

63. Edmonds E. Path, trees and flowers // Can. J. Math., 1965, no. 17, P. 449-467.

64. Edmonds E. Matching and a polyhedron with 0,1 vertices //J. Res. N. B. S. B, 1965, no. 69, P. 125-130.

65. Edmonds E. Optimum branchings //J. Res. Natl. Bur. Stand., Sect. B, 1967, no. 71B, P. 233-240.

66. Fischetti M. An improved bound for the asymmetric traveling salesman problem // Ricerca Operativa, 1986, no. 37, P. 71-85.

67. Fischetti M., Toth P. An additive bounding procedure for combinatorial optimization problem // Oper. Res., 1989, no. 37, P. 319-328.

68. Fischetti M., Toth P. An additive bounding procedure for asymmetric traveling salesman problem // Math. Program. Ser. A, 1992, no. 53, P. 173-197.

69. Fisher M. L. Worst-case analysis of algorithms // Management Science, 1980, no. 26, P. 1-18.

70. Fisher M. L., Nemhauser G. L., Wolsey L. A. An analysis of approximations for finding a maximum weight hamiltonian circuit / / Oper. Res., 1979, no. 27(4), P. 799-809.

71. Flood M. M. The traveling-salesman problem // Oper. Res., 1956, no. 4, P. 61-75.

72. Fleischmann B. A new class of cutting planes of the symmetric traveling salesman problem // Math. Program. Ser. A, 1988, no. 40, P. 225-246.

73. Fon-Der-Flaass D. G. Array of distinkt representatives a very simple NP-hard problem // Discrete Mathematics, 1997, no. 171, P. 225-298.

74. Frieze A. M. Complexity of a 3-dimensional assignment problem // European J. of Oper. Res., 1983, no. 13, P. 161-164.

75. Frieze A. M., Yadegar L. An algorithm for solving 3-dimensional assignment problems with application to scheduling in a teaching practice // J. of the Oper. Res. Society, 1981, no. 32, P. 989-995.

76. Gabov H. ~N.An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems // In Proceedings of the 15th annual ACM symposium on theory of computing (Boston, Apr. 2527), 1983, ACM, New York, P. 448-456.

77. Garey M. R., Johnson D. S. Computers and Intractability. // San Francisco: W.H. Freeman and Company, 1979.

78. Ghosh A. P. Expected travel among random points // Bulletin Culcatta Stat. Assoc., 1948, no. 2, P. 83-87.

79. Gilmori P. C., Gomory R. E. Sequencing a one tstate-variable machine: A solvable case of the traveling salesman problem // Oper. Res., 1964, no. 12, P. 665-679.

80. Gilmori P. C., Lawler E. L., Shmoys D. B. Well-solved special cases //In The traveling salesman problem: a guided tour of combinatorial

81. Optimization, Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Shrrioys ^ D. B., eds., Wiley, Chichester, 1985, R 87-143.

82. Glover F. Ejection chains, reference structures and alternating path methods for traveling salesman problem // Discrete Appl. Math., 1996, no. 65, R 223-253.

83. Glover F. Finding a best traveling salesman 4~opt move in the same time as a best 2-opt move // J. Heuristics, 1996, no. 2(2), R 169-179.

84. Glover F., Laguna M. Tabu Search // Kluwer, Boston, 1997.

85. Goemans M. Worst-case comparison of valid inequalities for the TSP // Math. Program. Ser. A, 1995, no. 69, P. 335-349.

86. Graham R. E. Bounds for Certain Multiprocessing Anomalies // Bell System Technical J., 1966, no. 45, P. 1563-1581.

87. Groetschel M., Padberg M. W. On the symmetric traveling salesman problem I: inequalities // Math. Program., 1979, no. 16, P. 265-280.

88. Groetschel M., Padberg M. W. On the symmetric traveling salesman problem II: lifting theorem and facets // Math. Program., 1979, no. 16, P. 281-302.

89. Groetschel M., Pulleyblank W. Clique tree inequalities and the symmetric traveling salesman problem // Math. Oper. Res., 1986, no. 11, P. 537-569.

90. Gutin G. and Punnen A. P. (Eds.) The traveling salesman problem and its variations // Dordrecht, Boston, London: Kluwer Ac. Publishers, 2002.

91. Hansen P., Kaufman L. A primal-dual algorithm for the three-dimensional assignment problems // Cahiers du Cero, 1973, no. 15, P. 327-336.

92. Hassin R., Rubinstein S. An approximation algorithm for the maximum traveling salesman problem // Inform. Process. Lett., 1998, no. 67, P. 125130.

93. Held M., Karp R. M. A Dynamic Programming Approach to Sequencing Problem // J. SIAM, 1962, no. 10(1), P. 196-210.

94. Held M., Karp R. M. The traveling salesman problem and minimal spanning trees // Oper. Res., 1970, no. 18, P. 1138-1162.

95. Held M., Karp R. M. The traveling salesman problem and minimum spanning trees: part II // Math. Program., 1971, no. 1, P. 6-25.

96. Helsgaun K. An effective implementation of the Lon-Kernighan traveling salesman heuristic // Eur. J. Oper. Res., 2000, no. 12, P. 106-130.

97. Hopcroft J. E., Karp R. M. An n5/2 algorithm for maximum matchings in bipartite graphs // SIAM J. on Computings, 1973, no. 2, P. 225-231.

98. Johnson D. S. Approximation algorithms for combinatorial problems // Journal of Computing and System Science, 1974, no. 9, P. 256-278.

99. Kabadi S. N. Solution of a large scale traveling salesman problem // Oper. Res., 1954, no. 2, P. 393-410.

100. Kabadi S. N., Baki M. F. Gilmore-Gomory type traveling salesman problem // Comput. Oper. Res., 1999, no. 26, P. 329-351.

101. Karp R. M. Reducibility among combinatorial problem //In Complexity of Computer Computation, Miller R. E. and Thatcher J. W., eds., Plenum Press, New York, 1972, P. 85-103.

102. Kosaraju S. R., Park J. K., Stein C. Long tour and short superstrings // In Proc. 35rh Ann IEEE Symp. Found. Comput. Sci. (FOCS'94), 1994, P. 166-177.

103. Kurzberg J. M. On approximation methods for assignment problem // Journal of the ACM, 1962, no. 9, P. 419-439.

104. Land A. H., Doig A. G. An automatic methods of solving discrete programming problems // Econometrica, 1960, V. 28, no. 3.

105. Lawer E. L. Combinatorial optimization: Natworks and Matroids // Holt, Rinehart and Wintson, New York, 1976.

106. Lawer E. L., Lenstra J. K., Rinooy Kan A. H. G., Shmoys

107. D. B. Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization // Wiley, Chichester, 1985.

108. Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling salesman problem // Oper. Res., 1973, no. 21, P. 972-989.

109. Machol R. E. An application of the assignment problem // Oper. Res., 1970, no. 18, P. 745-746.

110. Magos D. Tabu search for the planar three-index assignment problem // J. of Global Optimization, 1996, no. 8, P. 35-48.

111. Magos D., Miliotis An algorithm for the planar three-index assignment problem // European J. of Oper. Res., 1994, no. 77, P. 141-153.

112. Marks E. S. A lower bound for the expected travel among m random points // Ann. Math. Stat., 1948, no. 19, P. 419-422.

113. Melamed I. I., Sergeev S. I., Sigal I. Kh. The traveling salesman problem -I. Theoretical issue // Automat. Remote controle, 1989, P. 11471173.

114. Melamed I. I., Sergeev S. I., Sigal I. Kh. The traveling salesman problem. Exact Algorithms // Automat. Remote controle, 1990, P. 14591479.

115. Menger K. Das Botenproblem // Ergebniss Eines Mathematischen Kolloquiums, 1932, no. 2, P. 11-12.

116. Miller D. L., Pekny J. F. Results from a parallel branch and bound algorithm for the asymmetric traveling salesman problem // Oper. Res. Lett., 1989, no. 8, P. 129-135.

117. Miller D. L., Pekny J. F. Exact solution of large asymmetric traveling salesman problems // Science, 1991, no. 251, P. 754-761.

118. Mitchell J. S. B. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems // SIAM J. Comput., 1999, no. 28, P. 1298-1309.

119. Morton G., Land A. H. A contribution to the "Traveling-Salesman "problem // J.D. Stat. Soc., Ser. B, 1955, no. 17, P. 185-203.

120. Naddef D., Rinalde G. The symmetric traveling salesman problem polytope and its graphical relaxation: Composition of valid inequalities // Math. Program. Ser. A, 1991, no. 51, P. 359-400.

121. Naddef D., Rinalde G. The crown inequalities for the traveling salesman polytope // Math. Oper. Res., 1992, no. 17, P. 308-326.

122. Naddef D., Rinalde G. The graphical relaxation: a new framework for the symmetric traveling salesman polytope // Math. Program. Ser. A, 1993, no. 58, P. 53-88.

123. Naddef D., Rinalde G. The symmetric traveling salesman polytope: New facets from the graphical relaxation // Technical report, Laboratoire ID-IMAG, 2000.

124. Padberg M. W., Rinalde G. An efficient algorithm for the minimum capacity cut problem // Math. Program. Ser. A, 1990, no. 47, P. 19-36.

125. Padberg M. W., Sung T. Y. An analytical comparison of different formulations of the traveling salesman problem // Math. Program. Ser. A, 1991, no. 52, P. 315-357.

126. Papadimitriu C. H., Yannakakis M. Optimization, approximation, and complexity classes // Journal of Computer and System Sciences, 1991, V. 43, P. 425-440.

127. Park J. K. A special case of the n-vertex traveling salesman problem that can be solved in 0(n) time // Inform. Process., 1991, no. 25, P. 247-254.

128. Pierskalla W. P. The tri-substitution method for the three-multidimensional problem // Canadian ORS Journal, 1997, no.-5, P. 71-81.

129. Pierskalla W. P. The multidimensional assignment problem // Oper. Res., 1968, no. 16, P. 422-431.127. f

130. Poore A. B., Robertson III A. J. A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems // Computational Optimization and Applications, 1997, no. 8, P. 129-150.

131. Punnen A. P., Glover F. Implementing ejection chains with combinatorial leverage for the TSP J/ Research Report, University of Colorado-boulder, 1996.

132. Rego C. Relaxed tours and path ejection for the traveling salesman problem 11 Eur. J. Oper. Res., 1998, no. 106, P. 522-538.

133. Reineld G. The Traveling Salesman: Computational Solutions for TSP Applications // Springer-Verlag, Berlin, 1994.

134. Rinnoy Kan A. H. G. An introduction to the analysis of approximation algorithms // Discrete Appl. Math., 1986, no. 14, P. 171-186.

135. Robinson J. B. On the Hamiltonian game: a traveling salesman problem II Theoretical report, RAND Research Memorandum RM-303, 1949.

136. Sahni S. General technique for combinatorial approximation // Oper. Res., 1969, no. 14, P. 1005-1016.

137. Sahni S., Gonzales T. P. P-Complete Approximation Problem // Assoc. Comput. Mach., 1976, V. 23, no. 3, P. 555-565.

138. Shmoys D. Computing near-optimal solutions to combinatorial optimization problem // Comutiong, 1982, no. 28, P. 257-267.

139. Slominski D. Computing near-optimal solutions to combinatorial optimization problem //In Advances in Combinatorial Optimization, Cook W., Lovasz L., Seymour P., eds., Ams, Providence RI, 1995, P. 335-397.

140. Tarjan R. E. Finding optimum branchings // Networks, 1977, no. 7, P. 25-35.

141. Trevisan L. When Hamming meets Euclid: the approximability of geometric TSP and MST //In Proc. 29th ACM Symp. Theory Comput., 1997, P. 27-39.

142. Vlach M. Branch and bound method for the three-index assignment problem // Ekonomicko-Matematicky Obzor, 1967, no. 12, P. 181-191.

143. Wolsey L. A. Integer Programming // Wiley, Chichester, 1998.