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

Список иллюстраций.

Список таблиц.

Список сокращений.

Введение.

Глава 1. Обзор проблематики и постановка задачи.

Введение.

Язык программирования Пролог.

Механизм доказательства в Прологе.

Задача удовлетворения ограничениям (Constraint Satisfaction Problem).

Представление ограничений.

Алгоритмы разрешения ограничений.

Алгоритмы распространения ограничений.

Метод ветвей и границ.

Открытие середины 90х годов: фазовые переходы в комбинаторных задачах

Постановка задачи исследования.

Преобразование задачи коммивояжера в BCSP.

Преобразование задачи коммивояжера в CSP.

Приближенные методы решения задачи коммивояжера.

Выводы по главе 1.

Глава 2. Анализ поведения метода ветвей и границ при появлении фазового перехода и разработка методов решения в условиях фазового перехода.

Раздел 2.1 Особенности метода ветвей и границ при решении задач с топологическими особенностями класса I.

Топологические особенности.

Особенности решения.

Методы кластеризации.

Анализ топологии.

Гипотеза о природе фазового перехода от топологии.

Оценка вероятности появления топологических особенностей.

Выводы по разделу 2.1.

Раздел 2.2. Особенности метода ветвей и границ при решении задач с топологическими особенностями класса II.

Топологические особенности класса II.

Экспериментальные результаты.

Анализ топологии.

Анализ работы метода ветвей и границ на задачах топологическими особенностями класса II.

Возможные модификации.

Геометрическая интерпретация.

Анализ сложности и точности решения приближенным алгоритмом.

Выводы по разделу 2.2.

Раздел 2.3. Метод ветвей и границ при решении комбинаторных задачах с топологическими особенностями.

Задача коммивояжера.

Квадратическая задача о назначении.

Задача о 0/1 рюкзаке.

Фазовые переходы.

Влияние топологических особенностей на время решения методом ветвей и границ.

Выводы по разделу 2.3.

Раздел 2.4. Методы декомпозиции.

Изменение граничного значения и уровня значимости.74

Алгоритм с учетом декомпозиции.75

Иерархическая декомпозиция».77

Выводы по разделу 2.4.78

Раздел 2.5. Метод интеллектуального возврата.80

Введение.80

Использование топологических особенностей исходных данных.80

Подход 1.81

Подход 2.82

Алгоритм интеллектуального возврата.84

Результаты тестирования.85

Выводы по разделу 2.5.86

Выводы по главе 2.88

Глава 3. Разработка прототипа constraint системы.89

Раздел 3.1. Введение.89

Интеграция методов в Пролог-подобную систему.90

Выводы по разделу 3.1.91

Раздел 3.2. Разработка прототипа constraint системы.92

Этапы разработки.92

Разработка идеологии Пролог -подобной системы.92

Структура данных языка Пролог.93

Синтаксический и семантический анализ при преобразовании данных.100

Синтаксический и семантический анализ «Выражения».101

Алгоритм доказательства цели.103

Алгоритм доказательства предиката.105

Алгоритм возврата.107

Выводы по разделу 3.2.109

Раздел 3.3. Интеграция методов разрешения constraint.110

Абстрактная Машина Варрена.110

Использование объектно-ориентированного подхода.110

Интеграция методов решения задачи удовлетворения ограничениям.111

Выводы по разделу 3.3.117

Выводы по главе 3.117

Глава 4. Проверка применимости предложенного подхода.118

Оценка времени вычисления и точности реализованных методов, сравнение с приближенными и точными подходами.118

Сравнение с существующим программным комплексом.120

Задача коммивояжера.120

Задача кумулятивного расписания.121

Задача о 0/1 рюкзаке.128

Выводы по главе 4.130

Заключение.131

Направления дальнейших исследований.131

Научные положения работы.133

Обобщенные результаты по некоторым главам.134

Список литературы.136

Приложение 1. Статистические методы.146

Поиск начального кластера.146

Критерий согласия Колмогорова-Смирнова.146

Статистический критерий Стьюдента.147

Список иллюстраций

1. Рис. 1. Частота использования ребер длиной от 0 до 1 методом ветвей и границ при топологии класса I на матрице, нормированной на [0, 1]

2. Рис. 1.1. Структура constraint системы

