Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph
Abstract
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.
References
- Bianco L., Confessore G., Gentili M. Combinatorial aspects of the sensor location problem. ann. oper. Res. Vol. 144, issue 1. 2006. P. 201–234. DOI: 10.1007/s10479-006-0016-9.
- Pilipchuk L. A. [Sparse underdetermined systems of linear algebraic equations]. Мinsk, 2012 (in Russ.).
- Pilipchuk L. A., Vishnevetskaya T. S., Pesheva Y. H. Sensor location problem for a multigraph. Math. Balk. New Ser. Vol. 27. Fasc. 1–2. 2013. P. 65–75.
- Pilipchuk L. A., Pilipchuk A. S., Ramanouski Y. V. Optimal location of sensors on a multigraph with zero split ratios of some arc flows. AIP Conf. Proc. 2014. Vol. 1631. P. 350 –353. DOI: 10.1063/1.4902497.
- Pilipchuk A. S. The location of the minimum number of monitored nodes in the generalized graph for estimating traffic its unobservable part. Vestnik BGU. Ser. 1, Fiz. Mat. Inform. 2015. No. 1. P. 108–111 (in Russ.).
- Pilipchuk L. A., Pilipchuk A. S. Sparse linear systems: theory of decomposition, methods, technology, applications and implementation in Wolfram Mathematica. AIP Conf. Proc. 2015. Vol. 1690, issue 1. DOI: 10.1063/1.4936744.
- Pilipchuk L. A., German O. V., Pilipchuk A. S. The general solutions of sparse systems with rectangular matrices in the problem of sensors optimal location in the nodes of a generalized graph. Vestnik BGU. Ser. 1, Fiz. Mat. Inform. 2015. No. 2. P. 91– 96.
The authors who are published in this journal agree to the following:
- The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
- The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)
