Вычислительные методы и программирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Выч. мет. программирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Выч. мет. программирование, 2011, том 12, выпуск 1, страницы 205–212 (Mi vmp186)  

Вычислительные методы и приложения

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

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

Институт динамики систем и теории управления СО РАН

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

Ключевые слова: обращение дискретных функций; задача выполнимости (SAT-задача); булевы уравнения; задачи комбинаторной оптимизации.

Полный текст: PDF файл (320 kB)
Тип публикации: Статья
УДК: 519.6

Образец цитирования: О. С. Заикин, И. В. Отпущенников, А. А. Семёнов, “Параллельные алгоритмы решения проблемы выполнимости в применении к оптимизационным задачам с булевыми ограничениями”, Выч. мет. программирование, 12:1 (2011), 205–212

Цитирование в формате AMSBIB
\RBibitem{ZaiOtpSem11}
\by О.~С.~Заикин, И.~В.~Отпущенников, А.~А.~Семёнов
\paper Параллельные алгоритмы решения проблемы выполнимости в применении
к оптимизационным задачам с булевыми ограничениями
\jour Выч. мет. программирование
\yr 2011
\vol 12
\issue 1
\pages 205--212
\mathnet{http://mi.mathnet.ru/vmp186}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmp186
  • http://mi.mathnet.ru/rus/vmp/v12/i1/p205

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вычислительные методы и программирование
    Просмотров:
    Эта страница:88
    Полный текст:41
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021