Методы интеграции логического программирования и программирования в ограничениях тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Петров, Евгений Сергеевич

• Петров, Евгений Сергеевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Петров, Евгений Сергеевич

Введение и структура работы

1 Сходимость в нёдоопределенных вычислительных моделях

1.1 Определения .,.

1.2 Локальная совместность

1.3 Недоопределенные модели.

1.4 Недоопределенные вычисления.

1.5 Иллюстративный пример.

1.6 Сходимость вычислений в моделях с интервальной недо-определенностью

1.6.1 Дополнительные обозначения

1.6.2 Линейные уравнения с точки зрения НЗ

1.6.3 Технические леммы.

1.6.4 Исследование сходимости.

1.6.5 Связь с классическими методами.

2 Интеграция логического программирования и недоопре-деленных вычислительных моделей

2.1 Математическая логика и программирование.

2.1.1 Логическое программирование в ограничениях

2.1.2 ^-программирование

2.2 Система ЕСУРБ

2.2.1 Мета-термы

2.2.2 Отложенные цели.

2.3 Модельный пример

2.4 Интеграция недоопределенных вычислений в систему ЕСГ/РБ

2.4.1 Вычислительная сеть.

2.4.2 Организация управления.

3 Инструментальные системы

Ьо^Сак

3.1 Программирование с множествами

3.1.1 Язык ЯЕТЬ.

3.1.2 Логическое программирование.

3.2 Система Ьо^Са1с

3.2.1 Множество значений переменных и констант

3.2.2 Язык системы Ьо^Са1с.

3.2.3 Примеры записи задач

3.3 Механизм работы системы Ьо^Са1с.

3.3.1 Множество недоопределенных значений.

3.3.2 Порождение системы ограничений.

3.3.3 Вычислительные функции.

3.4 Оптимизации НЗ в системе Ьо^Са1с.

3.5 Интенсиональные описания множеств.

3.5.1 Вычисление параметров

3.5.2 Вычисление множества.

3.6 Экстенсиональные описания множеств.

Интервальная библиотека

3.7 Обзор методов решения нелинейных ограничений.

3.8 Общая характеристика Интервальной библиотеки

3.9 Спецификация ограничений для Интервальной библиотеки

3.9.1 Вещественные ограничения

3.9.2 Целочисленные и смешанные ограничения.

3.10 Символьные преобразования.

3.10.1 Символьное дифференцирование.

3.10.2 Массивы и массовые ограничения.

3.10.3 Определение функций пользователем.

3.11 Специальные возможности.

3.11.1 Основные нематематические предикаты.

3.11.2 Технические особенности.

3.11.3 Оптимизации Ж в Интервальной библиотеке

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

Настоящая диссертация посвящена исследованию и развитию аппарата недоопределенных вычислительных моделей и его интеграции с логическим программированием. Недоопределенные вычислительные модели были предложены А. С. Нариньяни в начале 80-х годов в качестве средства представления и обработки знаний, и в настоящее время развиваются коллективом Российского института искусственного интеллекта и лабораторией Искусственного интеллекта Института систем информатики им. А. П. Ершова СО РАН. С начала 90-х годов недоопределенные вычислительные модели с успехом используются в программировании в ограничениях (CP от «Constraint Programming»). Отличительной чертой недоопределенных вычислительных моделей как метода CP является применимость к решению задач со смесью данных различных типов.

За последние двадцать лет в рамках CP разработан ряд специальных методов и на их основе создано большое число систем для решения прикладных задач в области автоматического проектирования, ресурсного планирования, задач моделирования в различных естественно-научных дисциплинах [40, 21, 33, 14, 54, 16, 61, 62, 63].

Для решения задач численного моделирования, возникающих в химии, роботике, механике, финансовой математике и, как правило, содержащих неточные или неполные данные, в CP и недоопределенных моделях широко используется интервальное представление неизвестных значений в сочетании с потоковым принципом управления [21, 33, 14, 54, 16]. Несмотря на популярность такого метода, число работ, в которых исследуется его сходимость и другие теоретические свойства невелико [2, 59].

В главе 1 автор исследует сходимость в недоопределенных вычислительных моделях при решении линейных уравнений.