3. Рис. 2.1 «Строгая» кластеризация

4. Рис. 2.2. Частота исследования ребер длиной от 0 до 1 при решения задачи коммивояжера с топологическими особенностями методом ветвей и границ

5. Рис. 2.3. Частота исследования ребер длиной от 0 до 1 при решения задачи коммивояжера без топологических особенностей методом ветвей и границ

6. Рис. 2.4 Поиск решения методом ветвей и границ в матрице с топологическими особенностями

7. Рис. 2.5. Оценка среднего количество кластеров из диапазонов [1, 5], [6, 10], [11, 15] и [16, 20] на матрицах от 50x50 до 250x250

8. Рис. 2.6. Вероятность появления кластеров "от 11x11 до 15x15" в матрицах данной размерности

9. Рис. 2.7. Зависимость времени вычисления от количества кластеров на матрице 30x30

10. Рис. 2.8. Зависимость времени вычисления от количества кластеров на матрице 50x50

11.Рис. 2.9. Пример матрицы с топологическими особенностями класса II

12. Рис. 2.10. Пример редуцированной матрицы с топологическими особенностями класса II

13. Рис. 2.11. Пример матрицы типа «Класс II - верхняя граница»

14. Рис. 2.12. Пример матрицы типа «Класс II - нижняя граница»

15.Рис. 2.13. Геометрическая интерпретация топологии класса II

16. Рис. 2.14. Пример «накладывающихся» кластеров

17. Рис. 2.15. Решение QAP для нескольких размерностей

18. Рис. 2. 16. Решение QAP для размерности 11 и кластеров размерностью от 1 до 10

19. Рис. 2.17. Исследование количества возвратов при проведении вычислений с 0/1 рюкзаком из 48 элементов и С = Zw / 3

20. Рис 2.18. использование алгоритма «Иерархической декомпозиции»

21. Рис. 2.19 Соединение, когда вход и выход из кластера - соседние вершины по ходу оптимального решения

22. Рис. 2.20. Соединение в общем случае

23.Рис. 2.21. Выбор элементов для нового кластера

24.Рис. 3.1. Иерархия наследования элементов Пролога

25. Рис. 3.2. Постановка CSP в языке SICStus Пролог

26. Рис. 3.3. Постановка CSP с функцией минимизации в SICStus Пролог

27. Рис. 3.4. Иерархическая модель вычислений

28. Рис. 3.5. Диаграмма деятельности: доказательство в языке Пролог

29.Рис. 3.6. Диаграмма деятельности: доказательство

30. Рис. 3.7. Диаграмма деятельности: вычисление математического выражения

31. Рис. 3.8. Диаграмма деятельности: доказательство встроенного функтора solve

32. Рис. 4.1. Время вычисления при возрастании интервала для ресурсов. Ограничение по ресурсам =15

33.Рис. 4.2. Время вычисления при возрастании интервала для ресурсов. Ограничение по ресурсам =15

34. Рис. 4.3. Изменение сложности решения при изменении исходных данных на двух разных В&В

35. Рис. 4.4. Зависимость времени решения от размера кластеров при решении методом Pisinger В&В

36.Рис. 4.5. Зависимость времени решения от размера кластеров при решении методом Mallba В&В

Список таблиц

1. Таблица 1. Среднее количество ребер, используемых при поиске решения методом ветвей и границ на матрицах с топологическими особенностями по (3), (4)

2. Таблица 2. Время и относительная погрешность решения при кластеризации класса I.

3. Таблица 2.1. Среднее число ребер, исследуемых методом ветвей и границ

4. Таблица 2.2. Оценка количества кластеров, выявленных в некоторых асимметрических матрицах из TSPLIB

5. Таблица 2.3 Среднее количество ребер, используемых методом ветвей и границ при решении задач с топологическими особенностями класса II

6. Таблица 2.4. Среднее количество ребер, используемых при поиске решения при топологии «класса II - симметрическая»

7. Таблица 2.5. Оценка точности вычислений алгоритма вставки на матрицах с кластеризацией класса II. Кластеры 4x4.

8. Таблица 2.6. Точность и время решения методом декомпозиции матриц со строгой кластеризацией, кластеры 4x4.

9. Таблица 2.7. Результаты тестирования алгоритма интеллектуального возврата.

