Комплекс программ для исследования методов решения задачи о коммивояжере тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Ляликов, Вадим Николаевич

• Ляликов, Вадим Николаевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Ляликов, Вадим Николаевич

Оглавление.

Введение.

Глава 1. Современные методы решения задачи о коммивояжере.

§1.1. Формулировки ЗКВ. I 1 I I ' i ' ' '

§1'.12\| Алгоритмы и методы решения ЗКВ.

§1.3. Средства решения ЗКВ.

§1.4. Замечания о проведении вычислительных экспериментов.

Глава 2. Методы приближенного решения ЗКВ.

§2.1. Стабильная аппроксимация Л-ЗКВ.

2.1.1 Формальное описание алгоритма РМСА.

2.1.2. Экспериментальное исследование алгоритма РМСА.

2.1.3. Результаты вычислительных экспериментов.

Введение диссертации (часть автореферата) на тему «Комплекс программ для исследования методов решения задачи о коммивояжере»

Актуальность исследования. Задача о коммивояжере - traveling salesman problem (TSP, 3KB) - является NP-сложной задачей дискретной оптимизации [1]. Для нее не найдено и возможно не существует быстрых полиномиальных алгоритмов. На графах она формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе [76]. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.

Поиск точных и приближенных способов решения задачи о коммивояжере остается актуальным и с теоретической и с практической точек зрения. Результатом теоретических исследований являются такие методы [63] как:

• релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, метод ветвей и границ

• распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)

• эвристические: симулированный отжиг, генетические алгоритмы, цепная локальная оптимизация, поиск с запретами.

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

Программные коды, предназначенные для решения на оптимальность задачи о коммивояжере, за последние 30 лет развились от решения задач размерности 100 до 10 ООО.

Среди приложений ЗКВ, встречающихся в литературе, можно отметить:

• Оптимизацию в сетях

• Оптимизацию маршрутов

• Приложения в кристаллографии

• Управление роботами

• Обработку печатных плат

• Исследование ДНК

Городами» в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности.

Основными актуальными вопросами, связанными с решением ЗКВ, являются

• Быстрое точное решение асимметричных и. симметричных ЗКВ больших размерностей

• Быстрое приближенное решение асимметричных и симметричных ЗКВ больших размерностей

• Разработка быстрых схем аппроксимации ЗКВ высокой точности Диссертация посвящена новым подходам к решению этих задач: разработке новых алгоритмов и оптимизации существующих решений. Цель работы. Целью настоящей работы является

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

• реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ

• улучшение качества тура и ускорение существующих программ решения ЗКВ

• поиск новых способов эффективного использования существующего программного обеспечения (ПО) по решению ЗКВ

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

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

Для достижения поставленных целей решены следующие задачи:

1. Разработан алгоритм решения асимметричной задачи о коммивояжере (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжере (СЗКВ, STSP). Выработаны рекомендации по применению.

2. Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ РМСА [35].

3. Реализован алгоритм усеченного МВГ ZHANG1 [88] с задачей о назначениях для АЗКВ. Получены оценки времени работы и качества тура. Выработаны рекомендации по применению.

4. Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (MB О, Branch and Cut) [54] и эквивалентных преобразований в приближенных k-opt [56] алгоритмах для АЗКВ. По результатам выработаны рекомендации по> оптимизации времени и качества тура.

5. Экспериментально исследована эффективность отсечений ЗКВ для решения задачи, маршрутизации (Vehicle Routing Problem - VRP). Подтверждена эффективность подхода.

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

Основные положения, выносимые на защиту:

1. Новый алгоритм решения асимметричной задачи о коммивояжере путем неэквивалентного преобразования к симметричной задаче о коммивояжере.

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

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

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

Основные научные и практические результаты исследований по теме диссертации докладывались на

• VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г. Ульяновск, 2005)

• «XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г. Йошкар-Ола, 2006)

• девятом международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2007)

По теме диссертации опубликовано 10 работ. Личный вклад. В работе использовались теоретические и практические разработки отечественных и зарубежных авторов.' Формулировка новых алгоритмов, построение схем вычислительных экспериментов, программная реализация алгоритмов, анализ полученных результатов и обоснование выводов выполнены соискателем самостоятельно.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ляликов, Вадим Николаевич

