51838

Автор(ы): 

Автор(ов): 

2

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

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

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

Название: 

Decomposition in Multidimensional Boolean-Optimization Problems with Sparse Matrices

ISBN/ISSN: 

1064-2307

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

  • Journal of Computer and Systems Sciences International

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

Volume 57, Issue 1

Город: 

  • Москва

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

  • Pleiades Publishing

Год издания: 

2018

Страницы: 

97–108
Аннотация
In this paper, we review problems associated with sparse matrices. We formulate several theorems on the allocation of a quasi-block structure in a sparse matrix, as well as on the relation of the degree of the quasi-block structure and the number of its blocks, depending on the dimension of the matrix and the number of nonzero elements in it. Algorithms for the solution of integer optimization problems with sparse matrices that have the quasi-block structure are considered. Algorithms for allocating the quasi-block structures are presented. We describe the local elimination algorithm, which is efficient for problems with matrices that have a quasi-block structure. We study the problem of an optimal sequence for the elimination of variables in the local elimination algorithm. For this purpose, we formulate a series of notions and prove the properties of graph structures corresponding to the order of the solution of subproblems. Different orders of the elimination of variables are tested.

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

Лемтюжникова Д.В., Ковков Д.В. Decomposition in Multidimensional Boolean-Optimization Problems with Sparse Matrices / Journal of Computer and Systems Sciences International. М.: Pleiades Publishing, 2018. Volume 57, Issue 1. С. 97–108.

Публикация имеет версию на другом языке: 

Да

Связь с публикацией: