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

• Гуселетова, Ольга Николаевна
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Гуселетова, Ольга Николаевна

Введение.

1 Задачи дискретной оптимизации с логическими ограничениями и их приложения.

1.1 Задача выполнимости и ее обобщения

1.2 Методы решения задач выполнимости и максимальной выполнимости.

1.3 Некоторые приложения

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

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

2.2 Модель целочисленного линейного программирования

2.3 Примеры применения подхода.

2.4 Постановка задачи и модель ЦЛП с учетом групп составляющих и характеристик изделия.

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

3 Комплекс программ для создания эскизов одежды

3.1 Общая схема программного комплекса и методология проведения расчетов

3.2 База данных.

3.3 Модуль визуализации.

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

4.1 Задача формирования эскизов женских демисезонных пальто.

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

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

Актуальность темы исследования. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, управлении, исследовании социально-экономических, технических и других систем [6, 19, 20, 37, 45, 46, 88, 99, 101]. Весьма актуальным является направление, связанное с процессами создания сложных изделий, которые комбинируются из большого числа разнотипных элементов с учетом логических, ресурсных и других ограничений.

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

В настоящее время в области создания сложных изделий имеются системы, которые обеспечивают высокое качество принимаемых решений, сокращают расход ресурсов и время на изготовление новых изделий, повышают эффективность труда специалистов [1, 4, 7, 47, 102 - 104]. Вместе с тем в указанных разработках недостаточно применяются модели и методы оптимизации, что во многих случаях приводит к перебору и сравнению большого числа вариантов.

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

Задачи дискретной оптимизации с логическими ограничениями достаточно интересны как в теоретическом, так и в прикладном отношении. Наиболее известными среди них являются задачи выполнимости (задача SAT) и максимальной выполнимости логической формулы (задача MAX-SAT). Имеется значительное число работ, посвященных изучению сложности и структуры этих задач, выделению полиномиально разрешимых случаев и семейств «трудных» задач, разработке точных и приближенных алгоритмов их решения, различных эвристик, проведению теоретического и экспериментального анализа алгоритмов [17, 21, 56, 62, 64]. Среди основных методов, на которых базируются разрабатываемые алгоритмы, можно выделить методы расщепления, ветвей и границ, отсечения, перебора L-классов, локальный поиск и ряд других [2, 3, 24, 28 - 31, 38, 39, 69, 79, 92].

Одним из широко известных подходов к решению задач SAT и MAX-SAT является использование аппарата целочисленного линейного программирования (ЦЛП). Для анализа задач целочисленного программирования (ЦП), построения и исследования алгоритмов А.А. Колоколовым был предложен метод регулярных разбиений [27]. С использованием этого подхода исследована сложность решения ряда задач, изучена структура релаксационных множеств, рассмотрены вопросы устойчивости задач и алгоритмов, получены оценки числа итераций и ряд других важных теоретических результатов.

Значительное число исследований проведено на основе L-разбиения, в частности, для задач SAT и MAX-SAT, которые показали перспективность его применения [24, 28 - 30, 38, 39, 51, 78, 79, 81]. Поэтому актуальным является дальнейшее использование метода регулярных разбиений для анализа и решения задач с логическими и ресурсными ограничениями.

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

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

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

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

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

4. Создать программный комплекс для апробации развиваемого подхода на примере построения эскизов одежды.

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

На защиту выносятся:

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

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

3. Комплекс программ для построения эскизов одежды, разработанный на основе развиваемого подхода к формированию сложных изделий.

Научная новизна работы состоит в следующем:

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

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

3. Указанные математические модели и алгоритмы применены к построению эскизов одежды с учетом логических и ресурсных ограничений.

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

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

