Разработка и анализ алгоритмов для задачи выполнимости и ее обобщений на основе L-разбиения тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Ягофарова, Дарья Ивановна

• Ягофарова, Дарья Ивановна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Ягофарова, Дарья Ивановна

Введение

1 Задача выполнимости и методы ее решения

1.1 Постановки задач и модели целочисленного программирования.

1.2 Связь с другими задачами и приложения.

1.3 Алгоритмы для задач выполнимости и максимальной выполнимости.

2 Исследование и решение задачи выполнимости с использованием L-разбиения.

2.1 Предварительные сведения.

2.2 Анализ L-структуры многогранника задачи выполнимости.

2.3 Алгоритмы перебора L-классов для задачи выполнимости

2.4 Параллельные алгоритмы.

3 Применение метода перебора L-классов к решению некоторых задач дискретной оптимизации

3.1 Разработка алгоритмов локального поиска для задачи максимальной выполнимости с использованием перебора L-классов. GG

3.2 Модели целочисленного линейного программирования для задачи о минимальном комитете.

3.3 Экспериментальное сравнение L-структуры моделей . 7G

4 Экспериментальные исследования

4.1 Вычислительный эксперимент для алгоритмов перебора

L-классов.

4.2 Результаты эксперимента для параллельного алгоритма

4.3 Сравнение эвристических алгоритмов.

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

Задача выполнимости логической формулы играет важную роль в дискретной оптимизации и теории сложности [7, 42]. Она является первой задачей, для которой доказана NP-полнота [G7], к пей сводятся многие задачи теории графов, построения расписаний, криптографии. Ограничения логического типа необходимо учитывать в процессе принятия решений в планировании, управлении, проектировании и других областях [28, 36, 78, 87, 112]. В связи с этим широко применяются различные обобщения задачи выполнимости, например, задача максимальной выполнимости.

Ввиду сложности рассматриваемых задач для их исследования и решения требуется применение системного анализа, моделей и методов оптимизации. К основным направлениям исследования задачи выполнимости и ее обобщений относятся изучение сложности, выявление полиномиально разрешимых случаев, разработка и анализ алгоритмов, построение семейств "трудных" задач для конкретных алгоритмов [6, 64, 65, 68, 71, 74, 75, 78, 79, 85, 96, 100, 102, 107, 108, ИЗ].

Среди известных подходов к решению задач с логическими ограничениями можно выделить алгоритмы ветвей и границ, алгоритмы отсечения, а также комбинаций этих методов [6, 66, 69, 70, 78, 82, 103]. В последнее время большое внимание уделяется таким алгоритмам решения задач выполнимости и максимальной выполнимости как поиск с запретами [83, 98], имитация отжига [110], локальный поиск [77,106,109], генетические алгоритмы [61, 97].

В области принятия решений имеется несколько подходов к анализу несовместных систем ограничений. Можно, например, искать "решение", удовлетворяющее максимальному числу ограничений. Такой подход реализуется, в частности, в задаче максимальной выполнимости. Другим направлением решения задач с противоречивыми условиями является использование комитетных конструкций, обобщающих понятие решения. Данной проблематике посвящены работы Вл.Д. Мазурова, М.Ю. Хачая и других авторов [13, 39 - 41, 52, 99].

Для исследования и решения задач дискретной оптимизации, в том числе для рассматриваемых нами, широко используются модели и методы целочисленного программирования (ЦП) [1, 3, И, 38, 41, 49, 53, 54, 60, 78, 99].

Ранее А.А. Колоколовым предложен метод регулярных разбиений, который предназначен для анализа и решения задач ЦП [20]. Значительное число результатов получено с помощью L-разбиения [9,12, 1С -18, 21, 26, 27, 43, 47]. С использованием этого подхода описаны новые классы отсечений, найдены оценки числа итераций для алгоритмов отсечения, алгоритмов ветвей и границ и некоторых других, исследована L-структура ряда задач, предложены алгоритмы перебора L-классов для задачи целочисленного линейного программирования (ЦЛП), задачи о покрытии множества, простейшей задачи размещения, получены результаты по устойчивости задач и алгоритмов. Построены семейства задач с мощными 1/-иакрытиями, получены первые результаты по разработке алгоритмов перебора L-классов для задач выполнимости и максимальной выполнимости [1, 22, 25, 32, 89].

Несмотря на значительное число работ по задаче выполнимости и ее обобщениям недостаточно исследований проведено с использованием моделей и методов целочисленного программирования, в частности, метода регулярных разбиений. Другим актуальным направлением является создание параллельных алгоритмов для различных задач оптимизации [15, 4G, 48], в том числе для задач с логическими ограничениями.

