Tropical optimization problems

Research output: Contribution to conferenceAbstractpeer-review

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 finite-dimensional 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 Chebyshev-like approximation problems, problems with minimization and maximization of span seminorm, tropical “linear-fractional” 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 real-world problems in job scheduling, location analysis, decision making and other fields are also discussed.

Conference

ConferenceМеждународная научная конференция "Алгебра и математическая логика: теория и приложения" с сопутствующей молодежной летней школой
CountryRussian Federation
CityКазань
Period2/06/146/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.

Cite this