Activities per year
Abstract
We consider multidimensional optimization problems that are formulated in the framework of tropical mathematics to minimize functions defined on vectors over a tropical semifield (a semiring with idempotent addition and invertible multiplication). The functions, given by a matrix and calculated through multiplicative conjugate transposition, are nonlinear in the tropical mathematics sense. We start with known results on the solution of the problems with irreducible matrices. To solve the problems in the case of arbitrary (reducible) matrices, we first derive the minimum value of the objective function, and find a set of solutions. We show that all solutions of the problem satisfy a system of vector inequalities, and then use these inequalities to establish characteristic properties of the solution set. Furthermore, all solutions of the problem are represented as a family of subsets, each defined by a matrix that is obtained by using a matrix sparsification technique. We describe a backtracking procedure that allows one to reduce the bruteforce generation of sparsified matrices by skipping those, which cannot provide solutions, and thus offers an economical way to obtain all subsets in the family. Finally, the characteristic properties of the solution set are used to provide complete solutions in a closed form. We illustrate the results obtained with simple numerical examples.
Original language  English 

Pages (fromto)  2640 
Number of pages  15 
Journal  Journal of Logical and Algebraic Methods in Programming 
Volume  99 
Early online date  18 May 2018 
DOIs  
State  Published  Oct 2018 
Event  The 16th International Conference on Relational and Algebraic Methods in Computer Science  Université de Lyon, Lyon, France Duration: 15 May 2017 → 18 May 2017 Conference number: 16 http://www.enslyon.fr/LIP/PLUME/RAMiCS17/ 
Scopus subject areas
 Control and Optimization
 Algebra and Number Theory
 Management Science and Operations Research
Keywords
 tropical semifield
 tropical optimization
 matrix sparsification
 complete solution
 backtracking
 Backtracking
 Tropical semifield
 Complete solution
 LINEAR CONSTRAINTS
 Tropical optimization
 Matrix sparsification
Fingerprint Dive into the research topics of 'Complete algebraic solution of multidimensional optimization problems in tropical semifield'. Together they form a unique fingerprint.
Activities

The 16th International Conference on Relational and Algebraic Methods in Computer Science
Николай Кимович Кривулин (Participant)
15 May 2017 → 18 May 2017Activity: Attendance types › Participating in a conference, workshop, ...

Complete solution of an optimization problem in tropical semifield
Николай Кимович Кривулин (Speaker)
18 May 2017Activity: Talk types › Oral presentation