Глава 2 посвящена подходам к интеграции CP и логического программирования. Необходимость в такой интеграции возникает при создании на основе методов СР полноценных приложений. Известные системы логического программирования в ограничениях изначально ориентированы на определенные (иногда весьма экзотические) классы задач [19, 15, 29, 25]. Интеграция логического программирования и недо-определенных вычислительных моделей позволяет разрабатывать системы логического программирования в ограничениях, настраиваемые на предметную область решаемой задачи.

В главе 3 описываются две инструментальные разработки автора: интерпретатор Ьо^Са1с и Интервальная библиотека для системы логического программирования ЕСЬгР8е.

Богатый класс задач из области программирования в ограничениях образуют так называемые задачи с конечными областями значений переменных — хорошо формализованные фрагменты задач распределения ресурсов и планирования. Важными объектами в таких задачах являются конечные множества и их отображения (графы). Задачи с конечными областями значений переменных принято сводить к задаче целочисленного программирования, в результате чего, как правило, увеличивается размерность задачи и на второй план отходит ее комбинаторная сущность. Перспективным является создание средств для представления и обработки непосредственно множеств [24, 29].

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

Далее в главе 3 описывается Интервальная библиотека для решения нелинейных ограничений в системе ЕС1/Р8е. В библиотеке использована одна из первых версий вычислительного ядра системы 11шса1с [14] в доработанном виде. Целью создания библиотеки было обоюдное расширение возможностей системы ЕСГ/РБ6 и недоопределенных вычислительных моделей и, кроме того, демонстрация практической применимости предложенного в главе 2 метода использования недоопределенных вычислительных моделей в логическом программировании.

Четвертая глава описывает результаты тестирования Интервальной библиотеки и разработанные на ее основе приложения для решения задач автоматического проектирования и финансового моделирования.

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Петров, Евгений Сергеевич

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

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

2. Разработаны средства представления и обработки множеств в недоопределенных вычислительных моделях. Разработанные средства позволяют использовать интенсиональные и экстенсиональные спецификации множеств для эффективного решения комбинаторных задач. Разработаны язык для описания таких задач и его интерпретатор 1^Юа1с. Предложенные средства представления и обработки множеств использованы в интерпретаторе 1^Юа1с.

3. Разработана Интервальная библиотека для системы логического программирования ЕС1/РЗе. Библиотека предназначена для автоматического учета при логическом выводе неполной информации о вещественных решениях нелинейных ограничений. Библиотека включает средства для спецификации массовых ограничений, символьных преобразований, управления процессом вычислений. На основе Интервальной библиотеки разработаны приложения для решения задач автоматического проектирования и моделирования финансовых операций.

Заключение

Исследования по тематике диссертационной работы были поддержаны грантом 96-01-01608 от Российского фонда фундаментальных исследований и грантом 98-06 от Франко-русского центра по прикладной математике и информатике им. А. М. Ляпунова.

Список литературы диссертационного исследования кандидат физико-математических наук Петров, Евгений Сергеевич, 1999 год

1. Д. К. Фаддеев, В. Н. Фаддеева. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963.

2. В. В. Телерман, Д. М. Ушаков. Недоопределенные модели: формализация подхода и перспективы развития. Там же.

3. Е. С. Петров. Сходимость метода недоопределенных вычислений при решении линейных уравнений. Там же.

4. Т. М. Яхно, Е. С. Петров. 1^1са1с: интеграция программирования в ограничениях и недоопределенных моделей. Программирование, 3:70-78, 1996.

5. А. И. Мальцев. Алгоритмы и рекурсивные функции. М.: Наука, 1965.

6. Ю. И. Манин. Вычислимое и невычислимое. М.:Советское радио, 1980.

7. А. С. Нариньяни. Недоопределенность в системе представления и обработки знаний. Известия АН СССР, Техническая кибернетика, 5:3-28, 1986.

8. Е. С. Петров. Интервальная библиотека: опыт интеграции логического программирования и недоопределенных моделей. Программирование, 4:40-49, 1998.

9. Ю. И. Журавлев. Об одном классе алгоритмов над конечными множествами. Доклады Академии наук СССР, 151(5):1025—1028, 1963.

10. Ю. J1. Ершов. Е-определимость в допустимых множествах. Доклады Академии наук СССР, 285(4):792-793, 1985.

11. С. С. Гончаров, Д. И. Свириденко. Математические основы семантического программирования. Доклады Академии наук СССР, 289(6) : 1324—1328, 1986.

