Article

 Title: Complete solution of tropical vector inequalities using matrix sparsification (English) Author: Krivulin, Nikolai Language: English Journal: Applications of Mathematics ISSN: 0862-7940 (print) ISSN: 1572-9109 (online) Volume: 65 Issue: 6 Year: 2020 Pages: 755-775 Summary lang: English . Category: math . Summary: We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples. (English) Keyword: tropical semifield Keyword: tropical two-sided inequality Keyword: matrix sparsification Keyword: complete solution Keyword: backtracking MSC: 15A39 MSC: 15A80 MSC: 65F50 idZBL: Zbl 07285955 idMR: MR4191367 DOI: 10.21136/AM.2020.0376-19 . Date available: 2020-11-18T09:37:56Z Last updated: 2021-04-08 Stable URL: http://hdl.handle.net/10338.dmlcz/148395 . Reference: [1] Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games.Int. J. Algebra Comput. 22 (2012), Article ID 1250001, 43 pages. Zbl 1239.14054, MR 2900854, 10.1142/S0218196711006674 Reference: [2] Allamigeon, X., Gaubert, S., Katz, R. D.: The number of extreme points of tropical polyhedra.J. Comb. Theory, Ser. A 118 (2011), 162-189. Zbl 1246.14078, MR 2737191, 10.1016/j.jcta.2010.04.003 Reference: [3] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems.Wiley Series in Probability and Statistics. Wiley, Chichester (1992). Zbl 0824.93003, MR 1204266 Reference: [4] Butkovič, P.: Max-Linear Systems: Theory and Algorithms.Springer Monographs in Mathematics. Springer, London (2010). Zbl 1202.15032, MR 2681232, 10.1007/978-1-84996-299-5 Reference: [5] Butkovič, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra.Ekon.-Mat. Obz. 20 (1984), 203-215. Zbl 0545.90101, MR 0782401 Reference: [6] Butkovič, P., Zimmermann, K.: A strongly polynomial algorithm for solving two-sided linear systems in max-algebra.Discrete Appl. Math. 154 (2006), 437-446. Zbl 1090.68119, MR 2203194, 10.1016/j.dam.2005.09.008 Reference: [7] Carré, B. A.: An algebra for network routing problems.J. Inst. Math. Appl. 7 (1971), 273-294. Zbl 0219.90020, MR 0292583, 10.1093/imamat/7.3.273 Reference: [8] Clifford, A. H., Preston, G. B.: The Algebraic Theory of Semigroups. Vol. 1.Mathematical Surveys and Monographs 7. American Mathematical Society, Providence (1961). Zbl 0111.03403, MR 0132791, 10.1090/surv/007.1 Reference: [9] Cuninghame-Green, R. A.: Projections in minimax algebra.Math. Program. 10 (1976), 111-123. Zbl 0336.90062, MR 0403664, 10.1007/BF01580656 Reference: [10] Cuninghame-Green, R. A.: Minimax Algebra.Lecture Notes in Economics and Mathematical Systems 166. Springer, Berlin (1979). Zbl 0399.90052, MR 0580321, 10.1007/978-3-642-48708-8 Reference: [11] Cuninghame-Green, R. A.: Minimax algebra and applications.Advances in Imaging and Electron Physics. Volume 90 Academic Press, San Diego (1994), 1-121. MR 0580321, 10.1016/S1076-5670(08)70083-1 Reference: [12] Cuninghame-Green, R. A., Butkovič, P.: The equation ${A}\otimes x={B}\otimes y$ over (max,+).Theor. Comput. Sci. 293 (2003), 3-12. Zbl 1021.65022, MR 1957609, 10.1016/S0304-3975(02)00228-1 Reference: [13] Cuninghame-Green, R. A., Butkovič, P.: Bases in max-algebra.Linear Algebra Appl. 389 (2004), 107-120. Zbl 1059.15001, MR 2080398, 10.1016/j.laa.2004.03.022 Reference: [14] Elsner, L., Driessche, P. van den: Max-algebra and pairwise comparison matrices. II.Linear Algebra Appl. 432 (2010), 927-935. Zbl 1191.15019, MR 2577637, 10.1016/j.laa.2009.10.005 Reference: [15] Gaubert, S., Katz, R. D.: The tropical analogue of polar cones.Linear Algebra Appl. 431 (2009), 608-625. Zbl 1172.52002, MR 2535537, 10.1016/j.laa.2009.03.012 Reference: [16] Gaubert, S., Katz, R. D., Sergeev, S.: Tropical linear-fractional programming and parametric mean payoff games.J. Symb. Comput. 47 (2012), 1447-1478. Zbl 1270.90081, MR 2929038, 10.1016/j.jsc.2011.12.049 Reference: [17] Golan, J. S.: Semirings and Affine Equations Over Them: Theory and Applications.Mathematics and Its Applications 556. Kluwer Academic, Dordrecht (2003). Zbl 1042.16038, MR 1997126, 10.1007/978-94-017-0383-3 Reference: [18] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms.Operations Research/Computer Science Interfaces Series 41. Springer, New York (2008). Zbl 1201.16038, MR 2389137, 10.1007/978-0-387-75450-5 Reference: [19] Heidergott, B., Olsder, G. J., Woude, J. van der: Max Plus at Work. Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications.Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2006). Zbl 1130.93003, MR 2188299, 10.1515/9781400865239 Reference: [20] Jones, D.: On two-sided max-linear equations.Discrete Appl. Math. 254 (2019), 146-160. Zbl 1407.15017, MR 3913099, 10.1016/j.dam.2018.06.011 Reference: [21] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications.Mathematics and Its Applications 401. Kluwer Academic, Dordrecht (1997). Zbl 0941.93001, MR 1447629, 10.1007/978-94-015-8901-7 Reference: [22] Krivulin, N. K.: Solution of generalized linear vector equations in idempotent algebra.Vestn. St. Petersbg. Univ., Math. 39 (2006), 16-26. MR 2302633 Reference: [23] Krivulin, N.: A multidimensional tropical optimization problem with a non-linear objective function and linear constraints.Optimization 64 (2015), 1107-1129. Zbl 1311.65086, MR 3316792, 10.1080/02331934.2013.840624 Reference: [24] Krivulin, N.: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems.Linear Algebra Appl. 468 (2015), 211-232. Zbl 1307.65089, MR 3293251, 10.1016/j.laa.2014.06.044 Reference: [25] Krivulin, N.: Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling.J. Log. Algebr. Methods Program. 89 (2017), 150-170. Zbl 1386.90174, MR 3634737, 10.1016/j.jlamp.2017.03.004 Reference: [26] Krivulin, N.: Complete algebraic solution of multidimensional optimization problems in tropical semifield.J. Log. Algebr. Methods Program. 99 (2018), 26-40. Zbl 1412.90143, MR 3811166, 10.1016/j.jlamp.2018.05.002 Reference: [27] Lorenzo, E., Puente, M. J. de la: An algorithm to describe the solution set of any tropical linear system ${A}\odot x={B}\odot x$.Linear Algebra Appl. 435 (2011), 884-901. Zbl 1217.65076, MR 2807241, 10.1016/j.laa.2011.02.014 Reference: [28] Sergeev, S.: Multiorder, Kleene stars and cyclic projectors in the geometry of max cones.Tropical and Idempotent Mathematics Contemporary Mathematics 495. American Mathematical Society, Providence (2009), 317-342. Zbl 1179.15033, MR 2581526, 10.1090/conm/495 Reference: [29] Sergeev, S., Wagneur, E.: Basic solutions of systems with two max-linear inequalities.Linear Algebra Appl. 435 (2011), 1758-1768. Zbl 1227.15018, MR 2810669, 10.1016/j.laa.2011.02.033 Reference: [30] Wagneur, E., Truffet, L., Faye, F., Thiam, M.: Tropical cones defined by max-linear inequalities.Tropical and Idempotent Mathematics Contemporary Mathematics 495. American Mathematical Society, Providence (2009), 351-366. Zbl 1357.15017, MR 2581528, 10.1090/conm/495 Reference: [31] Yoeli, M.: A note on a generalization of Boolean matrix theory.Am. Math. Mon. 68 (1961), 552-557. Zbl 0115.02103, MR 0126472, 10.2307/2311149 Reference: [32] Zimmermann, K.: A general separation theorem in extremal algebras.Ekon.-Mat. Obz. 13 (1977), 179-201. Zbl 0365.90127, MR 0453607 .

Fulltext not available (moving wall 24 months)

Partner of