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

• Адельшин, Александр Владимирович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Адельшин, Александр Владимирович

Введение

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

1.1 Постановки задач и их сложность.

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

1.3 L-структура задач целочисленного программирования

1.4 Методы решения.

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

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

2.2 Построение специальных семейств логических формул

2.3 Анализ L-накрытий задач.

Глава 3. Разработка и анализ алгоритмов для задач максимальной и минимальной выполнимости

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

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

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

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

4.1 Исследование и сравнение алгоритмов точного решения

4.2 Исследование алгоритмов локального поиска.

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

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

Задачам, связанным с выполнимостью логических формул, посвящено значительное число работ в области дискретной оптимизации. Основными направлениями исследований являются разработка и анализ алгоритмов их решения, изучение структуры и сложности задач, выделение полиномиально разрешимых подклассов и построение семейств "трудных" задач для определенных классов алгоритмов [8, 41 - 47, 49, 51 - 54, 56, 57, 59, 63 - 66, 68, 69, 75, 76, 79 - 83, 86, 87, 89].

Одним из подходов к решению задач выполнимости и максимальной выполнимости является использование аппарата целочисленного линейного программирования (ЦЛП). В работах [41, 49, 66] используются модели ЦЛП для этих задач.

Для анализа задач целочисленного программирования (ЦП), разработки и исследования алгоритмов, основанных на релаксации условия целочисленности, А.А. Колоколовым был предложен метод регулярных разбиений [17]. Ранее с использованием этого подхода в [11, 14 - 17, 21, 35, 55, 74] и других работах исследована сложность решения ряда задач ЦП, изучена структура релаксационных множеств, введены новые классы отсечений, построены оценки числа итераций для некоторых известных алгоритмов, исследована устойчивость задач и алгоритмов, разработаны новые алгоритмы.

С помощью этого подхода начаты исследования задачи выполнимости, которые показали перспективность его применения [25]. Поэтому актуальным является дальнейшее использование указанного подхода для анализа задач с логическими ограничениями. С помощью него в диссертации исследуются задачи максимальной и минимальной выполнимости. Основные результаты получены на основе L-разбиения, которое является наиболее изученным среди регулярных разбиений.

В настоящее время проблематика ЦП является достаточно широкой и включает исследование структуры и сложности решения задач, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, приближенные и гибридные алгоритмы, метаэвристики, устойчивость задач и алгоритмов, многокритериальные постановки и ряд других [И, 16, 17, 21 - 23, 26 - 30, 32, 35 - 38, 55]. Во многих алгоритмах используется аппарат непрерывной оптимизации [13, 17, 31, 28, 36].

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

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

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

Кроме того, на построенных семействах задач исследовались алгоритмы перебора L-классов, ветвей и границ (метод Лэнд и Дойг) и двойственные дробные алгоритмы отсечения. Показано, что число итераций первых двух алгоритмов на некоторых семействах экспоненциально зависит от размерности задач, в то время как для первого алгоритма Го-мори число итераций растет линейно. Разработаны алгоритмы точного и приближенного решения невзвешенной задачи максимальной выполнимости, основанные на использовании метода перебора L-классов, лексикографическом переборе векторов и локальном поиске. Проведены экспериментальные исследования эффективности этих алгоритмов.

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

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

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

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

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

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

4. На предложенных семействах задач проведен анализ алгоритмов перебора L-классов, ветвей и границ (метод Лэнд и Дойг) и двойственных дробных алгоритмов отсечения. Показано, что число итераций алгоритмов перебора L-классов и ветвей и границ на некоторых семействах экспоненциально зависит от размерности задач, а число итераций первого алгоритма Гомори растет линейно.

Заключение

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

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

1. Аделыпин А.В. Задача минимальной выполнимости и некоторые алгоритмы дискретной оптимизации //Материалы конференции "Проблемы оптимизации и экономические приложения". Омск. - 2003. - С. 72.

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

3. Аделыпин А.В. Исследование задачи минимальной выполнимости с использованием L-разбиения //Информационный бюллетень Ассоциации мат. программирования. Вып. 10. - Екатеринбург: УрО РАН, 2003. - С. 19 - 20.

4. Аделыпин А.В. О сравнении некоторых алгоритмов целочисленного программирования //Материалы конференции "Дискретный анализ и исследование операций". Новосибирск, 2004. - С. 149.

5. Аделыпин А.В., Адельшина А.Г. К оценке числа итераций для двойственных алгоритмов отсечения //Вестник Омского университета. 2000. -т.- С. 14 - 16.

6. Аделыпин А.В., Колоколов А.А. Исследование задачи максимальной выполнимости с использованием L-разбиения //Материалыконференции "Дискретный анализ и исследование операций". Новосибирск, 2002. - С. 201.

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

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

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

10. Девятерикова М.В., Колоколов А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации //Автоматика и телемеханика. 2004. - т. - С. 48 - 54.

11. Девятерикова М.В., Колоколов А.А. Об устойчивости дробных накрытий задач целочисленного программирования //Междунар. конф. "Проблемы оптимизации и экономические приложения": Тез. докладов. Омск, 1997. - С. 59 - 61.

12. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во ИММ, 1998. - 247 с.

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

14. Заозерская Л.А. Исследование и решение некоторых классов задач целочисленного программирования на основе регулярных разбиений: Автореф. дис. канд. физ.-мат. наук. Омск, 1998. - 16 с.

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

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

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

18. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Решение задач выполнимости и некоторых ее обобщений с использованием метода перебора L-классов //Прикладная математика и информационные технологии. Омск, 2005. - С. 68 - 79.

19. Колоколов А.А., Адельшин А.В., Ягофарова Д.И. Алгоритмы лексикографического перебора для решения задачи выполнимости и некоторых ее обобщений //Труды XIII Байкальской международной школы-семинара. Иркутск, 2005. - Т.1. - С. 503 - 508.