12. А. В. Манцивода. Функционально-логический язык Флэнг. Кибернетика, 5:350-367, 1993.

13. F. Benhamou and W. J. Older. Applying interval arithmetic to real, integer and boolean constraints. Journal of Logic Programming, 1995.

14. N. Christofides. Graph theory: an Algorithmic Approach. Management Science. Academic Press, Imperial College, London, 1975.

15. J. Cohen. Constraint logic programming languages. Communications of the ACM, 33(7):52—68, July 1990.

16. E. Davis. Constraint propagation with interval labels. Artificial Intelligence, 32(3):281-331, 1987.

17. J. Dennis and R. B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Computational Mathematics. Prentice-Hall, 1983.

18. M. Dincbas, H. Simonis, P. Van Hentenryck, A. Aggoun, T. Graf, and E. Berthier. The constraint logic programming language CHIP. In FGCS'88, Tokyo, Japan, Nov. 1988. ICOT.

19. A. Dovier and G. Rossi. Embedding extensional finite sets in CLP. In Proc. 3rd Int. logic Programming Symp., Vancouver, Canada, 1993.

20. ECRC. ECU PS6 3.5: ECRC Common Logic Programming System. User's Guide., 1995.

21. E. J. Elton and M. J. Gruber. Modern Portfolio Theory and Investment Analysis. John Willey & Sons, Inc., New York, 1995.

22. E. C. Freuder. Synthesizing constraint expressons. Communications of the ACM, 21(11):958—966, 1978.

23. M. R. Garey and D. S. Johnson. Computers and Intractability. San Francisco: W. H. Freeman and Company, 1979.

24. C. Gervet. Conjunto: Constraint logic programming with finite set domains. In M. Bruynooghe, editor, ILPS'94: Proc. 4th Int. Logic Programming Symp., pages 339-358, 1994.

25. E. R. Hansen and R. I. Greenberg. An interval Newton method. Applied Mathematics and Computing, 12:89-98, 1983.

26. E. R. Hansen and S. Segupta. Bounding solutions of systems of equations using interval analysis. BIT, 21:203-211, 1981.

27. H. Hong and V. Stahl. Safe starting regions by fixed points and tightening. Computing, 53(3-4):323-335, 1994.

28. E. Hvvonen. Constraint reasoning based on interval arithmetic: the tolerance propagation approach. Artificial Intelligence, 58:71-112, 1992.

29. R. B. Kearfott, M. Dawande, K.-S. Du, and C.-Y. Hu. Algorithm 737: INTLIB: A portable FORTRAN-77 interval standard function library.

30. ACM Transactions on Mathematical Software, 20(4):447-459, 1994.35. 0. Knuppel. PROFIL/BIAS — a fast interval library. Computing, 53(3-4):277-287, 1994.

31. R. H. Koning. A Short Introduction to GAUSS, 1996.

32. R. Kowalski. Predicate logic as a programming language. In Proc. IFIP Congress, Stockholm, North-Holland, 1974.

33. B. Legeard and E. Legros. Short overview of the CLPS system. In Proc. PLILP'91, Passau, Germany, Aug. 1991.

34. D. Levin and I. Shvetsov. A novel end user facilities based on Subdefinite Calculations. In I. E. Shvetsov, editor, Representation and Processing of Partially Defined Knowledge, number 4 in Russian Research Institute of Artificial Intelligence, 1996.

35. A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99-118, 1977.

36. K. Meintjes and A. P. Morgan. Chemical equlilibrium problems as numerical test problems. ACM Transactions on Mathematical Software, 16:143-151, 1990.

37. R. E. Moore. Methods and Applications of Interval Analysis. SIAM Publ., 1979.

38. J. J. More and M. Y. Conard. Numerical solution of nonlinear equations. ACM Transactions on Mathematcial Software, 5:64-85, 1979.

39. A. P. Morgan. Solving polynomial systems using continuation for scientific and engineering problems. Englewood Cliffs: Prentice-Hall, NJ, 1987.

40. A. Narinyani, A. Semenov, T. Kashevarova, and A. Babichev. A new approach to solving algebraic systems by means of subdefinite models. In Proc. 16th IFIP Conf. on System and Modeling and

41. Optimization, volume 197 of Lecture Notes in Control and Computer Science, Compiegne, France, July 1993. Springer-Verlag.

