Decomposition in Multidimensional Boolean-Optimization Problems with Sparse Matrices
- Авторы: Kovkov D.1, Lemtyuzhnikova D.2
-
Учреждения:
- Dorodnicyn Computing Center
- Moscow Aviation Institute (National Research University)
- Выпуск: Том 57, № 1 (2018)
- Страницы: 97-108
- Раздел: Discrete Systems
- URL: https://journals.rcsi.science/1064-2307/article/view/220059
- DOI: https://doi.org/10.1134/S1064230718010033
- ID: 220059
Цитировать
Аннотация
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.
Об авторах
D. Kovkov
Dorodnicyn Computing Center
Email: darabbt@gmail.com
Россия, Moscow, 119333
D. Lemtyuzhnikova
Moscow Aviation Institute (National Research University)
Автор, ответственный за переписку.
Email: darabbt@gmail.com
Россия, Moscow, 125993
![](/img/style/loading.gif)