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

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

Тип публикации: Материал конференции

Тип материала: Текст

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

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

Язык публикации: russian

Номера страниц: 501-508

Количество страниц: 8

Год публикации: 2011

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

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

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

Адрес издателя: Челябинск

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

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

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

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

Индексируется УБС: Нет

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

Индексируется ВАК: Нет

Индексируется CORE: Нет