20. Колоколов А.А., Девятерикова М.В. Анализ устойчивости L-разбиения множеств в конечномерном пространстве //Дискретный анализ и исследование операций, 2000. Серия 2. Т.7. - №2. - С. 47-53.

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

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

23. Колоколов А.А., Нагорная З.Е., Гуселетова О.Н., Ярош А.В. Математические модели и программный комплекс для проектирова-" ния эскизов одежды //Прикладная математика и информационные технологии. Омск, 2005. - С. 80 - 98.

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

25. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование.- М.: Наука, 1969. 368 с.

26. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Ю. Гибридные методы в дискретной оптимизации //Изв. АН СССР. Техн. кибернетика. -1988. т. - С. 65 - 77.

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

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

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

30. Попов Л.Д. Об одноэтапном методе решения лексикографических вариационных неравенств //Известия вузов. Математика. 1998. -№12 (439). - С. 71 - 81.

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

32. Семенова Н.В. Решение одной задачи обобщенного целочисленного программирования //Кибернетика. 1984. - №5. - С. 25 - 31.

33. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1988. - 472 с.

34. Симанчев Р.Ю. О вполне регулярных отсечениях для задач целочисленной оптимизации //Управляемые системы. Новосибирск: ИМ СО АН СССР, 1990. - Вып. 30. - С. 61 - 71.

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

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

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

38. Adelshin A.V., Kolokolov А.А. The L-partition approach to the MAX SAT problem //XXXIII International Conference on Operations Research AIR02002: Book of Abstracts. Italy, 2002. - P. 44.

39. Aspvall B. Recognizing disguised NR(1) instances of the satisfiability problem //Joutnal of algorithms. 1980. - V.l. - P. 97 - 103.

40. Aytemiz T. A probabilistic study of 3-Satisfiability. Dissertation for the degree of Doctor of Philosophy. 2001. - 119 pp.

41. Bertsimas D., Teo C., Vohra R. New randomized rounding algorithms. Preprint. 1995.

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

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

44. 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.l. - P. 21 - 32.

45. Boros E., Crama Y., Hammer P.L., Saks M. A coplexity index for satisfiability problems //SIAM Journal of Computing. 1994. - V.23.- P. 45 49.

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

47. Chandru V., Hooker J.N. Extended Horn sets in propositional logic //Journal of the ACM. 1991. - V.38. - P. 205 - 221.

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

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

50. Crescenzi P., Капп V. A compendium of NP optimization problems. -1995.

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

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

53. Dowling W.F., Gallier J.H. Linear-time algorithms for testing the satisfiability of propositional Horn formulae //Journal of Logic Programming. 1984. - V.l. - P. 267 - 284.

54. 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 Applicatios. Moscow, 1996. - P. 297 - 303.

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

56. Hansen P., Jaumard B. Algorithms for the maximum satisfiability problem //Computing. 1990. - V.44. - P. 279 - 303.

57. Hansen P., Jaumard В., Mladenovic N., Parreira A.D. Variable neighbourhood search for maximum weighted satisfiability problem //Technical Report G-2000-62. Les Cahiers du GERAD. Group for Research in Decision Analysis. 2000.

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

59. Hogg T. Refining the phase transition in combinatorial search. //Artifical Inteligence. 1996. - V.81. - P. 127 - 154.

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

61. Jaumard В., Stan M., Desrosiers J. Tabu search and quadratic relaxation for satisfiability problem //DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. V.26. - P." 457 - 477.

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

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

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

65. 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. P. 19 - 130.

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

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

68. Kohli R., Krishnamurti R., Mirchandani P. The minimum satisfiability problem //SIAM Journal on Discrete Mathematics. 1994. - №9. - P. 275-283.

69. Kolokolov A.A. On the L-structure of integer linear programming problems //System modelling and optimization. Proc. of the 16th IFIP" conference on the modelling and optimization. Springer Verlag, 1993. - P. 756 - 760.

70. Kolokolov A.A. Regular partitions and cuts in the integer programming //Discrete Analysis and Operations Research. Kluver Academic Publishers. Netherlands, 1996. - P. 59 - 79.

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

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

73. Kolokolov A.A., Eremeev A.V., Zaozerskaya L.A. On hybrid L-class enumeration and genetic algorithm for set covering problem //15th Conference of International Federation of Operational Research Societies (IFORS'99): Abstracts. Pekin, 1999. - P. 117.

74. Lewis H.R. Renaming a set of clauses as a Horn set //Journal of the ACM. 1978. - V.25. - P. 134 - 135.

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

76. Monien В., Speckenmeyer E. Solving satisfiability in less then 271 steps //Discrete Applied Mathematics. 1985. - V.10. - P. 287 - 295.

77. Niedermeier R., Rossmanith P. New upper bounds for maximum satisfiability //Journal of Algorithms. 2000. - V.36. - P. 63 - 88.

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

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

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

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

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

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

84. Truemper K. Alpha-balanced graphs and matrices GF(3)-representability of matroids //Journal of Combinatorial Theory.- 1982. V.32. - P. 112 - 139.

85. Truemper K. Effective logic computation. Wiley, New York, 1998.

86. Vohra R. Personal communication. 1995.

87. Yagiura M., Ibaraki Т. Analyses on the 2 and 3-flip neighbourhoods for the MAX SAT //Journal of Combinatorial Optimization. 1999. -V.3. - P. 95 - 114.

88. Yannakakis M. On the approximation of maximum satisfiability //Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms, 1992. ¥Г 1-9.90. www.cs.ubc.ca/~hoos/SATLIB/benchmMml91. www.dimacs.rutgers.edu/