| Title:
|
A note on resolving the inconsistency of one-sided max-plus linear equations (English) |
| Author:
|
Li, Pingke |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
55 |
| Issue:
|
3 |
| Year:
|
2019 |
| Pages:
|
531-539 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
When a system of one-sided max-plus linear equations is inconsistent, its right-hand side vector may be slightly modified to reach a consistent one. It is handled in this note by minimizing the sum of absolute deviations in the right-hand side vector. It turns out that this problem may be reformulated as a mixed integer linear programming problem. Although solving such a problem requires much computational effort, it may propose a solution that just modifies few elements of the right-hand side vector, which is a desired property in some practical situations. (English) |
| Keyword:
|
max-plus algebra |
| Keyword:
|
max-plus linear systems |
| Keyword:
|
mixed integer programming |
| MSC:
|
15A80 |
| MSC:
|
90C11 |
| idZBL:
|
Zbl 07144952 |
| idMR:
|
MR4015997 |
| DOI:
|
10.14736/kyb-2019-3-0531 |
| . |
| Date available:
|
2019-11-14T08:39:14Z |
| Last updated:
|
2020-04-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147866 |
| . |
| Reference:
|
[1] Allamigeon, X., Benchimol, P., Gaubert, S.: Tropicalizing the simplex algorithm..SIAM J Discrete Math. 29 (2015), 751-795. MR 3336300, 10.1137/130936464 |
| Reference:
|
[2] Aminu, A., Butkovič, P.: Non-linear programs with max-linear constraints: A heuristic approach..IMA J. Management Math. 23 (2012), 41-66. MR 2874172, 10.1093/imaman/dpq020 |
| Reference:
|
[3] Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems..Wiley, Chichester 1992. MR 1204266 |
| Reference:
|
[4] Butkovič, P.: Max-linear Systems: Theory and Algorithms..Springer, Berlin 2010. Zbl 1202.15032, MR 2681232, 10.1007/978-1-84996-299-5 |
| Reference:
|
[5] Butkovič, P., Aminu, A.: Introduction to max-linear programming..IMA J. Management Math. 20 (2009), 233-249. MR 2511497, 10.1093/imaman/dpn029 |
| Reference:
|
[6] Cechlárová, K.: A note on unsolvable systems of max-min (fuzzy) equations..Linear Algebra Appl. 310 (2000), 123-128. MR 1753171, 10.1016/s0024-3795(00)00060-4 |
| Reference:
|
[7] Cechlárová, K., Cuninghame-Green, R. A.: Soluble approximation of linear systems in max-plus algebra..Kybernetika 39 (2003), 137-141. MR 1996552 |
| Reference:
|
[8] Cechlárová, K., Diko, P.: Resolving infeasibility in extremal algebras..Linear Algebra Appl. 290 (1999), 267-273. MR 1672997, 10.1016/s0024-3795(98)10248-3 |
| Reference:
|
[9] Cimler, R., Gavalec, M., Zimmermann, K.: An optimization problem on the image set of a (max, min) fuzzy operator..Fuzzy Sets and Systems 341 (2018), 113-122. MR 3787606, 10.1016/j.fss.2017.05.004 |
| Reference:
|
[10] Cuninghame-Green, R. A., Cechlárová, K.: Residuation in fuzzy algebra and some applications..Fuzzy Sets and Systems 71 (1995), 227-239. MR 1329610, 10.1016/0165-0114(94)00252-3 |
| Reference:
|
[11] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms..Springer, New York 2008. Zbl 1201.16038, MR 2389137 |
| Reference:
|
[12] Heidergott, B., Olsder, G. J., Woude, J. van der: Max Plus at Work: Modeling and Analysis of Synchronized Systems..Princeton University Press, Princeton 2005. MR 2188299, 10.1515/9781400865239 |
| Reference:
|
[13] Krivulin, N.: A multidimensional tropical optimization problem with a non-linear objective function and linear constraints..Optimization 64 (2015), 1107-1129. MR 3316792, 10.1080/02331934.2013.840624 |
| Reference:
|
[14] Li, P., Fang, S.-C.: Chebyshev approximation of inconsistent fuzzy relational equations with Max-$T$ composition..In: Fuzzy Optimization (W. A. Lodwick and J. Kacprzyk, eds.), Springer, Berlin 2010, pp. 109-124. MR 2722985 |
| Reference:
|
[15] Tharwat, A., Zimmermann, K.: Some optimization problems on solubility sets of separable Max-Min equations and inequalities..Acta Univ. Carolinae. Math. Phys. 38 (1997), 45-57. MR 1614039 |
| Reference:
|
[16] Zimmermann, K.: Optimization problems under max-min separable equation and inequality constraints..In: Decision Making and Optimization: Special Matrices and Their Applications in Economics and Management (M. Gavalec, J. Ramík, and K. Zimmermann, eds.), Springer, Cham 2015, pp. 119-161. |
| . |