10. Таблица 4.1. Погрешность алгоритма интеллектуального возврата при строгой кластеризации класса II

11. Таблица 4.2. Оценка точности решения методами интеллектуального возврата, декомпозиции и вставки при особенностях по формуле (2.2) и кластерах размером 5x5.

12.Таблица 4.3. Оценка количества кластеров, выявленных в некоторых асимметрических матрицах TSBLIB и точность вычислений алгоритмом интеллектуального возврата.

13.Таблица 4.4. Время решения TSP в зависимости от наличия или отсутствия строгих кластеров в SUCStus Прологе и BBmod

14. Таблица 4.5. Сравнение времени решения задачи о 0/1 рюкзаке методами В&В при размерности задачи 40 и различных характеристиках исходных данных

Список сокращений

Сокращение Комментарий

WAM Warren's Abstract Machine - абстрактная машина Варрена

DFS Deep First Search - поиск в глубину

CSP Constraint Satisfaction Problem - задача удовлетворения ограничениям

ВВ Branch and Bound method - метод ветвей и границ

BCSP Binary-CSP - бинарная задача удовлетворения ограничениям

TSP Travelling Salesman Problem - задача коммивояжера

FITSP Farthest insertion for travelling salesman problem - вставка самого дальнего при решении задачи коммивояжера

QAP Quadratic Assignment Problem - квадратическая задача о назначении

КЗН Квадратическая задача о назначении

BBmod Алгоритм, предложенный автором, являющийся модификацией метода ветвей и границ

CLP Constraint Logic Programming - логической программирование с использованием constraint технологии

Введение

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

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

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

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

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

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

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

Основные задачи исследования:

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

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

3. Разработка алгоритмов работы процедур решения constraint системы при наличии фазового перехода.

4. Разработка программного прототипа constraint системы, работающего в условиях фазового перехода.

5. Оценка эффективности предлагаемого подхода.

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

Научная новизна заключается в том, что

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

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

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

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

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

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

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

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

4. Выполнено экспериментальное сравнение точности и времени решения при наличии фазовых переходов между разработанной системой и коммерческой constraint системой SICStus Prolog, созданной Swedish Institute of Computer Science версия июля 2001 года, на задачах коммивояжера и кумулятивного расписания, показавшая сокращение времени решения до 10 раз.

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

Теоретические и прикладные вопросы современных информационных технологий - 2001», Улан-Удэ, 2001; вторая международная научно-практическая дистанционная конференция «Компьютерные технологии в науке, производстве, социальных и экономических процессах», 2001; международная конференция «Современные технологии обучения», Санкт-Петербург, 2002.

Предложенные методы использовались в НИОКР «Разработка интеллектуальных систем управления и систем транспортной логистики Санкт-Петербурга» (№5905/САУ-225), выполненной для правительства Санкт-Петербурга в 1998 году.

Разработанный подход использовался в образовательном проекте «Учебно-научный центр университета информатики, электроники и управления» регистрационный номер АО 1500150 ФЦП «Интеграция»: «Интегрированная система подготовки кадров и фундаментальных научных исследований в области информатики» (Проект регистрационный номер 142, книга 2) в 2001 году.

Материалы использовались при чтении курсов «Логическое программирование» и «Логическое и функциональное программирование» для специальностей 0102 и 2204, а так же в курсовом проектировании курса «Логическое программирование» для специальности 0102.

Выводы по главе 4

1. Показано, что применение метода ветвей и границ для решения задачи без исследования особенностей исходных данных может приводить к появлению фазового перехода [1, 7, 8].

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

3. Данный подход разработан на примере задачи коммивояжера и проверен на задаче кумулятивного расписания и 0/1 рюкзаке.

Заключение

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

Направления дальнейших исследований

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

Фазовые переходы в зависимости от исходных данных

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

В качестве направления для дальнейших исследований предлагаются следующие:

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

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

Методы декомпозиции

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

В качестве направления для дальнейших исследований предлагаются следующие:

• Исследовать точность и сложность методов «иерархической декомпозиции».

• Исследовать применимость принципов, использованных в данном подходе, при появлении фазовых переходов, возникающих по иным причинам.

Методы интеллектуального возврата

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

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

