zbMATH — the first resource for mathematics

Optimization problem under two-sided \((\max,+)/(\min,+)\) inequality constraints. (English) Zbl 07285956
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.
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
[1] Butkovič, P., Max-Linear Systems: Theory and Algorithms, Springer Monographs in Mathematics. Springer, London (2010)
[2] Cuninghame-Green, R., Minimax Algebra, Lecture Notes in Economics and Mathematical Systems 166. Springer, Berlin (1979)
[3] Krivulin, N. K., Methods of Idempotent Algebra in Modelling and Analysis of Complex Systems, Saint Peterburg University Press, St. Petersburg (2009), Russian
[4] Vorobjov, N. N., Extremal algebra of positive matrices, Elektron. Inform.-verarb. Kybernetik 3 (1967), 39-70 Russian
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.