ГлавнаяАрхивИсследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений

Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений | Прикладная дискретная математика. 2013. № 1(19).

Рассматриваются различные постановки задач дискретной оптимизации с логическими ограничениями и возможности их применения для решения некоторых задач проектирования сложных изделий. Представлен обзор результатов исследования указанных задач на основе моделей целочисленного программирования и метода регулярных разбиений. С использованием данного подхода проведен анализ структуры и сложности задач, предложены алгоритмы решения задач выполнимости и максимальной выполнимости.
  • Title Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений
  • Headline Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 1(19)
  • Date:
  • DOI
Ключевые слова
задача выполнимости, логические ограничения, целочисленное программирование, перебор L-классов, satisfiability problem, logical constraints, integer programming, L-class enumeration
Авторы
Ссылки
Адельшин А. В., Кучин А. К. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Омский научный вестник. 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.
Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений | Прикладная дискретная математика. 2013. № 1(19).
Исследование задач дискретной оптимизации с логическими ограничениями на основе метода регулярных разбиений | Прикладная дискретная математика. 2013. № 1(19).
Полнотекстовая версия