Activities per year
Abstract
We consider optimization problems that are formulated and solved in the tropical (idempotent) algebra setting. The problems are to minimize or maximize functions defined on vectors of a finitedimensional semimodule over an idempotent semifield, and may involve constraints in the form of linear vector equations and inequalities. The objective function can be either a linear function or a nonlinear function calculated by means of multiplicative conjugate vector transposition.
We give an overview of known tropical optimization problems and solution methods. The overview starts with problems with linear objective functions, which present idempotent analogues of the usual linear programming problems. Then, we consider problems with nonlinear objective functions, including Chebyshev and Chebyshevlike approximation problems, problems with minimization and maximization of span seminorm, tropical “linearfractional” programming problems, and problems with the evaluation of spectral radius. Some of these problems can be completely solved, and the solution is found in an explicit vector form. The existing solutions given for other problems are obtained in the form of iterative algorithms that produce a particular solution if any or indicate that there is no solution.
Furthermore, we present recent results on the solution of new optimization problems that extend known problems by introducing more general objective functions and taking into account additional linear constraints. To solve the problems, several approaches are proposed that offer direct explicit solutions in a compact vector form suitable for further analysis and applications. For many problems, the results obtained are complete solutions.
The solution of the some problems without constraints involves the evaluation of sharp lower or upper bounds for the objective function and the solution of an equation to find all vectors that yield the bound. To find solutions to the problems with linear equation and inequality constraints, we first obtain a general solution to the equation or inequality, and then substitute it into the objective function to get an unconstrained problem with known solution.
To solve other problems, we introduce an auxiliary variable, which indicates the minimum value of the objective function. The problem is then reduced to the solving of a linear inequality with a parameterized matrix, where the above variable plays the role of parameter. We exploit the existence condition for solutions of the inequality to evaluate the parameter, and then take the general solution of the inequality as the solution to the initial optimization problem.
Applications of the results to solve realworld problems in job scheduling, location analysis, decision making and other fields are also discussed.
We give an overview of known tropical optimization problems and solution methods. The overview starts with problems with linear objective functions, which present idempotent analogues of the usual linear programming problems. Then, we consider problems with nonlinear objective functions, including Chebyshev and Chebyshevlike approximation problems, problems with minimization and maximization of span seminorm, tropical “linearfractional” programming problems, and problems with the evaluation of spectral radius. Some of these problems can be completely solved, and the solution is found in an explicit vector form. The existing solutions given for other problems are obtained in the form of iterative algorithms that produce a particular solution if any or indicate that there is no solution.
Furthermore, we present recent results on the solution of new optimization problems that extend known problems by introducing more general objective functions and taking into account additional linear constraints. To solve the problems, several approaches are proposed that offer direct explicit solutions in a compact vector form suitable for further analysis and applications. For many problems, the results obtained are complete solutions.
The solution of the some problems without constraints involves the evaluation of sharp lower or upper bounds for the objective function and the solution of an equation to find all vectors that yield the bound. To find solutions to the problems with linear equation and inequality constraints, we first obtain a general solution to the equation or inequality, and then substitute it into the objective function to get an unconstrained problem with known solution.
To solve other problems, we introduce an auxiliary variable, which indicates the minimum value of the objective function. The problem is then reduced to the solving of a linear inequality with a parameterized matrix, where the above variable plays the role of parameter. We exploit the existence condition for solutions of the inequality to evaluate the parameter, and then take the general solution of the inequality as the solution to the initial optimization problem.
Applications of the results to solve realworld problems in job scheduling, location analysis, decision making and other fields are also discussed.
Original language  English 

Pages  90 
State  Published  2014 
Event  Международная научная конференция "Алгебра и математическая логика: теория и приложения" с сопутствующей молодежной летней школой  Казань, Russian Federation Duration: 2 Jun 2014 → 6 Jun 2014 http://kpfu.ru/math/conference/mezhdunarodnayanauchnayakonferenciya39algebra 
Conference
Conference  Международная научная конференция "Алгебра и математическая логика: теория и приложения" с сопутствующей молодежной летней школой 

Country  Russian Federation 
City  Казань 
Period  2/06/14 → 6/06/14 
Internet address 
Scopus subject areas
 Control and Optimization
 Algebra and Number Theory
Fingerprint Dive into the research topics of 'Tropical optimization problems'. Together they form a unique fingerprint.
Activities

Tropical optimization problems
Николай Кимович Кривулин (Speaker)
3 Jun 2014Activity: Talk types › Oral presentation

Международная научная конференция "Алгебра и математическая логика: теория и приложения" с сопутствующей молодежной летней школой
Николай Кимович Кривулин (Participant)
2 Jun 2014 → 6 Jun 2014Activity: Attendance types › Participating in a conference, workshop, ...