Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph

The problem of locating sensors on the network to monitor flows has been object of growing interest in the past few years, due to its relevance in the field of traffic management and control. The basis for modeling the processes of estimating flows in generalized multinetwork is a sparse underdetermined system of linear algebraic equations of a special type. Sensors are located in the nodes of the multinetwork for the given traffic levels on arcs within range covered by the sensors, that would permit traffic on any unobserved flows on arcs to be exactly. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be $NP$-complete. In this paper the effective algorithms are developed to determine the ranks of the matrices of each of the independent subsystems obtained as a result of applying the theory of decomposition. From the equality of the sum of the ranks of the matrices of independent subsystems and the number of unknowns in independent subsystems, the uniqueness conditions for the solution of a special sparse system of linear algebraic equations follow. The results of the research can also be applied to constructing optimal solutions to problems of mathematical programming.