51930

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

ДЕКОМПОЗИЦИЯ В МНОГОМЕРНЫХ ЗАДАЧАХ БУЛЕВОЙ ОПТИМИЗАЦИИ С РАЗРЕЖЕННЫМИ МАТРИЦАМИ

ISBN/ISSN: 

0002-3388

DOI: 

10.7868/S0002338818010109

Наименование источника: 

  • Известия Российской академии наук. Теория и системы управления

Обозначение и номер тома: 

№1

Город: 

  • Москва

Издательство: 

  • РАН

Год издания: 

2018

Страницы: 

98-110
Аннотация
Представлен обзор по проблемам, связанным с разреженными матрицами. Сформулирован ряд теорем о выделении квазиблочной структуры в разреженной матрице, а также о связи степени квазиблочной структуры и числа ее блоков в зависимости от размерности матрицы и числа ненулевых элементов в ней. Рассмотрены алгоритмы для решения целочисленных задач оптимизации с разреженными матрицами квазиблочной структуры. Представлены алгоритмы выделения квазиблочных структур. Описан локальный элиминационный алгоритм, который эффективен для задач с матрицами квази- блочной структуры. Изучается проблема оптимальной последовательности исключения переменных в локальном элиминационном алгоритме. Для этого сформулирован ряд понятий и доказаны свойства графовых структур, соответствующих порядку решения подзадач. Проведено тестирование для различных порядков исключения переменных.

Библиографическая ссылка: 

Лемтюжникова Д.В., Ковков Д.В. ДЕКОМПОЗИЦИЯ В МНОГОМЕРНЫХ ЗАДАЧАХ БУЛЕВОЙ ОПТИМИЗАЦИИ С РАЗРЕЖЕННЫМИ МАТРИЦАМИ // Известия Российской академии наук. Теория и системы управления. 2018. №1. С. 98-110.