| 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:
|
2023-01-02 |
| 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 |
| . |
