Research output: Contribution to journal › Article › peer-review
Solution of a multidimensional tropical optimization problem using matrix sparsification. / Krivulin, N. K. ; Sorokin, V. N.
In: Vestnik St. Petersburg University: Mathematics, Vol. 51, No. 1, 2018, p. 66-76.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Solution of a multidimensional tropical optimization problem using matrix sparsification
AU - Krivulin, N. K.
AU - Sorokin, V. N.
N1 - Krivulin, N.K., Sorokin, V.N. Solution of a Multidimensional Tropical Optimization Problem Using Matrix Sparsification. Vestnik St.Petersb. Univ.Math. 51, 66–76 (2018). https://doi.org/10.3103/S1063454118010065
PY - 2018
Y1 - 2018
N2 - A complete solution is proposed for the problem of minimizing a function defined on vectors with elements in a tropical (idempotent) semifield. The tropical optimization problem under consideration arises, for example, when we need to find the best (in the sense of the Chebyshev metric) approximate solution to tropical vector equations and occurs in various applications, including scheduling, location, and decision-making problems. To solve the problem, the minimum value of the objective function is determined, the set of solutions is described by a system of inequalities, and one of the solutions is obtained. Thereafter, an extended set of solutions is constructed using the sparsification of the matrix of the problem, and then a complete solution in the form of a family of subsets is derived. Procedures that make it possible to reduce the number of subsets to be examined when constructing the complete solution are described. It is shown how the complete solution can be represented parametrically in a compact vector form. The solution obtained in this study generalizes known results, which are commonly reduced to deriving one solution and do not allow us to find the entire solution set. To illustrate the main results of the work, an example of numerically solving the problem in the set of three-dimensional vectors is given.
AB - A complete solution is proposed for the problem of minimizing a function defined on vectors with elements in a tropical (idempotent) semifield. The tropical optimization problem under consideration arises, for example, when we need to find the best (in the sense of the Chebyshev metric) approximate solution to tropical vector equations and occurs in various applications, including scheduling, location, and decision-making problems. To solve the problem, the minimum value of the objective function is determined, the set of solutions is described by a system of inequalities, and one of the solutions is obtained. Thereafter, an extended set of solutions is constructed using the sparsification of the matrix of the problem, and then a complete solution in the form of a family of subsets is derived. Procedures that make it possible to reduce the number of subsets to be examined when constructing the complete solution are described. It is shown how the complete solution can be represented parametrically in a compact vector form. The solution obtained in this study generalizes known results, which are commonly reduced to deriving one solution and do not allow us to find the entire solution set. To illustrate the main results of the work, an example of numerically solving the problem in the set of three-dimensional vectors is given.
KW - idempotent semifield
KW - tropical optimization
KW - Chebyshev approximation
KW - complete solution
KW - matrix sparsification
KW - ALGEBRA
UR - http://www.scopus.com/inward/record.url?scp=85045076747&partnerID=8YFLogxK
U2 - 10.3103/S1063454118010065
DO - 10.3103/S1063454118010065
M3 - Article
VL - 51
SP - 66
EP - 76
JO - Vestnik St. Petersburg University: Mathematics
JF - Vestnik St. Petersburg University: Mathematics
SN - 1063-4541
IS - 1
ER -
ID: 32599857