Страница публикации

Параллельные алгоритмы решения SAT в применении к оптимизационным задачам с булевыми ограничениями

Авторы: Заикин О.С., Отпущенников И.В., Семенов А.А.

Журнал: Тр. Междунар. конф. "Параллельные вычисл. технологии" (ПаВТ'2011, Москва, 28 марта-1 апреля 2011г.)

Том:

Номер:

Год: 2011

Отчётный год: 2011

Издательство: Издательский центр ЮУрГУ

Местоположение издательства: Челябинск

URL:

Аннотация: Предложена параллельная технология, применимая к целому ряду задач дискретной оптимизации, и использующая концепцию крупноблочного параллелизма. Технология основана на эффективных процедурах сведения задач комбинаторной оптимизации к SAT-задачам. Процесс решения исходной оптимизационной задачи реализован в виде итерационной схемы, каждый этап которой-это решение некоторой SAT- задачи. Получаемые SAT-задачи решаются при помощи крупноблочных параллельных алгоритмов. Для учета информации, накопленной в предыдущих итерациях, реализована техника «Incremental SAT», применяемая в задачах верификации многих дискретных систем. Разработанная технология была протестирована на решении задач 0-1-ЦЛП в распределенных вычислительных средах.

Индексируется WOS: 0

Индексируется Scopus: 0

Индексируется РИНЦ: 1

Публикация в печати: 0

Добавил в систему: