Decomposition in Multidimensional Boolean-Optimization Problems with Sparse Matrices
- Authors: Kovkov D.V.1, Lemtyuzhnikova D.V.2
-
Affiliations:
- Dorodnicyn Computing Center
- Moscow Aviation Institute (National Research University)
- Issue: Vol 57, No 1 (2018)
- Pages: 97-108
- Section: Discrete Systems
- URL: https://journals.rcsi.science/1064-2307/article/view/220059
- DOI: https://doi.org/10.1134/S1064230718010033
- ID: 220059
Cite item
Abstract
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.
About the authors
D. V. Kovkov
Dorodnicyn Computing Center
Email: darabbt@gmail.com
Russian Federation, Moscow, 119333
D. V. Lemtyuzhnikova
Moscow Aviation Institute (National Research University)
Author for correspondence.
Email: darabbt@gmail.com
Russian Federation, Moscow, 125993