Принципы процедур решения NP-трудных задач в Constraint Прологе

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

В качестве направления для дальнейших исследований предлагаются следующие:

• Расширение списка задачи, к которым применимы предложенные принципы решения.

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

Научные положения работы

Научные положения данной диссертационной работы:

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

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

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

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

Более детальное описание представлено в следующем разделе.

Обобщенные результаты по некоторым главам

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

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

Разработаны методы идентификации данных топологических особенностей в задаче.

Исследована вероятность появления данных особенностей на тестовых задачах и степень возрастания сложности в общем случае. Исследована применимость данных особенностей к практическим задачам на примере задач коммивояжера из TSPLIB.

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

Предложен и апробирован обобщенный подход к решению NP-трудных задач, в которых может появиться фазовый переход:

1. Необходимо обнаружить наличие фазового перехода.

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

3. Необходимо разработать алгоритм решения при наличии обнаруженных особенностей.

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

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

1. Вальковский В.Б., Беляев С.А. "Использование фазовых переходов при решении комбинаторных задач" //Программные продукты и системы, #4, 2000, стр. 37 -38

2. Беляев С.А. "Аспекты создания программного комплекса для решения оптимизационных экономических задач" //Современные аспекты экономики, #8, 2001, стр. 6-9

3. Беляев С.А. "Заказчику программного обеспечения следует знать " //Компьютер Price, #46 (366), 2001, стр. 359 361

4. Беляев С.А. "Планирование как точная наука, или constraint технологии на практике" //Терабайт, #12 (20), 2001, стр. 63-64

5. Вальковский В.Б., Беляев С.А. "Интеллектуальный возврат в условиях фазового перехода при решении комбинаторных задач" //Программные продукты и системы, (в печати)

6. Беляев С.А. "Технология составления расписаний и форма обучения" //Тезисы доклада на VIII международной конференции "Современные технологии обучения", Санкт-Петербург, 2002, том 2, стр. 131 133

7. Hassan Ait-Kaci, Warren's Abstract Machine, Simon Fraser University, Canada, reprinted from MIT Press Version, 1999

8. Стерлинг JI., Шапиро Э. Искусство программирования на языке ПРОЛОГ. М.: Мир, 1990

9. Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта. М.:Мир, 1990

10. CP-AI-OR'99, Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems Ferrara, Italy, 25 - 26 February, 1999

11. A. Borning, M.Maher, A.Mortindale, M.Wilson, Constraint Hierarchies and Logic Programming, TR 88-11-10, CSD, University of Washington, 1988, 1- 26pp

12. D. Frost. Algorithms and Heuristics for Constraint Satisfaction Problems. PhD thesis, Information and Computer Science, University of California, Irvine, CA, 1997.

13. J. Jaffar and J. Lassez. Constraint logic programming: A survey. Journal of Logic Programming, 19(20):503-581, 1994.

14. A. K. Mackworth. Constraint satisfaction. In S. C. Shapiro, editor, Encyclopedia of Artificial Intelligence, 2nd Edition, pages 285-293. John Wiley & Sons, 1992.

15. Podleski A. Constraint Programming: Basics and Trends, Springer-Verlag, 1995

16. Tsang E. Foundation of Constraint Satisfaction, Academic Press, 1993

17. Клиенты и партнеры COSYTEC, http://www.cosytec.com/casesstudies/English/index.htm

18. В. A. Nadel. Some applications of the constraint satisfaction problem. In AAAI-90: Workshop on Constraint Directed Reasoning Working Notes, Boston, Mass., 1990.

19. J. L. Lauriere. A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10(1), 1978.

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

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

22. В. A. Nadel. Constraint Satisfaction Algorithms. Computational Intelligence, 5:188224, 1989.

23. V. Kumar. Algorithms for constraint satisfaction problems: A survey. AI magazine, 13(1):32—44, 1992.

24. R. Bartak, Guide to Constraint Programming , 1998, http://kti.ms.mff.cuni.cz/~bartak/constraints/extendcsp.html

25. B. Selman, H. A. Kautz, and B. Cohen. Noise Strategies for Improving Local Search. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 337—343, Seattle, Washington, 1994.

26. R. Debruyne and C. Bessfere. Some practicable filtering techniques for the constraint satisfaction problem. In Proc. of the 15th IJCAI, pages 412-417. 1997.