Вывод:

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

§3.4. Комплекс программ Описание программного комплекса

В рамках диссертационной работы разработан комплекс программ. Он реализован в виде набора взаимосвязанных классов на языке С++ (набора классов импорта/экспорта и базовых операций над матрицами, а также решателей - переборного SimpleSolver, распределенного МВГ, неэквивалентного преобразования АЗКВ -> СЗКВ; эвристики Жанга, оболочки конкорда и других), нескольких программ и библиотек сторонних разработчиков. Все использовавшееся программное обеспечение распространялось свободно (по крайней мере, для академического использования) и с открытыми исходными текстами. Последний пункт являлся важным критерием при подборе библиотек и программ, так как позволял вносить лишь необходимые модификации, основываясь на уже разработанном и оттестированном коде, как например, реализация схемы аппроксимации РМСА на основе реализации эвристики Кристофидеса из пакета GOBLIN.

Разработка академического программного обеспечения в рамках парадигмы свободного программного обеспечения (СПО) является современной тенденцией и поддерживается влиятельными учебными заведениями, например, Университетом Беркли, и крупными коммерческими компаниями, такими как IBM. Как отмечается в [67], использование СПО и разработка нового ПО в рамках СПО позволяет уменьшить недостатки присущие стандартной схеме разрабатываемого в рамках научных исследований ПО:

• Результаты невоспроизводимы.

В отличие, например, от детально описываемых физических экспериментов, программы характеризуются не только- сложностью алгоритмов, но и эффективностью реализации. Показателен пример Кармаркара [67].

• Пристрастность сравнений.

Авторам программ приходится сравнивать «мою реализацию вашей идеи» и «мою реализацию моей идеи»

• Модели и реализации теряются

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

• Развитие тормозится

Без обмена идеями и решениями развитие в области идет медленнее.

• «Велосипеды изобретаются заново»

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

• Обмен знаниями ограничен

Часто новые теоретические разработки для одного класса задач можно применять и для других классов. Если программные реализации закрыты - перенос невозможен.

• Сотрудничество затруднено недостатком стандартов

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

Несмотря на то, что наиболее известными программами СПО являются низкоуровневые приложения, такие как GNU/Linux (операционная система), apache (веб сервер), bind (сервис доменных имен), Perl (скриптовый язык), что в значительной степени связано с гораздо более широкой целевой аудиторией, в рамках исследовательских работ, находящихся обычно на среднем и высоком уровнях стэка, и разрабатываемых ограниченным сообществом, эта парадигама также оказывается эффективной [67].

В рамках диссертационной работы было проведено исследование СПО средств решения задач ЛП и ЦЛП, являющихся важными элементами реализаций алгоритмов Branch & Cut и Branch & Price. Результаты вычислительных экспериментов показали, насколько затратным по времени и проблематичным по качеству результата является процесс разработки крупных СПО проектов.

Как указано! в обзоре [65], существует множество закрытых и несколько открытых программных продуктов для решения указанных задач.

Целью одного из этапов работы было сравнение возможностей и производительности свободных библиотек целочисленного линейного программирования (ЦЛП). Сравнивались два наиболее крупных пакета с открытой лицензией, способных решать задачи ЦЛП: GLPK (GLKP 4.8) и lpsolve (lpsolve 5.1). Примеры задач ЦЛП для тестирования были выбраны с учетом доступности, что позволяет сравнивать результаты с другими работами. В отчете представлены данные для задач из набора, предложенного профессором Гансом Миттелманом [70] . В [70] не использовалась библиотека lpsolve, но представлены результаты для нескольких закрытых, не рассматривающихся здесь . Тесты проводились на машине: Athlon 2000+, 512 Mb DDR SDRAM (памяти было достаточно для проведения всех тестов), OS GNU/Linux 2.4

Параметры тестовых задач, такие как число строк, столбцов, целых и ненулевых переменных, можно посмотреть в [70].

Затраты времени на решение задач приведены на (рис. 4.1) Стандартный решатель lpsolve не справился с некоторыми задачами и выдавал сообщение об этом по истечении определенного времени. Такие случаи отмечены вертикальными линиями вместо точек.