Цель диссертации - разработка и анализ алгоритмов решения задачи выполнимости с использованием моделей целочисленного линейного программирования и L-разбиепия, исследование некоторых смежных задач.

В работе предложены алгоритмы перебора L-классов для задачи выполнимости логической формулы и на их основе разработаны параллельные варианты алгоритмов. Указанные алгоритмы применяются для точного решения невзвешенной задачи максимальной выполнимости [23, 25] и в программном комплексе для эскизного проектирования одежды [29]. Проведено исследование L-структуры задач 2-выполнимости и выполнимости некоторых специальных логических формул.

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Ягофарова, Дарья Ивановна

Основные результаты диссертации заключаются в следующем:

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

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

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

4. Предложена модель целочисленного линейного программирования для задачи о минимальном комитете, предназначенная для ее анализа с использованием L-разбиения, проведено ее экспериментальное исследование.

5. Создано программное обеспечение для разработанных алгоритмов, проведены экспериментальные исследования на известных сериях тестовых задач.

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Ягофарова, Дарья Ивановна, 2006 год

1. Адельшин А.В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика. - 2004. - № 3. - С. 35 - 42.

2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

3. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978. - 333 с.

4. Беспалов Д.В., Семенов А.А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. 2002. -Т. 7, Ч. 2. - С. 18 - 25.

5. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

6. Всемирнов М.А., Гирш Э.А., Данцин Е.Я., Иванов С.В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Зап. науч. семин. ПОМН. 2001. - Т. 277. - С. 14 - 46.

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

8. Данцин Е.Я. Две системы доказательства тавтологииности, основанные на методе расщеплений. Зап. науч. семин. ЛОМИ. - 1981. - Т. 105.- С. 24 - 44.

9. Девятерикова М.В., Колоколов А.А. Анализ устойчивости по целевой функции некоторых алгоритмов дискретной оптимизации // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. - Т. 1. -С. 449 - 454.

10. Дулькейт В.И., Файзуллин Р.Т. Алгоритм построения эквивалентных КНФ для задачи факторизации // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 90.

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

12. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. -2000. Сер. 2, Т. 7. - С. 22 - 46.

13. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. - 288 с.

14. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М: Наука, 1983. -336 с.

15. Еремин И.И., Попов Л.Д. Параллельные фейеровские методы для сильно структурированных систем линейных неравенств и уравнений // Алгоритмы и программные средства параллельныхвычислений. Екатеринбург: ИММ УрО РАН, 2002. - Вып. 6. -С. 61 - 65.

16. Заблоцкая О.А. Нижняя оценка числа итераций для одного алгоритма лексикографической оптимизации // Дискретная оптимизация и численные методы решения прикладных задач. -Новосибирск: ВЦ СО АН СССР, 1986. С. 21 - 27.

17. Забудский Г.Г. Некоторые свойства многогранника задачи о р-медиапе // Вестник Омского университета. Омск: ОмГУ, 1997. - № 4. - С. 11-13.

18. Заозерская J1.A. Об одном алгоритме перебора L-классов для решения задачи о покрытии множества // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 1998. - Т. 1. - С. 139 - 142.

19. Калльрат Ю.Н., Колоколов А.А., Ягофарова Д.И. Алгоритм перебора L-классов для задачи выполнимости // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложеиия". Омск, 2003. - С. 94.

20. Колоколов А.А. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. - С. 67 - 93.

21. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций. 1994. - № 2. - С. 18 - 39.

22. Колоколов А.А., Адельшин А.В., Чередова Ю.Н. Применение L-разбиения к исследованию некоторых задач выполнимости // Труды XII Байкальской международной школы-семинара "Методыоптимизации и их приложения". Иркутск, 2001. - Т. 1. -С. 166 - 172.

23. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 42 - 46.

24. Колоколов А.А., Заозерская JI.A. Регулярные разбиения и лексикография: Учебно-методическое пособие. Омск: ОмГУ, 1999. -31 с.

25. Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. Омск: ОмГУ, 1996. - № 1. -С. 21-23.

26. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Параллельный алгоритм перебора L-классов для задачи выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006.1. С. 102.

27. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости. Препринт. Омск: Ом ГУ, 2006. - 19 с.

28. Колоколов А.А., Чередова Ю.Н. Исследование и решение задачи о выполнимости с использованием L-разбиения // Материалы международной конференции "Дискретный анализ и исследование операций". Новосибирск, 2000. - С. 150.