27. E. C. Freuder and M. J. Quinn. The use of linear spanning trees to represent constraint satisfaction problems. Technical Report 87-41, University of New Hampshire, Durham, 1987.

28. F. Bacchus and P. van Run. Dynamic variable ordering in CSPs. In Principles and Practice of Constraint Programming (CP-95), Cassis, France, 1995. Available as Lecture Notes on CS, vol 976, pp 258-277, 1995.

29. Ian Gent, Ewan Maclntyre, Patrick Prosser, Barbara Smith and Toby Walsh. Random Constraint Satisfaction: Flaws and Structure. Constraints, 6 (4), 345-372,2001

30. Ian Gent, Kostas Stergiou and Toby Walsh. Decomposable Constraints. Artificial Intelligence, 123 (1-2), 133-156, 2000

31. A. K. Mackworth and E. C. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25:65-74, 1985.

32. G. Kondrak and P. van Beek. A theoretical evaluation of selected algorithms. Artificial Intelligence, 89:365-387, 1997.

33. J. C. Sogno. Analysis of standard and new algorithms for the integer and linear constraint satisfaction problem. Technical report, INRIA, 1992.

34. Roberto Bayardo and Daniel Mirankar. A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 298—304, 1996.

35. Zhe Lui, Algorithms for Constraint Satisfaction Problem, thesis presented to University Waterloo, Ontario, Canada, 1998, 1-13 lpp

36. R.Detcher, D.Frost, Backtracking Algorithms for constraint satisfaction problems a tutorial survey, DICS, University of California, Irvine, 1999, l-47pp

37. E. C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24~32, 1982.

38. E. C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24—32, 1982.

39. Steven Minton, Mark Johnston, Andrew Philips, and Philip Laird. Minimizing conflicts: a heuristic repair method for constraint satisfaction problem and scheduling problems. Artificial Intelligence, 58:161-205, 1992.

40. D. Frost and R. Dechter. Look-ahead value ordering for constraint satisfaction problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-95), pages 572-578, 1995.

41. D. Frost and R. Dechter. Looking at full look-ahead. In Proceedings of the Second International Conference on Constraint Programming (CP-96), 1996.

42. Christian Bessiere. Arc-consistency and arc-consistency again. Artificial Intelligence, 65(1):179—190, 1994.47. "Constraint Satisfaction Problem", UGAI Lectures, http://yoda.cis.temple.edu:8080/UGAIWWW/lectures/constraints.html

43. P. Van Hentenryck, Y. Deville, and C.-M. Teng. A generic arc consistency algorithm and its specializations. Artificial Intelligence, 57:291—321, 1992.

44. D. A. McAllester. Truth maintenance. In AAAI-90: Proceedings of the Eighth National Conference on Artificial Intelligence, pages 1109—1116, 1990.

45. Christian Bessiere, Eugene C. Freuder, and Jean-Charles Regin. Using Inference to Reduce Arc Consistency Computation. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 592-598, Montreal, Canada, 1995.

46. Geographically Distributed Environments: Combinatorial Optimization Library, http://www.lsi.upc.es/~mallba/public/mallba-LL.html

47. E.L. Lawler and D.E. Wood, "Branch-and-bound methods: a survey", Operations Research 14, 1966, pp 699-719

48. Herbert Wilf. Algorithms and complexity. University of Pensilvania. Internet edition, 1994

49. P. Gent and T. Walsh. Easy problems are sometimes hard. Artificial Intelligence, 70:335-345, 1994.

50. Gent, T. Walsh "The TSP Phase Transition", RR/1995/178, Department of Computer Science, University of Strathclyde

51. Axo А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.Мир, 1979

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

53. Papadimitriou С.Н. Computational Complexity, Addison-Wesley, 1994

54. I.Gent, T.Walsh, Phase Transition from Real Computational Problems, DCS, University of Strathclyde, 1995, SERC grant GR/H 23610, 1995 l-9pp

55. D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In Proc. of 10th National Conference on AI. AAAI Press/MIT Press, July 1992.

56. Zhang W., Korf R.E., A study of complexity transitions on the asymmetric travelling salesman problem, Artificial Intelligence, 1996, Vol. 81, p. 223-239