В заключение можно отметить, что как и указано в [68], используемые в библиотеке вЬРК алгоритмы еще не полностью проработаны и слабо оптимизированы, что проявляется в существенном проигрыше по времени некоторым закрытым аналогам. Также были выявлены проблемы со стабильностью вычислений, особенно у библиотеки 1рБо1уе. Если же рассматривать только открытые реализации, то ОЬРК на данный момент является предпочтительной для использования и доработки. А в целом сравнение ОЬКР и 1рБо1уе показывает, насколько затратным и сложным процессом является разработка современных новых ЛП-решений.

3000 к 2500 s 2000 Q)

1500 а; 1000 Q. ш

500 0

Решение задач ЦЛП. GLPK и lpsolve

- In snlvfí / - 1

GLPK ^ nug08 irp mas284 bienstl dano33 dano34markshare11

Задача,название

Рис 4.1. Время решения задач ЦЛП, с

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

Список основных использовавшихся библиотек и программ (в скобках отмечены основные критерии, по которым программное обеспечение подбиралось):

• С++, stl - язык и библиотеки (удобная реализация стандартных алгоритмов со стандартными типами данных, например, со строками; механизм шаблонов, позволяющий создавать шаблоны алгоритмов и типов данных, например, алгоритмов сортировки и очередей, специфичных для задачи; удобство создания объектно-ориентированной модели приложения и ее реализации; относительная простота интеграции с кодами сторонних разработчиков, которые в основном были реализованы на языках ANSI С и С++)

• PVM — библиотека распределенных вычислений (для распределенных вычисления в гетерогенных сетях) (промышленный стандарт, оттестированный и переносимый)

• libhungarian - библиотека для решения задачи о назначениях (оттестированность, компактность)

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

• concorde - программа решения ЗКВ. Использовалась для решения ЗКВ на оптимальность средствами ветвей и границ (лучший по производительности код В&С оптимизации ЗКВ на 2008 год), и получения нижних оценок ЗКВ - границы Хелда-Карпа.

• LKH - программа приближенного решения ЗКВ (один из лучших по качеству тура и времени работы алгоритмов приближенного решения ЗКВ на 2008)

• Каркас SYMPHONY и приложение VRP из набора программ COIN-OR - средств СПО для создания решателей МВГ, МЕЮ (Branch & Cut), Branch & Price.

Входом каждого решателя является матрица симметричной или асимметричной задачи о коммивояжере в формате TSPLIB [81] или во внутреннем формате. Выходом является значение стоимости найденного тура и опционально сам тур. При необходимости перед передачей матрицы на вход Solver'а она может быть преобразована в эквивалентную или в матрицу специального формата. Например, из асимметричной в симметричную. Соответственно после того, как Solver выдаст решение, оно должно будет пройти соответствующую постобработку. Например, вычитание стоимостей, добавленным к ребрам в 2-node АЗКВ-»СЗКВ преобразователе.

Заключение

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

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

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

На научную новизну претендуют:

1. Новый алгоритм решения асимметричной задачи о коммивояжере путем неэквивалентного преобразования к симметричной задаче о коммивояжере.

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

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

Основными результатами работы по разработке и улучшению методов и программных средств решения ЗКВ являются:

1. уменьшение времени работы (увеличение скорости решения) в случае точных методов

2. уменьшение времени работы и уменьшение длины тура в случае приближенных методов

Для нескольких алгоритмов, например, для полиномиальной схемы аппроксимации симметричной ЗКВ, впервые были получены экспериментальные оценки времени работы и качества тура.

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

Созданный комплекс программ зарегистрирован в Отраслевом фонде алгоритмов и программ.

Список литературы диссертационного исследования кандидат технических наук Ляликов, Вадим Николаевич, 2008 год

1. Алгоритмы. Построение и анализ Текст. / Т. Кормен [и др.] ; пер. с англ. И. В. Красикова, Н. А. Ореховой, В. Н. Ромашова. 2-е изд. - М. : Вильяме, 2005. - 1290 с.

