Previous |  Up |  Next


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:
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
EuDML logo