29. Колоколов А.А., Ягофарова Д.И. Об одной модели целочисленного программирования для задачи о минимальном комитете // Материалы российской конференции "Дискретный анализ и исследование операций". Новосибирск, 2004. - С. 163.

30. Колоколов А.А., Ягофарова Д.И., Тюрюмов А.Н. Разработка алгоритмов для задачи выполнимости и некоторых ее обобщений с использованием перебора L-классов // Омский научный вестник.- 2006. № 5 (39)-С. 57-61.

31. Колоколов А.А., Ярош А.В. Проектирование одежды с использованием некоторых моделей дискретной оптимизации // Омский научный вестник. 2002. - Вып. 20. - С. 91 - 94.

32. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. -М.: Постмаркет, 2001. 328 с.

33. Кузнецова А.А., Стрекаловский А.С., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации //ЖВМ и МФ. 1999. - Т. 39. - М. - С. 9 - 16.

34. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. - 248 с.

35. Мазуров Вл.Д., Хачай М.Ю. Комитетпые конструкции // Известия Уральского университета. 1999, серия "Математика - механика".- Вып. 2 (14). С. 77 - 109.

36. Мазуров Вл.Д., Хачай М.Ю. Комитеты систем линейных неравенств // Автоматика и телемеханика. 2004. - № 2. -С. 43 - 54.

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

38. Сайко JI.A. Исследование мощности L-накрытий некоторых задач о покрытии // Дискретная оптимизация и анализ сложных систем.- Новосибирск: ВЦ СО АН СССР, 1989. С. 76 - 97.

39. Семенов А.А., Буранов Е.В. Погружение задачи криптоанализа симметричных шифров в пропозициональную логику // Вычислительные технологии. 2003. - Т. 8. (Совместный выпуск с журналом "Региональный вестник Востока") - С. 118 - 126.

40. Сергиенко И.В., Шило В.П. Вероятностная декомпозиция задач линейного целочисленного программирования с булевыми переменными и автоматический выбор алгоритмов для их решения // Кибернетика и системный анализ. 1994. - № 2. - С. 149 - 158.

41. Сергиенко И.В., Шило В.П., Рощин В.А. Распараллеливание процесса оптимизации для задач дискретного программирования // Кибернетика и системный анализ. 2004. - № 2. - С. 45 - 52.

42. Симанчев Р.Ю. Сравнение вполне регулярных отсечений и алгоритмов // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. - С. 107 - 123.

43. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 156.

44. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. М.: Мир, 1991. - 702 с.

45. Файзуллин Р.Т., Салаев Е.В. Об одном итерационном алгоритме решения задачи "Выполнимость" // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 129.

46. Файзуллин Р.Т., Салаев Е.В. Применение метода последовательных приближений с инерцией к решению задачи 3-SAT // Таврический вестник информатики и математики. 2006. - №1. - С. 44 - 49.

47. Хачай М.Ю. К задаче о минимальном комитете // Тезисы докладов Всероссийской конференции "Алгоритмический анализ неустойчивых задач". Екатеринбург, 2004. - С. 309.

48. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1974. 520 с.

49. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит, 1995. - 190 с.

50. Ягофарова Д.И. Анализ L-структуры задачи 2-выполнимости // Материалы ежегодного научного семинара "Под знаком -Омск: ООО "Издатель-Полиграфист", 2003. С. 71 - 77.

51. Ablow С.М., Kaylor D.J. Inconsistent homogenous linear inequalities // Bull.Amer.Math.Soc. 1965. - V. 71 - № 5. - P. 724.

52. Ablow C.M., Kaylor D.J. A commitee solution of the pattern recognition problem // IEEE Trans. 1965. - V. IT-11. - № 3. -P. 453 - 455.

53. Aspvall В., Plass M.F., Tarjan R.E. A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas // Information Processing Letters 8(3). 1979. - P. 121 - 132.

54. Ayteiniz T. A probabilistic study of 3-Satisfiability. Dissertation for the degree of Doctor of Philosophy. 2001. - 119 p.

55. Back Т., Eiben A.E., Vink M.E. A superior evolutionary algorithm for 3-SAT //In Proc. of the 7th Annual Conference on Evolutionary Programming, LNCS 1744. 1998. - P. 125 - 136.

56. Blair C.E., Jeroslow R.G., Lowe J.K. Some results and experiments in programming techniques for propositional logic //Computers and Operations Research. 1986. - V. 13. - №5. - P. 633 - 645.