2. Ашманов С. А. Линейное программирование Текст. : учеб. пособие для вузов / С. А. Ашманов. М. : Наука, 1981. - 304 с.

3. Воденин Д. Р. Эвристика Жанга для асимметричной задачи коммивояжера' Текст. / Д. Р. Воденин, В. Н. Ляликов // Обозрение прикладной и промышленной математики. 2006. - Т. 13, Вып. 6. - С. 1062-1063.

4. Воеводин В. В. Параллельные вычисления Текст. : учеб. пособ. для студентов вузов, обучающихся по направлению 510200 "Прикладная математика и информатика" / В. В. Воеводин, Вл. В. Воеводин. СПб. : БХВ-Петербург, 2002. - 599 с.

5. Гудман С. Введение в разработку и анализ алгоритмов Текст. / С. Гудман, С. Хидетниеми ; пер. с англ. Ю. Б. Котова [и др.]. М. : Мир, 1981.-366 с.

6. Информационные материалы, посвященные высокопроизводительным и параллельным вычислениям Электронный ресурс. / Всероссийский Информационно-Аналитический Центр по параллельным вычислениям. -Режим доступа: http://parallel.ru/.

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

8. Ляликов В. Н. Получение решений близких к симметричным ATSP преобразованием к STSP Текст. / В. Н. Ляликов // Обозрение прикладной и промышленной математики. — 2006. Т. 13, Вып. 6. - С. 1094-1095.

9. Ляликов В. Н. Неравенства задачи о коммивояжере для задачи маршрутизации Текст. / В. Н. Ляликов // Обозрение прикладной и промышленной математики. — 2008. Т. 15, Вып. 1. - С. 154.

10. Ляликов В. Н. Оптимизация локального поиска для асимметричной задачи о коммивояжере Текст. / В. Н. Ляликов // Обозрение прикладной и промышленной математики. 2008. - Т. 15, Вып. 1. - С. 154-155.

11. Ляликов В. Н. Методы линейного программирования для решения асимметричной задачи коммивояжера Текст. / В. Н. Ляликов // XV Туполевские чтения : междунар. молодеж. науч. конф. Казань : КГТУ, 2007. - Т. II. - С. 87-88.

12. Ляликов В. Н. О локальных отсечениях для задачи о коммивояжере Текст. / В. Н. Ляликов // Информационно-математические технологии в экономике, технике и образовании : материалы конф. Екатеринбург : УПИ, 2007. - С. 34-36:

13. Ляликов В. Н. Программный комплекс для проведения вычислительных экспериментов с целью исследования методов решения симметричной и асимметричной задачи коммивояжера : ЕСПД 03524577.02165-01 Текст. /

14. B. Н. Ляликов // Программное и информационное обеспечение поддержки научно-исследовательских работ. — М. : ВНТИЦ, 2007.

15. Схрейвер А. Теория линейного и целочисленного программирования Текст. : в 2-х т. / А. Схрейвер ; пер. с англ. С. А. Тарасова, М. А. Фрумкина, В. И. Шлыка ; под ред. Л. Г. Хачияна. М. : Мир, 199Г.

16. Харари Ф. Теория графов Текст. / Ф. Харари ; пер. с англ. и предисл. В. П. Козырева ; под ред. Г. П. Гаврилова. 3-е изд. — М. : КомКнига, 2006. -300 с.

17. Ху Т. Целочисленное программирование и потоки в сетях Текст. / Т. Ху ; пер. с англ. П. Л. Бузыцкого [и др.] ; под ред. и с предисл. А. А. Фридмана. -М. : Мир, 1974.-519 с.

18. Aardal К. Polyhedral Techniques in Combinatorial Optimization Текст. / К. Aardal, S. van Hoesel // Statistica Neerlandica : orgaan van de Vereniging voor Statistiek. 1996. - № 50. - P. 3-26.

19. Andaljayalakshmi G. A hybrid genetic algorithm a new approach to solve traveling salesman problem Текст. / G. Andaljayalakshmi, S. Sathiamoorthy,

20. R. Rajaram // International Journal of Computational Engineering Science. -2001. Vol. 2, №2.-P. 339-355.