Апробация работы. Основные результаты диссертации опубликованы в работах [11 - 16, 33 - 36, 52, 80] и докладывались на следующих конференциях и семинарах: II межвузовской научно-практической конференции студентов и аспирантов «Молодежь, наука, творчество - 2004» (г. Омск, 2004); Российской конференции «Дискретный анализ и исследование операций» (DAOR'04) (г. Новосибирск, 2004); V Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск, 2004); межвузовской научно-методической конференции «Модернизация профессионального образования в условиях интеграции: проблемы обеспечения качества» (г. Омск, 2005); XIII Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Иркутск, 2005); Международной конференции «Operations Research 2005» (г. Бремен, Германия, 2005); III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2006); Третьей азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (г. Бишкек, 2007); VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (г. Омск, 2007); научных семинарах в Омском государственном университете им. Ф.М. Достоевского, Омском филиале Института математики им. C.JI. Соболева СО РАН и Институте вычислительной математики и математической геофизики СО РАН.

Публикации. По теме диссертации опубликовано 12 печатных работ, 2 из них в рецензируемых изданиях из списка ВАК.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гуселетова, Ольга Николаевна

Заключение

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

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

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

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

4. Создан комплекс программ для построения эскизов одежды, который применен в учебном процессе при подготовке специалистов в области оптимизации и сфере сервиса.

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

1. Абдулин С.Ф. Системы автоматизированного проектирования и управления: Аннотированный ретроспективный библиографический указатель (1990 - 2000г.г.). - Омский государственный институт сервис. - 2001. - 234 с.

2. Аделыпин А.В. Задача максимальной выполнимости и некоторые алгоритмы целочисленного программирования: Труды межд. семинара, посвященного 90-летию со дня рождения С.Н. Черникова. Екатеринбург: Уро РАН. - 2002. - С. 235 - 239.

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

4. Андреева М.В., Холина Т.Ю. Конструктивное моделирование в САПР "Ассоль"// Швейн. пром-сть. 2001. - №1. - С. 34 - 37.

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

6. Береснев B.J1. Дискретные задачи размещения и полиномы от булевых переменных. Изд-во Ин-та математики, Новосибирск, 2005. - 408 с.

7. Булатова Е.Б., Размахнина В.В., Ещенко В.Г. Компьютерные технологии проектирования одежды на базе системы "Грация"// Швейн. пром-сть. 2000. - № 1. - С. 38 - 40.

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

9. Гегечкори Е.Т. К вопросу о формировании исходного множества альтернатив в принятии управленческих решений // Матер. V Межд. науч. техн. конф. Омск: Изд-во ОмГТУ, 2004. Кн. 2. -С. 261 - 264.

10. Гусейнов Г.М., Ермилова В.В., Ермилова Д.Ю. и др. Композиция костюма: Учеб. пособ. для студ. высш. учеб. завед. М.: Издательский центр "Академия". - 2003. - 432 с.

11. Гуселетова О.Н. Об одном алгоритме решения задач дискретной оптимизации с логическими ограничениями // Динамика систем, механизмов и машин: Матер. VI Междунар. науч.-техн. конф. -Омск: Изд-во ОмГТУ, 2007. Кн.З - С. 26 - 30.

12. Гуселетова О.Н., Колоколов А.А. Решение задач дискретной оптимизации с логическими ограничениями при проектировании сложных изделий // Автоматика и телемеханика, 2008. № 10. -С. 176 - 182.

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

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

15. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Изд-во НГУ, Новосибирск, 1996. - 167 с.

16. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрГУ -Центр "Фактория Пресс", 2000. - 303 с.

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

18. Забиняко Г.И. Пакет программ целочисленного линейного программирования //Дискретный анализ и исследование операций. 1999. Т.6. -№ 2. - С. 32 - 41.

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

20. Козлова Т.В. Основы теории проектирования костюма: Учеб. Для вузов. М.: Легпромбытиздат. - 1988. - 352 с.

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

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

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

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

25. Колоколов А.А., Девятерикова М.В., Заозерская JI.A. Регулярные разбиения в целочисленном программировании: Учебное пособие. -Омск: ОмГУ. 2007. - 48 с.

26. Колоколов А.А., Нагорная З.Е., Ярош А.В. Системы автоматизированного проектирования в сервисе: Уч. пособие. Ч 1. Омск: ОГИС, 2006.

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

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

29. Колоколов А.А., Ярош А.В. Автоматизация некоторых этапов проектирования одежды на основе моделей дискретной оптимизации // Препринт. Омск: Изд-во ОмГТУ. 2004. -24 с.

30. Колоколов А.А., Ярош А.В. Применение некоторых многокритериальных задач дискретной оптимизации для автоматизации проектирования одежды // Всероссийская конф. "Проблемы оптимизации и экономические приложения". Омск: ОФ ИМ СО РАН. - 2003. - С. 174.

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

32. Мухачева Э.А., Валеева А.Ф., Мухачева А.С. Методы локального поиска в дискретных задачах оптимального распределения ресурса. Изд-во УГАТУ, Уфа, 2001. - 103 с.ш

33. Попков В.К. Математические модели связности // В.К. Попков, Отв. ред. А.С. Алексеев. 2-е изд., испр. и доп. - Новосибирск: Изд. ИВМиМГ СО РАН. - 2006. - 490 с.

34. Солтанбаева Г.Ш. Разработка метода автоматизированного проектирования конструкций новых моделей одежды: Автореф. дис. канд. техн. наук. М. - 1992.

35. Страуструп Б. Язык программирования С++. Специальное издание. М.: Бином. - 2001. - 1099 с.

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

37. Федоров А., Елманова Н. Базы данных для всех. М.: КомпьютерПресс. - 2001. - 256 с.

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

39. Aytemiz Т. A probabilistic study of 3-Satisfiability. Dissertation for the degree of Doctor of Philosophy. 2001. - 119 p.

40. 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.

41. Blair С.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.

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

43. 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.

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

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

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

47. 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.

48. 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.

49. Franco J., Van Gelder A. A perspective on certain polynomial time solvable classes of Satisfiability // Discrete Applied Mathematics.

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

51. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989.

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

53. Gu J., Purdom P. W., Franco J., Wah B. W. Algorithms for the Satisfiability (SAT) Problem: A Survey DIMACS Series in Discrete Mathematics and Theoretical Computer Science. - 1996. - P. 131.

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

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

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

57. 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.

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

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

60. 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.

61. Kautz H., Selman B. Planning as Satisfiability, in Proceedings of the 10th European Conference on Artificial Intelligence (ECAI 92), August 1992.

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

63. Kolokolov A., Adelshin A., Cheredova J. The L-Partition Approach To SAT And MAX SAT // Annual Conference of the GOR. Book of Abstracts. 2001. - P. 118.

64. Kolokolov A., Devyaterikova M., Cheredova J. A Study of Satisfiability Problem Using L-Partition // International Conference on Operations Research.Book of Abstracts. TU Dresden. 2000. - P. 39.

65. Kolokolov A., Guseletova O., Yarosh A. Application of Some Discrete Optimization Methods to Computer-Added Design of Clothes // International Conference on Operations Research 2005, Bremen. 2005.- P. 107.

66. Kolokolov A., Kallrath J., Yagofarova D. Analysis and Solving the Satisfiability Problem using L-partition International Conference on Operations Research 2003, Heidelberg. - 2003. - P. 128.

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

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

69. 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.

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

71. Monien В., Speckenmeyer E. Solving Satisfiability in less then2n steps. // Discrete Applied Mathematics 10, 1985. P. 287 - 295.

72. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. A Wiley-Interscience Publication: John Wiley and Sons, inc., 1999.

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

74. 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.

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

76. Reeves C. Genetic Algorithms for the Operation Researcher // INFORMS Journal on Computing. 1997. - Vol.9, №3. - P. 231 -250.

77. Resende M.G.C., Feo T.A. A GRASP for Satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 26: Clicues, Coloring and Satisfiability: Second DIMACS Challenge, 1996, P. 499 520.

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

79. Selman В., Kautz H., Cohen B. Local Search Strategies for Satisfiability Testing. DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 26: Clicues, Coloring and Satisfiability: Second DIMACS Challenge, 1996. P. 521 - 531.

80. Spears M.W. Simulated Annealing for Hard Satisfiability Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 26: Clicues, Coloring and Satisfiability: Second DIMACS Challenge, 1996. P. 533 - 557.

81. 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.

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

83. Vijey V. Vazirani. Approximation Algorithms, j j Springer, 2001.

84. Yannakakis M. On the approximation of maximum satisfiability // Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms. -1992. P. 1 - 9.

85. Zvi Drezner, Horst W. Hamacher. Facility Location. Approximations and Theory. // Springer Verlag, 2004.102. http://www.aomt.kiev.ua103. http://sapr.ru104. http://corp. fortdialog. ru/nd/sapr/unigraphics/