Geodesic
A note on resolving the inconsistency of one-sided max-plus linear equations
Kybernetika, Tome 55 (2019) no. 3, pp. 531-539
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2019-3-0531
Classification : 15A80, 90C11
Keywords: max-plus algebra; max-plus linear systems; mixed integer programming 
@article{10_14736_kyb_2019_3_0531,
     author = {Li, Pingke},
     title = {A note on resolving the inconsistency of one-sided max-plus linear equations},
     journal = {Kybernetika},
     pages = {531--539},
     year = {2019},
     volume = {55},
     number = {3},
     doi = {10.14736/kyb-2019-3-0531},
     mrnumber = {4015997},
     zbl = {07144952},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2019-3-0531/}
}
TY  - JOUR
AU  - Li, Pingke
TI  - A note on resolving the inconsistency of one-sided max-plus linear equations
JO  - Kybernetika
PY  - 2019
SP  - 531
EP  - 539
VL  - 55
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2019-3-0531/
DO  - 10.14736/kyb-2019-3-0531
LA  - en
ID  - 10_14736_kyb_2019_3_0531
ER  - 
%0 Journal Article
%A Li, Pingke
%T A note on resolving the inconsistency of one-sided max-plus linear equations
%J Kybernetika
%D 2019
%P 531-539
%V 55
%N 3
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2019-3-0531/
%R 10.14736/kyb-2019-3-0531
%G en
%F 10_14736_kyb_2019_3_0531
Li, Pingke. A note on resolving the inconsistency of one-sided max-plus linear equations. Kybernetika, Tome 55 (2019) no. 3, pp. 531-539. doi: 10.14736/kyb-2019-3-0531

[1] Allamigeon, X., Benchimol, P., Gaubert, S.: Tropicalizing the simplex algorithm. SIAM J Discrete Math. 29 (2015), 751-795. | DOI | MR

[2] Aminu, A., Butkovič, P.: Non-linear programs with max-linear constraints: A heuristic approach. IMA J. Management Math. 23 (2012), 41-66. | DOI | MR

[3] Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, Chichester 1992. | MR

[4] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010. | DOI | MR | Zbl

[5] Butkovič, P., Aminu, A.: Introduction to max-linear programming. IMA J. Management Math. 20 (2009), 233-249. | DOI | MR

[6] Cechlárová, K.: A note on unsolvable systems of max-min (fuzzy) equations. Linear Algebra Appl. 310 (2000), 123-128. | DOI | MR

[7] Cechlárová, K., Cuninghame-Green, R. A.: Soluble approximation of linear systems in max-plus algebra. Kybernetika 39 (2003), 137-141. | MR

[8] Cechlárová, K., Diko, P.: Resolving infeasibility in extremal algebras. Linear Algebra Appl. 290 (1999), 267-273. | DOI | MR

[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. | DOI | MR

[10] Cuninghame-Green, R. A., Cechlárová, K.: Residuation in fuzzy algebra and some applications. Fuzzy Sets and Systems 71 (1995), 227-239. | DOI | MR

[11] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms. Springer, New York 2008. | MR | Zbl

[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. | DOI | MR

[13] Krivulin, N.: A multidimensional tropical optimization problem with a non-linear objective function and linear constraints. Optimization 64 (2015), 1107-1129. | DOI | MR

[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

[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

[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.

Cité par Sources :