Исследуется смешанная задача максимальной выполнимости на основе моделей целочисленного линейного программирования и метода регулярных разбиений. Установлена зависимость мощности произвольного L-комплекса многогранника указанной смешанной задачи с мощностью L-комплекса соответствующей задачи выполнимости, использование которой позволяет создавать и анализировать алгоритмы решения смешанной задачи, основанные на методе перебора L-классов.
Скачать электронную версию публикации
Загружен, раз: 200
- Title Исследование L-структуры многогранника смешанной задачи максимальной выполнимости
- Headline Исследование L-структуры многогранника смешанной задачи максимальной выполнимости
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 38
- Date:
- DOI 10.17223/20710410/38/9
Ключевые слова
логические ограничения, смешанная задача максимальной выполнимости, целочисленное программирование, L-разбиение, logical constraints, partial maximum satisfiability problem, integer programming, L-partitionАвторы
Ссылки
Колоколов А. А., Ярош А. В. Автоматизация проектирования сложных изделий с использованием дискретной оптимизации и информационных технологий // Омский научный вестник. 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.
Marathe M. V. and Ravi S. S. On approximation algorithms for the minimum satisfiability problem // Inform. Proc. Lett. 1996. V. 58. P.23-29.
Заикин О. С., Отпущенников И. В., Семенов А. А. Применение SAT-подхода к решению квадратичной задачи о назначениях // XV Байкальская Междунар. школа-семинар «Методы оптимизации и их приложения». Иркутск, 2011. С. 111-116.
Колоколов А. А., Адельшин А. В., Ягофарова Д. И. Решение задачи выполнимости с использованием метода перебора 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 Discr. Math. and Theor. Comput. Sci. 1996. V. 35. P. 19-152.
Hamadi Y., Jabbour S., and Sais L. ManySAT: a parallel SAT solver // J. Satisfiability, Boolean Modeling and Computation. 2009. No. 6. P. 245-262.
Thornton J., Bain S., Sattar A., and Pham D.N. A two level local search for MAX-SAT problems with hard and soft constraints // Proc. 15th Australian Joint Conf. 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. №1. С. 35-42.
Kolokolov A., Adelshin A., and Yagofarova D. Analysis and solving SAT and MAX-SAT problems using an L-partition approach // J. Math. Modeling. Algorithms. 2013. No. 12(2). P.201-212.
Колоколов А. А., Адельшин А. В. Анализ и решение задач дискретной оптимизации с логическими ограничениями на основе L-разбиения // Прикладная дискретная математика. 2015. №4(30). С. 100-108.
Исследование L-структуры многогранника смешанной задачи максимальной выполнимости | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/9
Скачать полнотекстовую версию
Загружен, раз: 456