Kybernetika 55 no. 3, 531-539, 2019

A note on resolving the inconsistency of one-sided max-plus linear equations

Pingke LiDOI: 10.14736/kyb-2019-3-0531

Abstract:

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.

Keywords:

max-plus algebra, max-plus linear systems, mixed integer programming

Classification:

15A80, 90C11

paper.pdf

References:

  1. X. Allamigeon, P. Benchimol and S. Gaubert: Tropicalizing the simplex algorithm. SIAM J Discrete Math. 29 (2015), 751-795.   CrossRef
  2. A. Aminu and P. Butkovič: Non-linear programs with max-linear constraints: A heuristic approach. IMA J. Management Math. 23 (2012), 41-66.   DOI:10.1093/imaman/dpq020
  3. F. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley, Chichester 1992.   CrossRef
  4. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer, Berlin 2010.   DOI:10.1007/978-1-84996-299-5
  5. P. Butkovič and A. Aminu: Introduction to max-linear programming. IMA J. Management Math. 20 (2009), 233-249.   DOI:10.1093/imaman/dpn029
  6. K. Cechlárová: 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
  7. K. Cechlárová and R. A. Cuninghame-Green: Soluble approximation of linear systems in max-plus algebra. Kybernetika 39 (2003), 137-141.   CrossRef
  8. K. Cechlárová and P. Diko: Resolving infeasibility in extremal algebras. Linear Algebra Appl. 290 (1999), 267-273.   DOI:10.1016/s0024-3795(98)10248-3
  9. R. Cimler, M. Gavalec and K. Zimmermann: 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
  10. R. A. Cuninghame-Green and K. Cechlárová: Residuation in fuzzy algebra and some applications. Fuzzy Sets and Systems 71 (1995), 227-239.   DOI:10.1016/0165-0114(94)00252-3
  11. M. Gondran and M. Minoux: Graphs, Dioids and Semirings: New Models and Algorithms. Springer, New York 2008.   CrossRef
  12. B. Heidergott, G. J. Olsder and J. van der Woude: Max Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton University Press, Princeton 2005.   DOI:10.1515/9781400865239
  13. N. Krivulin: 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
  14. P. Li and S.-C. Fang: 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.   CrossRef
  15. A. Tharwat and K. Zimmermann: Some optimization problems on solubility sets of separable Max-Min equations and inequalities. Acta Univ. Carolinae. Math. Phys. 38 (1997), 45-57.   CrossRef
  16. K. Zimmermann: 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.   CrossRef