Tropical optimization problems

Research output

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

Fingerprint

Optimization Problem
Objective function
Idempotent
Chebyshev
Nonlinear Function
General Solution
Linear Function
Linear Inequalities
Semimodule
Semifield
Fractional Programming
Seminorm
Job Scheduling
Auxiliary Variables
Transposition
Particular Solution
Approximation Problem
Evaluation
Spectral Radius
Linear Constraints

Scopus subject areas

  • Mathematics(all)

Cite this

Krivulin, N. (2014). Tropical optimization problems. 90. Abstract from Алгебра и математическая логика: теория и приложения. Международная научная конференция с сопутствующей молодежной летней школой, Казань, .
Krivulin, N. / Tropical optimization problems. Abstract from Алгебра и математическая логика: теория и приложения. Международная научная конференция с сопутствующей молодежной летней школой, Казань, .
@conference{d5ca39839e3f4cbea6dd4ad18a4990ff,
title = "Tropical optimization problems",
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.",
author = "N. Krivulin",
note = "Материалы конференции {"}Алгебра и математическая логика: теория и приложения{"} (г. Казань, 2-6 июня 2014 г.) и сопутствующей молодежной летней школы {"}Вычислимость и вычислимые структуры{"}. Казань: КФУ, 2014. 176 с.; Международная научная конференция {"}Алгебра и математическая логика: теория и приложения{"} с сопутствующей молодежной летней школой ; Conference date: 02-06-2014 Through 06-06-2014",
year = "2014",
language = "English",
pages = "90",
url = "http://kpfu.ru/math/conference/mezhdunarodnaya-nauchnaya-konferenciya-39algebra",

}

Krivulin, N 2014, 'Tropical optimization problems', Казань, 2/06/14 - 6/06/14, pp. 90.

Tropical optimization problems. / Krivulin, N.

2014. 90 Abstract from Алгебра и математическая логика: теория и приложения. Международная научная конференция с сопутствующей молодежной летней школой, Казань, .

Research output

TY - CONF

T1 - Tropical optimization problems

AU - Krivulin, N.

N1 - Материалы конференции "Алгебра и математическая логика: теория и приложения" (г. Казань, 2-6 июня 2014 г.) и сопутствующей молодежной летней школы "Вычислимость и вычислимые структуры". Казань: КФУ, 2014. 176 с.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

M3 - Abstract

SP - 90

ER -

Krivulin N. Tropical optimization problems. 2014. Abstract from Алгебра и математическая логика: теория и приложения. Международная научная конференция с сопутствующей молодежной летней школой, Казань, .