57. H.Rudova, L.Matyska, Constraint based Timetabling with students schedule, BRNO 60200, Masaryk University, Czheh Republic, 1-15pp

58. I.Gent, T.Walsh, The Number Partition Phase Transition, RR-95-185, DCS, University of Strathclyde, 1995, 1-19pp

59. D. Corne, H-L. Fang, and C. Mellish. Solving the modular exam scheduling problem with genetic algorithms. In Industrial and Engineering Applications of AI and Expert Systems: Proc. of the 6th Int. Conference, 1992.

60. B. Nudel. Consistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics. Artificial Intelligence, 21:135—178, 1983.

61. D. Corne, H-L. Fang, and C. Mellish. Solving the modular exam scheduling problem with genetic algorithms. In Industrial and Engineering Applications of AI and Expert Systems: Proc. of the 6th Int. Conference, 1992.

62. P. Prosser. Binary constraint satisfaction problems: Some are harder than others. In Proc. of ECAI-94, pages 95-99, 1994.

63. P. Gent and T. Walsh. The hardest random SAT problems. In B. Nebel and L. Dreschler-Fischer, editors, KI-94: Advances in AI. 18th German Annual Conference on AI, pages 355—366. Springer- Yerlag, 1994.

64. P. Gent and T. Walsh. The SAT phase transition. In Proc. of ECAI-94, pages 105109,1994

65. L. Saitta, Jean-Daniel Zucker, "Abstraction and Phase Transitions", Universita del Piemonte Orientate, Submission to SARA'2000

66. G. Reinelt. TSPLIB a traveling salesman problem library. ORSA Journal on Computing, 3:376-384, 1991.

67. M. Grotschel and 0. Holland, "Solution of large-scale symmetric travelling salesman problems", Mathematical Programming 51, 1991, pp 141-202

68. B. Golden, L. Bodin, T. Doyle, W. Stewart "Approximate Traveling Salesman Algorithms"

69. A. M. Frieze, G. Galbiati, F. Maffioli "On the Worst-Case Performance of Some Algorithms for the Asymmetric Travelling Salesman Problem"

70. E. Lower, J. Lenstra, A. Rinooy Kan, D. Shmoys "The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization", pp. 676

71. V. G. Deineko and G. J. Woeginger, A Study of Exponential Neighborhoods for the Traveling Salesman Problem and for the Quadratic Assignment Problem. Preprint, 1997, Graz TU, Austria.

72. P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI-91), pages 331-337, 1991.

73. T. Lai and A. Sprague, "Performance of parallel branch-and-bound algorithms", IEEE Trans. Computers, vol. 34, pp. 962-964, 1985.

74. K.G.Ramakrishnan, M.G.C.Resende, P.M.Pardalos, Branch and bound algorithm for the Quadratic Assignment Problem using Low-Bound based on Linear Programming, April 1995

75. T.Koopmans, M.Berkmann, Assignment problems and the location of econimic activities, Econometria, 25 (1957), pp. 53-76

76. E. Lawler. The quadratic assignment problem. Management Science, 9:586—599, 1963

77. S.W. Hadley, F. Rendl, and H. Wolkowicz. A new lower bound via projection for the quadratic assignment problem. Mathematics of Operations Research, 17:727-739, 1992.

78. E. C. Yela, The Quadratic Assignment Problem: Theory and Algorithms, Kluwer Academic Publishers, Dordrecht, 1998.

79. M. S. Bazaraa and O. Kirca. A branch-and-bound-based heuristic for solving the quadratic assignment problem. Naval Research Logistics Quarterly, 30:287 304, 1983.

80. P. Hahn, W. Hightower, T. Johnson, M. Guignard-Spielberg, C. Roucairol. 1999. Tree elaboration strategies in branch-and-bound algorithms for assigning the quadratic assignment problem, 6th SIAM Conference on Optimization.

81. T. Stutzle. ACO Algorithms for the Quadratic Assignment Problem. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, 1999.

82. E. Balas. The asymmetric assignment problem and some new facets of the travelling salesman polytope on a directed graph. SIAM Journal on Discrete Mathematics, 3:425- 451, 1989.

83. V. Chvatal, "Hard knapsack problems", Operations Research, vol. 28, pp. 1402-1411, 1980.