21. Applegate D. "Finding Cuts in the TSP" : a preliminary report Текст. / D. Applegate, R. Bixby // DIMACS Technical Report. 1995. - P. 95-105.

22. Applegate D. TSP cuts outside the template paradigm Электронный,ресурс. /. D. Applegate, R. E. Bixby, V. Chvatal.// Technical report, Computer Sciences, Rutgers University. — Режим доступа : http://www.cs.rutgers.edu/~chvatal/dagstuhl.ps, 2000.

23. Applegate D. Chained Lin-Kernighan for large traveling salesman problems Текст. / D. Applegate, W. Cook, A. Rohe // INFORMS J. Comput. 2003. -Vol. 15.-P. 82-92.

24. Arora S. Polynomial Time Approximation Schemes for Euclidian Traveling Salesman and Other Geometric Problems Текст. / S. Arora // Journal of the ACM. 1998. - Vol.- 45, № 5. - P. 753-782.

25. Balas E. Polyhedral theory for the asymmetric traveling salesman problem Текст. / E. Balas // The traveling salesman problem and its variations / edited by G. Gutin, A. Punnen. Dordrecht: Kluwer Academic Publishers, 2002. - P. 117-168.

26. Balas E. Branch and bound methods Текст. / E. Balas, P. Toth // The Traveling Salesman Problem / edited by E. L. Lawler, J. K. Lenstra. John Wiley & Sons Ltd, 1985. - P. 361-401.

27. Baumann F. ABACUS. A Branch-And-CUt System Электронный ресурс. / F. Baumann. Version 3.0 // User's Guide and Reference Manual. - Режим доступа: http://www.informatik.uni-koeln.de/abacus/, 2007.

28. Bentley J. L. Fast algorithms for geometric traveling salesman problems Текст. / J. L. Bentley // ORSA. Journal on Computing. 1992. - Vol. 4. -P. 387-411.

29. Blasum U. Application of the Branch and Cut Method to the Vehicle Routing Problem Текст. / U. Blasum, W. Hochstattler // Zentrum fiir Angewandte Informatik Koln Technical Report. 2000. - P. 386.

30. Bockenhauer H.-J. Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem Текст. / H.-J. Bockenhauer, J. Hromkovic, R. Klasing // Theoretical Computer Science. -2002. № 285. - P. 3-24.

31. Bockenhauer H.-J. Improved lower bounds on the approximability of the traveling salesman problem Текст. / H.-J. Bockenhauer, S. Seibert // RAIRO Theoretical Informatics and Applications. 2000. - Vol. 34. - P. 213-255.

32. Caprara A. {1, /4}-Chvatal-Gomory Cuts Текст. / A. Caprara, M. Fischetti // Mathematical Programming. Series A and B. 1966. - Vol. 74, № 3. - P. 221<-235.

33. Christine L. Valenzuela Estimating the Held-Karp lower bound for the geometric TSP Текст. / L. Christine Valenzuela, J. Jones. Antonia' // University of Wales. -2001.-12 July.

34. Cirasella J. The asymmetric traveling salesman problem : algorithms, instance generators, and tests, ALENEX 2001 proceedings Текст. / J. Cirasella, D. S. Johnson, L. A. McGeoch // Springer Lecture Notes in Computer Science. P. 32-59.

35. Concorde (a computer code for the symmetric traveling salesman problem (TSP) and some related network optimization problems) webpage Электронный ресурс. Режим доступа : http://www.tsp.gatech.edu/concorde.html.

36. Dahl G. An introduction to convexity, polyhedral theory and combinatorial optimization Текст. / G. Dahl. University of Oslo, 1997.

37. Diestel R. Graph Theory Текст. / R. Diestel. New York : Springer-Verlag, 1997.

38. DIMACS 8th Implementation Challenge Электронный ресурс. Режим доступа: http://www.research.att.com/~dsj/chtsp.

39. Fischetti М. Local branching Текст. / M. Fischetti, A. Lodi // Math. Program. Ser. B. 2003. - Vol. 98. - P. 23-47.

40. Fortini M. LP-based heuristics for the traveling salesman problem Текст. / M. Fortini // Dottorato di Ricerca in Automatica e Ricerca Operativa (MAT/09). -Universita.degli studi di Bologna, 2007.

