Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
max-plus algebra; max-plus linear systems; mixed integer programming
max-plus algebra; max-plus linear systems; mixed integer programming
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.
References:
[1] Allamigeon, X., Benchimol, P., Gaubert, S.: Tropicalizing the simplex algorithm. SIAM J Discrete Math. 29 (2015), 751-795. DOI 10.1137/130936464 | MR 3336300
[2] Aminu, A., Butkovič, P.: Non-linear programs with max-linear constraints: A heuristic approach. IMA J. Management Math. 23 (2012), 41-66. DOI 10.1093/imaman/dpq020 | MR 2874172
[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
[4] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010. DOI 10.1007/978-1-84996-299-5 | MR 2681232 | Zbl 1202.15032
[5] Butkovič, P., Aminu, A.: Introduction to max-linear programming. IMA J. Management Math. 20 (2009), 233-249. DOI 10.1093/imaman/dpn029 | MR 2511497
[6] Cechlárová, K.: A note on unsolvable systems of max-min (fuzzy) equations. Linear Algebra Appl. 310 (2000), 123-128. DOI 10.1016/s0024-3795(00)00060-4 | MR 1753171
[7] Cechlárová, K., Cuninghame-Green, R. A.: Soluble approximation of linear systems in max-plus algebra. Kybernetika 39 (2003), 137-141. MR 1996552
[8] Cechlárová, K., Diko, P.: Resolving infeasibility in extremal algebras. Linear Algebra Appl. 290 (1999), 267-273. DOI 10.1016/s0024-3795(98)10248-3 | MR 1672997
[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 10.1016/j.fss.2017.05.004 | MR 3787606
[10] Cuninghame-Green, R. A., Cechlárová, K.: Residuation in fuzzy algebra and some applications. Fuzzy Sets and Systems 71 (1995), 227-239. DOI 10.1016/0165-0114(94)00252-3 | MR 1329610
[11] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms. Springer, New York 2008. MR 2389137 | Zbl 1201.16038
[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 10.1515/9781400865239 | MR 2188299
[13] 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
[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
[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
[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.
Search
Partner of
