TWO METHODS OF SOLVING THE SYSTEM OF DIFFERENCE AND INTERVAL CONSTRAINTS
Abstract
We develop two methods of solving DBM system. One method is based on Fourier – Motskin
elimination scheme, it has complexity O(n3) for finding initial solve and complexity O(n3) for finding solve by changing one of variable value for some cases. The other method is based on the network of constraints approach, it has complexity O(n3) for finding initial solve and O(n) or approximately for finding solve by changing one of variable value if it is limited by special bounds.
About the Authors
I. V. Rubanov
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
M. S. Barketau
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
M. Y. Kovalyov
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Рубанов, И.В. Задача выбора маршрутов движения объектов при ограничении на сближение / И.В. Рубанов, М.С. Баркетов, М.Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск : ОИПИ НАН Беларуси, 2014. – С. 136–140.
2. Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France : Vérimag, 2006. – 15 p.
3. Bellman, R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. – 1958. – Vol. 16, no. 1. – P. 87–90.
4. Данциг, Дж. Линейное программирование, его применения и обобщения / Дж. Данциг. – М. : Прогресс, 1966. – 600 с.
5. Кормен, Т. Алгоритмы, построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; пер. с англ. под. ред. А. Шеня. – М. : МЦНМО, 2002. – 960 с.
6. Писарук, Н.Н. Исследование операций / Н.Н. Писарук. – Минск : БГУ, 2015. – 304 c.
7. Solving Systems of Difference Constraints Incrementally / G. Ramalingam [et al.] // Algorithmica. – 1999. – Vol. 23. – P. 261–275.
8. Fourier, J.B.J. Solution d'une question particulière du calcul des inégalités / J.B.J. Fourier. – France, 1826.
9. Герман, В.Н. Решение линейных ограничений над полем вещественных и рациональных чисел / В.Н. Герман // Кибернетика и системный анализ. – 2010. – № 4. – С. 123–133.
10. On Solving Boolean Combinations of UTVPI Constraints / Sanjit A. Seshia [et al.] // J. on Satisfability, Boolean Modeling and Computation. – 2007. – Vol. 3. – P. 67–90.
Review
For citations:
Rubanov I.V., Barketau M.S., Kovalyov M.Y. TWO METHODS OF SOLVING THE SYSTEM OF DIFFERENCE AND INTERVAL CONSTRAINTS. Informatics. 2016;(3):67-69. (In Russ.)
Views: 3534
Email this article 