Kybernetika 54 no. 2, 400-412, 2018

Adaptive thresholding technique for solving optimization problems on attainable sets of (max, min)-linear systems

Mahmoud GadDOI: 10.14736/kyb-2018-2-0400

Abstract:

This article develops a parametric method depend on threshold technique for solving some optimization problems on attainable sets of so called (max, min)-separable linear systems. The concept of attainable set for (max, min)-separable linear equation systems will be introduced. Properties of the attainable sets will be studied in detail. The (max, min) - separable linear equation systems, in which the function of unknown variable occur only on one side, will be consider. The main idea of the proposed algorithm is that we will begin the calculations with the maximum element and we will try to decrease the value of the objective function of our problem, by decreasing its components in such a way that they stay within attainable set. Optimization problem consisting in finding the nearest point of an attainable set to a given fixed point will be considered. An algorithm for solving the optimization problem will be proposed. Motivational example from the area of operations research, which shows possible applications of the optimization problem solved in this paper, will be given. Numerical example illustrating the proposed algorithm is included.

Keywords:

attainable sets, adaptive thresholding technique, (max;min)-separable equations

Classification:

90C47, 90C31

paper.pdf

References:

  1. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics and Springer-Verlag, London - Dodrecht - Heudelberg - New York 2010.   DOI:10.1007/978-1-84996-299-5
  2. R. A. Cuninghame-Green: Minimax Algebra, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag 166, Berlin 1979.   DOI:10.1007/978-3-642-48708-8
  3. I. I. Eremin, V. D. Mazurov and N. N. Asta\'fev: Linear Inequalities in mathematical programming and pattern recognition. Ukr. Math. J. 40 (1988), 3, 243-251. Translated from Ukr. Mat. Zh. 40 (1988), 3, 288-297.   DOI:10.1007/bf01061299
  4. M. Gad: Optimization problems under one-sided $(\max, \min)$-linear equality constraints. In: WDS'12 Proc. Contributed Papers Part I, 2012, pp. 13-19. 21st Annual Student Conference, Week of Doctoral Students Charles University, Prague 2012.   CrossRef
  5. M. Gad: Optimization problems under two-sided $(\max, \min)$-linear inequalities constraints. Academic Coordination Centre J. 18 (2012), 4, 84-92. In: International Conference Presentation of Mathematics Conference ICPM'12, Liberec 2012.   CrossRef
  6. M. Gad, J. Jablonský and K. Zimmermann: Incorrectly posed optimization problems under extremally linear equation constraints. In: Proc. 34th International Conference of Mathematical Methods in Economics MME 2016, Liberec 2016, pp. 231-236.   CrossRef
  7. M. Gavalec, M. Gad and K. Zimmermann: Optimization problems under $(\max, \min)$-linear equations and / or inequality constraints. J. Math. Sci. 193 (2013), 5, 645-658. Translated from Russian Journal Fundamentalnaya i Prikladnaya Matematika(Fundamental and Applied Mathematics) 17 (2012), 6, 3-21.   CrossRef
  8. K. Zimmernann: Extremální algebra (in Czech). Ekon. ústav ČSAV, Praha 1976.   CrossRef
  9. K. Zimmermann and M. Gad: Optimization problems under one-sided $(\max, +)$-linear constraints. In: Conference Presentation of Mathematics ICPM'11, Liberec 2011, pp. 159-165.   CrossRef