84. S. Martello, D. Pisinger, P. Toth, "New trends in exact algorithms for the 0-1 knapsack problem", European Journal of Operational Research, 123, 325-332 (2000), http://www.diku.dk/research/published/1997/97-10.ps.gz

85. Sadeh, N. and Fox, M. S. (1996) Variable and Value Ordering Heuristics for the Job Shop Scheduling page (46) A state-of-the-art review of job-shop scheduling techniques 03/10/98 Constraint Satisfaction Problem" Artificial Intelligence, 86(1), 141.

86. M. L. Ginsberg. Dynamic backtracking. Journal of Artificial Intelligence Research, 1:25-46, 1993.

87. J. R. Bitner and E. M. Reingold. Backtrack programming techniques. Communications of the ACM, 18(11):651—656, 1975.

88. M. Stallmanand G. J. Sussman. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence, 9:135-196, 1977.

89. N. J. Nillson. Principles of Artificial Intelligence. Tioga, Palo Alto, CA, 1980.

90. M. C. Cooper. An optimal k-consistency algorithm. Artificial Intelligence, 41(1):89-95, 1990.

91. J.Borrett, E.Tsang, N.Walsh, Adaptive Constraint Satisfaction: The Quickest First Principle, DCS, University of Essex, UK, TR-CSM-256, 1955, l-24pp

92. J. Pearl. Heuristics: Intelligent Search Strategies. Addison-Wesley, 1984.

93. M. Bruynooghe. Solving combinatorial search problems by intelligent backtracking. Information Processing Letters, 12:36—39, 1981.

94. A. B. Backer, Intelligent backtracking on the Hardest Constraint Problems, CIRL DCIS, University of Oregon, 1995, l-26pp

95. A. B. Baker. Intelligent Backtracking on constraint satisfaction problems: experimental and theoretical results. PhD thesis, Graduate School of the University of Oregon, Eugene, OR, 1995.

96. A. B. Baker. The hazards of fancy backtracking. In Proceedings of National Conference of Artificial Intelligence (AAAI-94), 1994.

97. A. M. Frieze, G. Galbiati, F. Maffioli "On the Worst-Case Performance of Some Algorithms for the Asymmetric Travelling Salesman Problem"

98. R. Dechter and I. Meiri. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelligence, 68:211—241, 1994.

99. P. Prosser. Hybrid algorithms for constraint satisfaction problems. Computational Intelligence, 9(3):268~299, 1993.

100. R. Bayardo and D. Miranker. A complexity analysis of spacebounded learning algorithms for the constraint satisfaction problem. In AAAI-96: Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 298—304, Portland, OR, 1996.

101. R. Bayardo, Jr. and D. P. Miranker. On the space-time trade-off in solving constraint satisfaction problems. In Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), pages 558- 562, 1995.

102. SICStus Prolog User's Manual, Swedish Institute of Computer Science, 2001

103. Mayoh В., Penjam J., Tyugu E. (Ets) Constraint Programming NATO Advanced Study Institute, Tallin, Institute of Cybernetics, Estonian Academy of Science, TR CS 57/1993

104. R.J. Wallace, "Enhancements of branch and bound methods for the maximal constraint satisfaction problem", Proc. of AAAI-96, pp 188-196, Portland, Oregon, USA, 1996.

105. Norman Sadeh and Mark S. Fox. Variable and value ordering heuristics for activity-based job-shop scheduling. In Proceedings of the Fourth International Conference on Expert Systems in Production and Management, pages 134-144, 1990.

106. N. Sadeh, K. Sycara, and Y. Xiong. Backtracking techniques for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 76:455-480, 1995.

107. D. Applegate and W. Cook. A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3:149-156, 1991.

108. J.Han, M.Kamber "Data Mining: Concept and Techniques", ACADEMIC PRESS (www.academicpress.com), 2001, pages: 335 393

109. Б.В. Гнеденко, Курс теории вероятностей, Москва, «Наука», 1965

110. Н. Джонсон, Ф. Лион Статистика и планирование эксперимента в технике и науке. Методы обработки данных. Пер. с англ./ Под ред. Э.К.Лецкого. М.:Мир, 1980, стр. 155- 158, 297-302