42. A. S. Narinyani. Subdefinite set — a formal model of incompletely specified aggregate. In Proc. Symp. on Fuzzy Sets and Possibity Theory, Acapulco, Mexico, 1980.

43. A. S. Narinyani. Subdefiniteness and basic means of knowledge representation. Computers and Artificial Intelligence, 2(5):443-452, 1983.

44. A. S. Narinyani. Intelligent software technology for the new decade. Communication of the ACM, 34(6):60-67, 1991.

45. A. S. Narinyani, S. B. Borde, and D. A. Ivanov. Subdefinite mathematics and novel scheduling techniques. Artificial Intelligence in Enginieering, 11, 1997.

46. S. Nash. Newton-like minimization via the Lanczos method. SI AM Journal on Numerical Analysis, 21:770-788, 1984.

47. S. Nash and A. Sofer. BTN: Software for parallel unconstrained optimization. ACM Transactions on Mathematical Software, 18:414448, 1992.

48. W. J. Older and Vellino. Extending Prolog with constraint arithmetics on real intervals. In Proc.Canadian Conf. on Computer and Electrical Engineering, Ottawa, Canada, 1990.

49. M. Pereira, F. Pereira, and D. H. D. Warren. User's Guide to DECsystem-10 Prolog. University of Edingburgh: Department of Artificial Intelligence, 1978.

50. J.-F. Puget. A C++ implementation of CLP. In Proc.SPICIS, Singapore, 1994.

51. A. Schijver. Theory of Linear and Integer Programming. New York, John Willeyfe Sons, 1986.

52. R. B. Schnabel, J. E. Kootz, and B. E. Weiss. A modular system of algorithms for unconstrained minimization. ACM Transactions on Mathematical Software, 11:419-440, 1985.

53. J. Schwartz, R. Dewar, E. Dubinsky, and E. Schonberg. Programming with Sets. An Introduction to SETL. Texts and Monographs in Computer Science. Springer-Verlag, 1986.

54. A. Semenov, A. Babichev, T. Kashevarova, and A. Leschenko. UniCalc: a novel approach to solving systems of algebraic equations. In Proc.Int.Conf. on Numerical Analysis with Automatic Result Verification, pages 29-47, Lafayette, La, USA, Feb. 1993.

55. S. P. Shary. A new approach to the analysis of static systems under interval uncertainty. In G. Alefeld, A. Frommer, and B. Lang, editors, Scientific Computing and Validated Numerics, pages 118-132. Berlin: Akademic Verlag, 1996.

56. P. Van Hentenryck. Constraint Satisfaction in Logic Programming. The MIT Press, Cambridge, MA, 1989.

57. P. Van Hentenryck. Helios: A modeling language for global optimization. In Practical Application of Constraint Technology, pages 317 -335, 1996.

58. P. Van Hentenryck, D. McAllester, and D. Kapur. Solving polynomial systems using a branch and prune approach. SI AM Journal on Numerical Anahsys, 34, Apr. 1997.

59. P. Van Hentenryck, L. Michel, and Y. Deville. Numerica: a Modelling Language for Global Optimization. The MIT Press, Cambridge, MA, 1997.

60. J. Verschelde, P. Verlinden, and R. Cools. Homotopies exploiting newton polytopes for solving sparse polynomial systems. SIAM Journal on Numerical Analysis, 31(3):915-930, 1994.

61. C. Walinsky. CLP(E*): Constraint logic programming with regular sets. In G. Levi and M. Martelli, editors, Proc.6th Int.Conf. on Logic Programming, pages 181-196, Lisbon, Portugal, June 1989. The MIT Press.

62. T. M. Yakhno and E. S. Petrov. LogiCalc: integrating constraint programming and subdefinite models. In Practical Application of Constraint Technology, pages 357-372, Westminster Central Hall, London, UK, Apr. 1996.

63. T. M. Yakhno, V. Z. Zilberfaine, and E. S. Petrov. Applications of ECL'PS6: Interval Domain Library. In Practical Application of Constraint Technology, pages 339-357, Westminster Central Hall, London, UK, 1997.

64. T. M. Yakhno, V. Z. Zilberfaine, and E. S. Petrov. Applications of ECLlPSe: Interval Domain library. The ICL Systems Journal, pages 35-50, Nov. 1997.