57. Borchers В., Furman J. A Two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems //Journal of Combinatorial Optimization. 1998. - V.2. - №4. - P. 299 - 306.

58. Boros E., Crama Y., Hammer P.L. Polynomial-time inference of all valid implications for Horn and related formulae // Annals of Mathematics and Artificial Intelligence. 1990. - V. 1. - P. 21 - 32.

59. Boros E., Hammer P.L., Sun X. Recognition of q-Horn formulae in linear time // Discrete Applied Mathematics. 1994. - V. 55. - P. 1 - 13.

60. Cheriyan J., Cunningham W.H., Tuncel L., and Wang Y. A linear programming and rounding approach to max 2-sat // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. -V. 26. - P. 395 - 414.

61. Cook S.A. The complexity of theorem-proving procedure // Proc. 3rd Annual ACM Symposium on the Theory of Computing. 1971. -P. 151 - 159.

62. Cook S.A., Mitchell D.G. Finding Hard Instances of the Satisfiability-Problem: A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 35. - P. 1 - 17.

63. Davis M., Logemann G., Loveland D. A machine program for theorem-proving // Communications of the ACM. 1962. - V. 5. - Ж 7. -P. 394 - 397.

64. Davis M., Putnam H. A computing procedure for quantification theory // Journal of the ACM. 1960. - V. 7. - Ж 3. - P. 201 - 215.

65. Dowling W.F., Gallier J.H. Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae // Journal of Logic Programming 1, 1984, P. 267 284.

66. Eremeev A. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of Artificial Evolution Conference. Lecture Notes in Computer Science, 2000. Vol. 1829. - P. 84 - 95.

67. Eremeev A.V., Kolokolov A.A. On some genetic and L-class enumeration algorithms in integer programming // Proc. of the First Intertational Conference on Evolutionary Computation and its Applications. Moscow, 1996. - P. 297 - 303.

68. Franco J., Van Gelder A. A perspective on certain polynomial time solvable classes of satisfiability // Discrete Applied Mathematics. -2003. V. 125. - P. 297 - 303.

69. Goemans M.X., Williamson D.A. New 3/4-approximation algorithms for MAX SAT // SIAM Journal on Discrete Mathematics. 1994. -№.7. - P. 656 - 666.

70. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989. - 412 pp.

71. Gu J. Local Search for the Satisfiability (SAT) Problem // IEEE Transaction on Sistems, Man and Cibernetics. 1993. - № 23 (4) -P. 1108 - 1129.

72. Gu J., Purdom P., Franco J., Wah B. Algorithms for the Satisfiability (SAT) Problem: A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 35. - P. 19 - 130.

73. Hansen P., Jaumard B. Algorithms for the Maximum Satisfiability Problem. // Computing 44. 1990. - P. 279 - 303.

74. Hastad J. Some optimal inapproximability results //Proc. of the 29th Annual ACM Symposium on Theory of Computing, 1997. P. 1 - 10.

75. Hogg T. Refining the phase transition in combinatorial search // Artificial Intelligence. 1996. - V.81. - P. 127 - 154.

76. Hooker J.N. Generalized resolution and cutting planes //Annals of Operations Research. 1988. - V.12. - P. 217 - 239.

77. Jaumard В., Stan M., Desrosiers J. Tabu Search and a Quadratic Relaxation for the Satisfiability Problem // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - Vol. 26. -P. 457 - 477.

78. Johnson D. Approximation algorithms for combinatorial problems //Journal of Comput. System Science. 1974. - V.9. - P. 256 - 278.

79. Joy S., Mitchell J., Borchers B. A branch and cut algorithm for MAX-SAT and weighted MAX-SAT // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997. - V. 35. -P. 519 - 536.

80. Karloff H., Zwick U. A 7/8-approximation algorithm for MAX 3-SAT? //Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997. P. 406 - 415.

81. Kautz H., Selman В. Planning as Satisfiability // Proceedings of the 10th European Conference on Artificial Intelligence (ECAI 92). 1992.- P. 359 363.

82. Kohli R., Krishnamurti R. Average perfomance of heuristics for satisfiability //SIAM Journal on Discrete Mathematics. 1989. - V.2.- P. 508 523.

83. Kolokolov A.A., Adelshin A.V., Cheredova J.N. The L-partition approach to SAT and MAX SAT // Annual Conference of the GOR. Abstracts. Duisburg, 2001. - P. 118.

