Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
tropical semifield; tropical two-sided inequality; matrix sparsification; complete solution; backtracking
tropical semifield; tropical two-sided inequality; matrix sparsification; complete solution; backtracking
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.
References:
[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. DOI 10.1142/S0218196711006674 | MR 2900854 | Zbl 1239.14054
[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. DOI 10.1016/j.jcta.2010.04.003 | MR 2737191 | Zbl 1246.14078
[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). MR 1204266 | Zbl 0824.93003
[4] Butkovič, P.: Max-Linear Systems: Theory and Algorithms. Springer Monographs in Mathematics. Springer, London (2010). DOI 10.1007/978-1-84996-299-5 | MR 2681232 | Zbl 1202.15032
[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. MR 0782401 | Zbl 0545.90101
[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. DOI 10.1016/j.dam.2005.09.008 | MR 2203194 | Zbl 1090.68119
[7] Carré, B. A.: An algebra for network routing problems. J. Inst. Math. Appl. 7 (1971), 273-294. DOI 10.1093/imamat/7.3.273 | MR 0292583 | Zbl 0219.90020
[8] Clifford, A. H., Preston, G. B.: The Algebraic Theory of Semigroups. Vol. 1. Mathematical Surveys and Monographs 7. American Mathematical Society, Providence (1961). DOI 10.1090/surv/007.1 | MR 0132791 | Zbl 0111.03403
[9] Cuninghame-Green, R. A.: Projections in minimax algebra. Math. Program. 10 (1976), 111-123. DOI 10.1007/BF01580656 | MR 0403664 | Zbl 0336.90062
[10] Cuninghame-Green, R. A.: Minimax Algebra. Lecture Notes in Economics and Mathematical Systems 166. Springer, Berlin (1979). DOI 10.1007/978-3-642-48708-8 | MR 0580321 | Zbl 0399.90052
[11] Cuninghame-Green, R. A.: Minimax algebra and applications. Advances in Imaging and Electron Physics. Volume 90 Academic Press, San Diego (1994), 1-121. DOI 10.1016/S1076-5670(08)70083-1 | MR 0580321
[12] Cuninghame-Green, R. A., Butkovič, P.: The equation ${A}\otimes x={B}\otimes y$ over (max,+). Theor. Comput. Sci. 293 (2003), 3-12. DOI 10.1016/S0304-3975(02)00228-1 | MR 1957609 | Zbl 1021.65022
[13] Cuninghame-Green, R. A., Butkovič, P.: Bases in max-algebra. Linear Algebra Appl. 389 (2004), 107-120. DOI 10.1016/j.laa.2004.03.022 | MR 2080398 | Zbl 1059.15001
[14] Elsner, L., Driessche, P. van den: Max-algebra and pairwise comparison matrices. II. Linear Algebra Appl. 432 (2010), 927-935. DOI 10.1016/j.laa.2009.10.005 | MR 2577637 | Zbl 1191.15019
[15] Gaubert, S., Katz, R. D.: The tropical analogue of polar cones. Linear Algebra Appl. 431 (2009), 608-625. DOI 10.1016/j.laa.2009.03.012 | MR 2535537 | Zbl 1172.52002
[16] Gaubert, S., Katz, R. D., Sergeev, S.: Tropical linear-fractional programming and parametric mean payoff games. J. Symb. Comput. 47 (2012), 1447-1478. DOI 10.1016/j.jsc.2011.12.049 | MR 2929038 | Zbl 1270.90081
[17] Golan, J. S.: Semirings and Affine Equations Over Them: Theory and Applications. Mathematics and Its Applications 556. Kluwer Academic, Dordrecht (2003). DOI 10.1007/978-94-017-0383-3 | MR 1997126 | Zbl 1042.16038
[18] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces Series 41. Springer, New York (2008). DOI 10.1007/978-0-387-75450-5 | MR 2389137 | Zbl 1201.16038
[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). DOI 10.1515/9781400865239 | MR 2188299 | Zbl 1130.93003
[20] Jones, D.: On two-sided max-linear equations. Discrete Appl. Math. 254 (2019), 146-160. DOI 10.1016/j.dam.2018.06.011 | MR 3913099 | Zbl 1407.15017
[21] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications. Mathematics and Its Applications 401. Kluwer Academic, Dordrecht (1997). DOI 10.1007/978-94-015-8901-7 | MR 1447629 | Zbl 0941.93001
[22] Krivulin, N. K.: Solution of generalized linear vector equations in idempotent algebra. Vestn. St. Petersbg. Univ., Math. 39 (2006), 16-26. MR 2302633
[23] Krivulin, N.: A multidimensional tropical optimization problem with a non-linear objective function and linear constraints. Optimization 64 (2015), 1107-1129. DOI 10.1080/02331934.2013.840624 | MR 3316792 | Zbl 1311.65086
[24] Krivulin, N.: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468 (2015), 211-232. DOI 10.1016/j.laa.2014.06.044 | MR 3293251 | Zbl 1307.65089
[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. DOI 10.1016/j.jlamp.2017.03.004 | MR 3634737 | Zbl 1386.90174
[26] Krivulin, N.: Complete algebraic solution of multidimensional optimization problems in tropical semifield. J. Log. Algebr. Methods Program. 99 (2018), 26-40. DOI 10.1016/j.jlamp.2018.05.002 | MR 3811166 | Zbl 1412.90143
[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. DOI 10.1016/j.laa.2011.02.014 | MR 2807241 | Zbl 1217.65076
[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. DOI 10.1090/conm/495 | MR 2581526 | Zbl 1179.15033
[29] Sergeev, S., Wagneur, E.: Basic solutions of systems with two max-linear inequalities. Linear Algebra Appl. 435 (2011), 1758-1768. DOI 10.1016/j.laa.2011.02.033 | MR 2810669 | Zbl 1227.15018
[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. DOI 10.1090/conm/495 | MR 2581528 | Zbl 1357.15017
[31] Yoeli, M.: A note on a generalization of Boolean matrix theory. Am. Math. Mon. 68 (1961), 552-557. DOI 10.2307/2311149 | MR 0126472 | Zbl 0115.02103
[32] Zimmermann, K.: A general separation theorem in extremal algebras. Ekon.-Mat. Obz. 13 (1977), 179-201. MR 0453607 | Zbl 0365.90127
Search
Partner of
