Страница публикации
Параллельные алгоритмы решения проблемы выполнимости в применении к оптимизационным задачам с булевыми ограничениями
Авторы: Заикин О.С., Отпущенников И.В., Семенов А.А.
Журнал: Вычисл. методы и программирование: новые вычисл. технологии
Том: 12
Номер: 1
Год: 2011
Отчётный год: 2011
Издательство:
Местоположение издательства:
URL:
Аннотация: Предложена параллельная технология, которая может использоваться при решении ряда задач дискретной оптимизации. Технология основана на эффективных процедурах сведения задач комбинаторной оптимизации к задачам выполнимости (SAT-задачам). Процесс решения оптимизационной задачи реализован в виде итерационной схемы, каждый этап которой - это решение некоторой SAT-задачи. Получаемые SAT-задачи решаются при помощи различных схем распараллеливания. Для учета информации, накопленной в предыдущих итерациях, реализована техника "Incremental SAT", применяемая в задачах верификации моделей дискретных систем. Разработанная технология была протестирована на некоторых комбинаторных задачах, в частности на квадратичной задаче о назначениях. Работа выполнена при поддержке гранта "Лаврентьевский конкурс молодежных проектов СО РАН" на 2010-2011 гг. и при финансовой поддержке РФФИ (код проекта 11-07-00377-а). Статья рекомендована к публикации Программным комитетом Международной научной конференции "Параллельные вычислительные технологии" (ПАВТ-2011; http://agora.guru.ru/pavt2011).
Индексируется WOS: 0
Индексируется Scopus: 0
Индексируется РИНЦ: 1
Публикация в печати: 0
Добавил в систему: