A multidimensional tropical optimization problem with a non-linear objective function and linear constraints. (English) Zbl 1311.65086
Summary: We examine a multidimensional optimization problem in the tropical mathematics setting. The problem involves the minimization of a non-linear function defined on a finite-dimensional semimodule over an idempotent semifield subject to linear inequality constraints. We start with an overview of known tropical optimization problems with linear and non-linear objective functions. A short introduction to tropical algebra is provided to offer a formal framework for solving the problem under study. As a preliminary result, a solution to a linear inequality with an arbitrary matrix is presented. We describe an example optimization problem drawn from project scheduling and then offer a general representation of the problem. To solve the problem, we introduce an additional variable and reduce the problem to the solving of a linear inequality, in which the variable plays the role of a parameter. A necessary and sufficient condition for the inequality to hold is used to evaluate the parameter, whereas the solution to the inequality is considered a solution to the problem. Based on this approach, a complete direct solution in a compact vector form is derived for the optimization problem under fairly general conditions. Numerical and graphical examples for two-dimensional problems are given to illustrate the obtained results.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 15A80 | Max-plus and related algebras |
| 90C48 | Programming in abstract spaces |
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
idempotent semifield; multidimensional optimization problem; nonlinear objective function; linear inequality constraints; project schedulingReferences:
| [1] | DOI: 10.1057/jors.1962.10 · doi:10.1057/jors.1962.10 |
| [2] | Pandit SNN, J. SIAM. 9 pp 632– (1961) |
| [3] | Romanovskiĭ IV, Soviet Math. Dokl. 5 pp 1684– (1964) |
| [4] | Vorob’ev NN, Soviet Math. Dokl. 4 pp 1220– (1963) |
| [5] | Baccelli FL, Synchronization and linearity: an algebra for discrete event systems. Wiley series in probability and statistics (1993) |
| [6] | DOI: 10.1007/978-1-84996-299-5 · Zbl 1202.15032 · doi:10.1007/978-1-84996-299-5 |
| [7] | Carré B, Graphs and networks. Oxford applied mathematics and computing science series (1979) |
| [8] | Cuninghame-Green R, Minimax algebra. Vol. 166, Lecture notes in economics and mathematical systems (1979) |
| [9] | DOI: 10.1007/978-94-017-0383-3 · doi:10.1007/978-94-017-0383-3 |
| [10] | Gondran M, Graphs, dioids and semirings: new models and algorithms. Vol. 41, Operations research/computer science interfaces (2008) · Zbl 1201.16038 |
| [11] | Heidergott B, Max-plus at work: modeling and analysis of synchronized systems. Princeton series in applied mathematics (2006) · Zbl 1130.93003 |
| [12] | DOI: 10.1007/978-94-015-8901-7 · doi:10.1007/978-94-015-8901-7 |
| [13] | Krivulin NK, Methods of idempotent algebra for problems in modeling and analysis of complex systems (2009) |
| [14] | Zimmermann U, Linear and combinatorial optimization in ordered algebraic structures. Vol. 10, Annals of discrete mathematics (1981) · Zbl 0466.90045 |
| [15] | DOI: 10.1007/BF01580656 · Zbl 0336.90062 · doi:10.1007/BF01580656 |
| [16] | DOI: 10.1002/nav.3800100131 · Zbl 0122.15301 · doi:10.1002/nav.3800100131 |
| [17] | Superville L, Various aspects of max-algebra [Ph.D. thesis] (1978) |
| [18] | DOI: 10.1016/S0304-0208(08)72952-9 · doi:10.1016/S0304-0208(08)72952-9 |
| [19] | DOI: 10.1007/BFb0121020 · Zbl 0558.90102 · doi:10.1007/BFb0121020 |
| [20] | Krivulin N, Advances in computer science: proc. 6th WSEAS European Computing Conf. (ECC ’12) pp 216– (2012) |
| [21] | Krivulin N, WSEAS Trans. Math. 10 pp 191– (2011) |
| [22] | Krivulin NK, Vestnik St. Petersburg Univ. Math. 38 pp 42– (2005) |
| [23] | Krivulin NK, Vestnik St. Petersburg Univ. Math. 39 pp 72– (2006) |
| [24] | DOI: 10.3103/S1063454111040078 · Zbl 1272.15007 · doi:10.3103/S1063454111040078 |
| [25] | Krivulin NK, Vestnik St. Petersburg Univ. Math. 39 pp 16– (2006) |
| [26] | DOI: 10.1093/imaman/dpq020 · Zbl 1248.90075 · doi:10.1093/imaman/dpq020 |
| [27] | DOI: 10.1093/imaman/dpn029 · Zbl 1169.90396 · doi:10.1093/imaman/dpn029 |
| [28] | DOI: 10.1090/conm/495/09694 · doi:10.1090/conm/495/09694 |
| [29] | DOI: 10.1007/0-387-32698-7_6 · doi:10.1007/0-387-32698-7_6 |
| [30] | DOI: 10.1016/0165-0114(91)90130-I · Zbl 0739.90073 · doi:10.1016/0165-0114(91)90130-I |
| [31] | Krivulin N, WSEAS Trans. Math. 11 pp 605– (2012) |
| [32] | DOI: 10.1016/S0024-3795(03)00476-2 · Zbl 1056.15009 · doi:10.1016/S0024-3795(03)00476-2 |
| [33] | DOI: 10.1007/s10100-011-0203-x · Zbl 1339.90265 · doi:10.1007/s10100-011-0203-x |
| [34] | DOI: 10.1016/S0304-0208(08)72967-0 · doi:10.1016/S0304-0208(08)72967-0 |
| [35] | DOI: 10.1080/02331939208843777 · Zbl 0814.65064 · doi:10.1080/02331939208843777 |
| [36] | DOI: 10.1016/S0304-3975(02)00231-1 · Zbl 1031.90046 · doi:10.1016/S0304-3975(02)00231-1 |
| [37] | DOI: 10.1016/S0304-3975(02)00228-1 · Zbl 1021.65022 · doi:10.1016/S0304-3975(02)00228-1 |
| [38] | DOI: 10.1142/S0218196711006674 · Zbl 1239.14054 · doi:10.1142/S0218196711006674 |
| [39] | DOI: 10.1016/j.jsc.2011.12.049 · Zbl 1270.90081 · doi:10.1016/j.jsc.2011.12.049 |
| [40] | Krivulin N, Advances in computer science: proc. 6th WSEAS European Computing Conf. (ECC’12) pp 146– (2012) |
| [41] | DOI: 10.1016/S1076-5670(08)70083-1 · doi:10.1016/S1076-5670(08)70083-1 |
| [42] | DOI: 10.1007/s10958-007-0450-5 · doi:10.1007/s10958-007-0450-5 |
| [43] | Vorob’ev NN, Elektron. Informationsverarbeit. Kybernetik. 3 pp 39– (1967) |
| [44] | DOI: 10.1093/imamat/7.3.273 · Zbl 0219.90020 · doi:10.1093/imamat/7.3.273 |
| [45] | DOI: 10.1016/S0304-0208(08)72960-8 · doi:10.1016/S0304-0208(08)72960-8 |
| [46] | DOI: 10.1016/S0304-0208(08)72965-7 · doi:10.1016/S0304-0208(08)72965-7 |
| [47] | DOI: 10.1007/978-3-540-24800-2 · doi:10.1007/978-3-540-24800-2 |
| [48] | Project Management Institute, A guide to the project management body of knowledge (PMBOKGuide) (2010) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