41. Fredman M. L. Data structures for traveling salesman Текст. / M. L. Fredman, D. S. Johnson, L. A. McGeoch. // Journal of Algorithms. 1995. — Vol. 18. -P. 432-479.

42. Fugenschuh A. Computational Integer Programming and Cutting Planes Текст. / A. Fugenschuh, A. Martin // Handbooks in Operations Research and Management Science, Kluwer. 2005. - P. 69-122.

43. Geist A. PVM : Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing Текст. / A. Geist, A. Beguelin, J. Dongarra. -Cambridge : The MIT Press, 1994.

44. Geist G. A. PVM and MPI: a Comparison of Features / G. A. Geist, J. A. Kohl, P. M. Papadopoulos Текст. // Calculateurs Paralleles. 1996. - Vol. 8(2).-P. 137-150.

45. GOBLIN Graph Library 2.8Ы6 : GOBLIN is a С++ class library focussed on graph optimization and network programming problems. Reference Manual,

46. February 4, 2007 Электронный ресурс. Release 2.8. - Режим доступа : http://www.math.iini-augsburg.de/~fremuth/goblin.html, 2007.

47. Grötschel M. Padberg Polyhedral theory Текст. /М. Grötschel // The Traveling Salesman Problem / edited by E. L. Lawler, J. K. Lenstra. Hoboken : John Wiley & Sons Ltd, 1985. - P. 251-305.

48. Haupt R. L. Practical genetic algorithms Текст. / R. L. Haupt, S. E. Haupt. -Hoboken : John Wiley & Sons, 2004. 253 p.

49. Helsgaun, K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic Текст. / К. Helsgaun // DATALOGISKE SKRIFTER (Writings on Computer Science). 1998. - № 81.

50. Hromkovic J. Algorithmics for Hard Problems Текст. / J. Hromkovic. 2-nd edition. - Springer, 2003.

51. Johnson D. S. Experimental.analysis of heuristics for the STSP Текст. / D. S. Johnson, L. A. McGeoch // The traveling salesman problem and its variations / edited by G. Gutin, A.'Punnen. Dordrecht : Kluwer Academic Publishers, 2002.-P. 369-443.

52. Junger M. The Design of the Branch-and-Cut System ABACUS Текст. : technical report / M. Junger, S. Thienel ; Institut fur Informatik, Universität zu Köln. Köln, 1997.

53. Kindervater G. A. P. Parallel local search for the time-constrained traveling salesman problem Текст. / G. A. P. Kindervater, J. K. Lenstra, M. W. P. Savelsbergh // European* Journal of Operational Research. Vol. 33 (1988). - P. 65-81.

54. Ladanyi L. Introduction to BCP MCF Example Электронный ресурс. : web document 2006 / L. Ladanyi, F. Margot. - Режим доступа : http://dimacs.rutgers.edu/Workshops/COIN/slides/bcp tutorial.pdf

55. Lecture : The Traveling Saleman Problem Текст. / W. Cook // INFORMS Annual Meeting. Miami. 2001. - November 5.

56. Lecture : TSP Cuts that do not follow the template paradigm, Combinatorial Optimization and Integer Programming Текст. / V. Chvatal. The State of the Art Columbia University. - 2001, November 28.

57. Linear Programming Frequently Asked Questions Электронный ресурс. — Режим доступа : http://www-unix.mcs.anl.gov/otc/Guide/faq/Hnear-programming-faq.html, September 2, 2004

58. Lodi A. TSP software Текст. / A. Lodi, A. P. Punnen // The traveling salesman problem and its variations / edited by G. Gutin, A. Punnen. Dordrecht : Kluwer Academic Publishers, 2002. - P. 737-749.

59. Lougee-Heimer R. The Common Optimization INterface for Operations Research Текст. / R. Lougee-Heimer // IBM Journal of Research and Development. Mathematical Sciences. 2003. - Vol. 47, № 1. - P. 57-66.

60. Makhorin A. GNU Linear Programming Kit Электронный ресурс. / A. Makhorin // Reference Manual, version 4.8. Moscow Aviation Institute 2005. -Режим доступа : http://www. gnu.msn.bv/people/people.html.

