Previous |  Up |  Next


Title: Optimization problem under two-sided (max, +)/(min, +) inequality constraints (English)
Author: Zimmermann, Karel
Language: English
Journal: Applications of Mathematics
ISSN: 0862-7940 (print)
ISSN: 1572-9109 (online)
Volume: 65
Issue: 6
Year: 2020
Pages: 777-783
Summary lang: English
Category: math
Summary: $(\max ,+)$-linear functions are functions which can be expressed as the maximum of a finite number of linear functions of one variable having the form $f(x_1, \dots , x_h) = \max _j(a_j+ x_j)$, where $a_j$, $j = 1, \dots , h$, are real numbers. Similarly $(\min ,+)$-linear functions are defined. We will consider optimization problems in which the set of feasible solutions is the solution set of a finite inequality system, where the inequalities have $(\max ,+)$-linear functions of variables $x$ on one side and $(\min ,+)$-linear functions of variables $y$ on the other side. Such systems can be applied e.g. to operations research problems in which we need to coordinate or synchronize release and completion times of operations or departure and arrival times of passengers. A motivation example is presented and the proposed solution method is demonstrated on a small numerical example. (English)
Keyword: nonconvex optimization
Keyword: $(\max ,+)/(\min ,+)$-linear functions
Keyword: OR - arrival-departure coordination
MSC: 90C26
MSC: 90C30
idZBL: Zbl 07285956
idMR: MR4191368
DOI: 10.21136/AM.2020.0001-20
Date available: 2020-11-18T09:38:25Z
Last updated: 2021-04-08
Stable URL:
Reference: [1] Butkovič, P.: Max-Linear Systems: Theory and Algorithms.Springer Monographs in Mathematics. Springer, London (2010). Zbl 1202.15032, MR 2681232, 10.1007/978-1-84996-299-5
Reference: [2] Cuninghame-Green, R.: Minimax Algebra.Lecture Notes in Economics and Mathematical Systems 166. Springer, Berlin (1979). Zbl 0399.90052, MR 0580321, 10.1007/978-3-642-48708-8
Reference: [3] Krivulin, N. K.: Methods of Idempotent Algebra in Modelling and Analysis of Complex Systems.Saint Peterburg University Press, St. Petersburg (2009), Russian.
Reference: [4] Vorobjov, N. N.: Extremal algebra of positive matrices.Elektron. Inform.-verarb. Kybernetik 3 (1967), 39-70 Russian. Zbl 0168.02603, MR 0216854

Fulltext not available (moving wall 24 months)

Partner of
EuDML logo