In the paper, we analize discrete optimization problems with logical constraints based on integer linear programming models and L-partition approach. We obtain an upper bound for the power of any L-complex of the 2-SAT polytope. The use of this evaluation allows to solve some applied problems of designing complex products by these approaches much more efficiently.
Download file
Counter downloads: 269
- Title Analysis and solution of discrete optimization problems with logical constraints on the base of L-partition approach
- Headline Analysis and solution of discrete optimization problems with logical constraints on the base of L-partition approach
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(30)
- Date:
- DOI
Keywords
задача выполнимости, логические ограничения, целочисленное программирование, L-разбиение, satisfiability problem, logical constraints, integer programming, L-partitionAuthors
References
Колоколов А. А., Адельшин А. В., Ягофарова Д. И. Решение задачи выполнимости с использованием метода перебора L-классов // Информационные технологии. 2009. №2. С.54-59.
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. American Mathematical Society, 1996. P. 19-152.
Hamadi Y., Jabbour S., and Sais L. ManySAT: a parallel SAT solver // J. Satisfiability, Boolean Modeling and Comput. 2009. No. 6. P. 245-262.
Thornton J., Bain S., 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.
Колоколов А. А., Адельшин А. В., Ягофарова Д. И. Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений // Прикладная дискретная математика. 2013. №1(19). С. 99-109.
Адельшин А. В., Кучин А. К. Разработка алгоритмов решения смешанной задачи максимальной выполнимости // Материалы V Всерос. конф. «Проблемы оптимизации и экономические приложения». Омск, 2012. С. 99.
Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций. 1994. №2. С. 18-39.
Адельшин А. В. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика. 2004. №3. С. 35-42.
Ягофарова Д. И. Анализ L-структуры задачи 2-выполнимость // Материалы конф. «Под знаком 'Сигма'». Омск, 1994. С. 71-77.
Kolokolov A., Adelshin A., and Yagofarova D. Analysis and solving SAT and MAX-SAT problems using an L-partition approach // J. Math. Modeling Algorithm. 2013. No. 12(2). P. 201-212.
Cook S. A. The complexity of theorem-proving procedure // Proc. 3rd Annual ACM Symp. Theory of Computing. N. Y.: ACM, 1971. P. 151-159.
Колоколов А. А., Ярош А. В. Автоматизация проектирования сложных изделий с использованием дискретной оптимизации и информационных технологий // Омский научный вестник. 2010. №2(90). С. 234-238.
Посыпкин М. А, Заикин О. С., Беспалов Д. В., Семенов А. А. Решение задач криптоанализа поточных шифров в распределенных вычислительных средах // Труды ИСА. 2009. Т. 46. С. 119-137.
Massacci F. and Marraro L. Logical cryptanalysis as a SAT problem // J. Automated Reasoning. 2000. No. 24. P. 165-203.
Analysis and solution of discrete optimization problems with logical constraints on the base of L-partition approach | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 4(30).
Download full-text version
Counter downloads: 775