61. Mitchell J. E. Branch-and-Cut Algorithms for Combinatorial Optimization Problems Текст. : handbook of Applied Optimization / J. E. Mitchell. -Oxford University Press, 2000.

62. Mittelmann H. Mixed Integer Linear Programming Benchmark (free codes) Электронный ресурс. / H. Mittelmann. Режим доступа : ftp://plato.la.asu.edu/pub/milpf.txt., May 18, 2005.

63. Moore A. W. An introductory tutorial on kd-trees : Текст. extract from A. Moore's PhD Thesis : Efficient Memory-based learning for robot control : technical Report, No. 209 / A. W. Moore ; Computer Laboratory, University of Cambridge, 1991.

64. Padberg M. W. Polyhedral computations Текст. / M. W. Padberg, M. Grotsche7

65. The Traveling Salesman Problem / edited by E. L. Lawler et al.. Hoboken : John Wiley & Sons Ltd, 1985. - P. 307-360.

66. Parberry I. Problems on Algorithms Электронный ресурс. / I. Parberry, W. Gasarch. 2-е edition. — Режим доступа : http://www.eng.unt.edu/ian/books/poa.html, 2002.

67. Punnen A. P. The traveling salesman problem Текст. : applications, formulations and variations / A. P. Punnen // The traveling salesman problem and its variations / edited by G. Gutin, A. Punnen. Dordrecht : Kluwer Academic Publishers, 2002. - P. 1-28.

68. Ralphs Т. K. Parallel Branch and Cut for Capacitated Vehicle Routing Текст. / Т. К. Ralphs // Parallel Computing. 2003. - Vol. 29. - Issue 5. - P. 607 - 629.

69. Ralphs Т. K. SYMPHONY 5.1.4 User's Manual Электронный ресурс. / Т. К. Ralphs. Режим доступа : www.branchandcut.org/SYMPHQNY, 2007.

70. Ralphs Т. К. Capacitated Node Routing Problem Электронный ресурс. / Т. К. Ralphs, J. С. Hartman. Режим доступа : http://coral.ie.lehigh.edu/~ted/files/papers/CNRP.pdf, 2001.

71. Ralphs Т. К. An improved algorithm for solving biobjective integer programs Текст. / Т. К. Ralphs, M. J. Saltzman, M. M. Wiecek // Annals of Operations Research. 2006. - Vol. 147, № 1. - P. 43 - 70.

72. Reinelt G. TSPLIB A Traveling Salesman Problem Library Текст. / G. Reinelt// ORSA J. Comput. - 1991.-№ 3/4.-P. 376-385.

73. Sedgewick R. Algorithms Текст. / R. Sedgewick. Addison-Wesley, 1984. 83.Sleator D.D. Self-adjusting binary search trees [Текст] / D. D. Sleator, R. E. Taijan // J. ACM. - 1985. - № 32. - P. 652-686.

74. Stroustrup В. The С++ Programming Language third ed. Текст. / В. Stroustrup // AT&T Labs Murray Hill. New Jersey, 1997.

75. TSPLIB homepage Электронный ресурс. Режим доступа : http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

76. Usami Y. Traveling salesman problem and statistical physics Текст. / Y. Usami, M. Kitaoka // International Journal of Modern Physics. Vol. 11, No. 13 (1997).-P. 1519-1544.

77. Zhang W. Depth-First Branch-and-Bound versus Local Search Текст. : a Case Study / W. Zhang // Proc. 17th National Conference on Artificial Intelligence (AAAI-2000). Austin : Texas, 2000. - P. 930-935.

78. Zhang W. Truncated Branch-and-Bound Текст. : a Case Study on the Asymmetric TSP / W. Zhang // Proc. AAAI 1993 Spring Symp. AI and NP-Hard Problems. Stanford : CA, 1993. - P. 160-166.

79. Website for the DIMACS : implementation Challenge on the Traveling Salesman Problem Электронный ресурс. / D. S. Johnson [et al.]. Режим доступа: http://www.research.att.com/~dsi/chtsp/