Some discrete optimization problems with logical constraints are considered, and the possibility of applying these problems in complex products design is investigated. The results of the studying these problems with the use of the integer programming models and regular partitions approach are reviewed. The structure and the complexity of the problems are analysed, and the algorithms for SAT and MAX-SAT problems based on this approach are proposed.
Download file
Counter downloads: 70
- Title Study of discrete optimization problems with logical constraints based on regular partitions
- Headline Study of discrete optimization problems with logical constraints based on regular partitions
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(19)
- Date:
- DOI
Keywords
задача выполнимости, логические ограничения, целочисленное программирование, перебор L-классов, satisfiability problem, logical constraints, integer programming, L-class enumerationAuthors
References
Адельшин А. В., Кучин А. К. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Омский научный вестник. 2011. №1(97). С. 5-9.
Колоколов А. А., Адельшин А. В., Ягофарова Д. И. Алгоритмы лексикографического перебора для решения задачи выполнимости и некоторых её обобщений // Труды XIII Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». Иркутск, 2005. Т. 1. С.503-508.
Колоколов А. А., Чередова Ю. Н. Исследование и решение задачи о выполнимости с использованием L-разбиения // Материалы междунар. конф. «Дискретный анализ и исследование операций». Новосибирск, 2000. С. 150.
Massacci F. and Marraro L. Logical cryptanalysis as a SAT problem // J. Automated Reasoning. 2000. No. 24. P. 165-203.
Посыпкин М. А, Заикин О. С., Беспалов Д. В., Семенов А. А. Решение задач криптоанализа поточных шифров в распределенных вычислительных средах // Труды ИСА. 2009. Т. 46. С. 119-137.
Колоколов А. А., Серышева Ю. С., ШулеповаЛ.Д. Решение задач формирования малых групп с учетом межличностных отношений // Труды XV Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». Иркутск, 2011. Т. 5. С. 61-66.
Гуселетова О. Н., Колоколов А. А. Решение задач дискретной оптимизации с логическими ограничениями при проектировании сложных изделий // Автоматика и телемеханика. 2008. №10. С. 176-182.
Адельшин А. В., Жовнер Е. Н. Применение задач выполнимости логической формулы для проектирования химического состава резин // Вестник Омского университета. 2011. №2. С. 14-18.
Колоколов А. А., Ярош А. В. Автоматизация проектирования сложных изделий с использованием дискретной оптимизации и информационных технологий // Омский научный вестник. 2010. №2(90). С. 234-238.
Cook S. A. The complexity of theorem-proving procedure // Proc. 3rd Annual ACM Symposium on the Theory of Computing. New York: ACM, 1971. P. 151-159.
Колоколов А. А., Адельшин А. В., Чередова Ю. Н. Применение L-разбиения к исследованию некоторых задач выполнимости // Труды XII Байкальской междунар. конф. «Методы оптимизации и их приложения». Иркутск, 2001. Т. 1. С. 166-172.
Адельшин А. В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика. 2004. №1. С. 35-42.
Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций. 1994. №2. С. 18-39.
Thornton J., BainS., Sattar A., and PhamD.N. A two level local search for MAX-SAT problems with hard and soft constraints // Proc. 15th Australian Joint Conference on Artificial Intelligence, AustAI-2002. Canberra, Australia, 2002. P. 603-614.
Hansen P. and Jaumard B. Algorithms for the maximum satisfiability problem // Computing. 1990. No. 4. P. 279-303.
Gu J., Purdom P., Franco J., and Wah B. Algorithms for the satisfiability (SAT) problem: a survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Princeton: AMS, 1996. P. 19-152.
Колоколов А. А., Адельшин А. В., Ягофарова Д. И. Решение задачи выполнимости с использованием метода перебора L-классов // Информационные технологии. 2009. №2. С.54-59.
Study of discrete optimization problems with logical constraints based on regular partitions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 1(19).
Download full-text version
Download fileCounter downloads: 234