84. Kolokolov A., Adelshin A., Yagofarova D. Development of Local Search Algorithms for MAX-SAT Problem Using L-class Enumeration // International Conference on Operations Research 2006. Abstract Guide.- Karlsruhe, 2006. P. 78.

85. Kolokolov A., Adelshin A., Yagofarova D. Local search algorithms for the MAX SAT problem based on L-class enumeration //Extended Abstracts of 18th Mini Euro Conference on VNS. Tenerife (Spain), 2005.-P. 117-118.

86. Kolokolov A., Kallrath J.,Yagofarova D. Analysis and Solving the Satisfiability Problem Using L-partition. // Abstracts of Annual International Conference Operations Research 2003. Heidelberg, 2003.- P. 128.

87. Kolokolov A., Yagofarova D., Tyuryumov A. Development of L-class Enumeration Algorithms for Satisfiability Problem // Abstracts of Annual International Conference Operations Research 2005. Bremen, 2005. - P. 107 - 108.

88. Kullmann O. New methods for 3-SAT decision and worst-case analysis.- Theoretical Computer Science 223 (1-2), 1999. P. 1 - 72.

89. Laursen Per S. Parallel Heuristic search introductions and a new approach // Solving Combinatorial Optimiz. Problems in Parallel / ed. A. Ferreire and P. Pardalos. - Berlin: Springer-Verlag, 1996. -P. 248-274.

90. Marathe M.V., Ravi S.S. On approximation algorithms for the minimum satisfiability problem // Information Processing Letters. -1996. V. 58. - P. 23 - 29.

91. Marchiori E., Rossi C. A flipping genetic algorithm for hard 3-SAT problems //In Proc. of the Genetic and Evolutionary Computation Confeence (GECCO-99). 1999. - P. 393 - 400.

92. Mazure В., Sais L., Gregorie E. Tabu Search for SAT // Proceedings of CP'95 Workshop on Solving Really Hard Problems. 1995. -P. 127 - 130.

93. Mazurov VI.D., Khachai M.Yu., Rybin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics, and Prediction // Proceedings of the Steklov Institute og mathematics Suppl. 1 2002. -P. 67-101.

94. Mitchell D., Selman В., Levesque H. Hard and Easy Distributions of SAT Problems // Proceedings of АААГ92. 1992 - P. 459 - 465.

95. Monien В., Speckenmeyer E. Solving Satisfiability in less then 2" steps. // Discrete Applied Mathematics. 1985. - JV* 10. - P. 287 - 295.

96. Papadimitriou C.H. On selecting a satisfying truth assignment // Proc. of FOCS'91. 1991. - P. 163 - 169.

97. Paturi R., Pudlak P., Saks M.E., Zane F. An improved exponential-time algorithm for k-SAT // Proc. of FOCS'98. 1998. - P. 628 - 637.

98. Paturi R., Pudlak P., Zane F. Satisfiability coding lemma // Proc. of FOCS'97. 1997. - P. 566 - 574.

99. Reeves С. Genetic Algorithms for the Operation Researcher // INFORMS Journal on Computing, 1997. V. 9. - № 3. - P. 231 - 250.

100. Resende M.G.C, Feo T.A. A GRASP for Satisfiability // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. -1996. V. 26. - P. 499 - 520.

101. Schoning U. A probabilistic algorithm for k-SAT and constraint satisfaction problems // Proc. of FOCS'99. 1999. - P. 410 - 414.

102. Scutella M.G. A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability // Journal of Logic Programming. -1990. V. 8. - P. 265 - 273.

103. Selman В., Kautz H., Cohen B. Local Search Strategies for Satisfiability Testing // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 26 - P. 521 - 531.

104. Spears M.W. Simulated Annealing for Hard Satisfiability Problems // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. - V. 26. - P. 533 - 557.

105. Stiitzle Т., Hoos H., Roli A. A review of the literature on local search algorithms for MAX-SAT // Technical Report AIDA-01-02. Darmstadt University of Technology. Computer Science Department. Intellectics Group. 2001. - 21 pp.

106. Velev M.N., Bryant R.E. Effective use of boolean satisfiability procedures in thr formal verification of superscalar and VLIM microprocessors. // Proc. of 38th Design Automation Conference (DAC'01). 2001. - P. 226 - 231.

107. Yannakakis M. On the approximation of maximum satisfiability // Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms. -1992. P. 1 - 9.114. www.cs.ubc.ca/~hoos/SATLIB/benchm.html115. www.nmt.edu/~borchers/maxsat.html