Algebraic solutions of tropical optimization problems

DOI10.1134/S199508021504006XzbMATH Open1336.65107arXiv1406.1777OpenAlexW1612769635MaRDI QIDQ266221FDOQ266221

Authors: Nikolai Krivulin 

Publication date: 13 April 2016

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Abstract: We consider multidimensional optimization problems, which are formulated and solved in terms of tropical mathematics. The problems are to minimize (maximize) a linear or nonlinear function defined on vectors of a finite-dimensional semimodule over an idempotent semifield, and may have constraints in the form of linear equations and inequalities. The aim of the paper is twofold: first to give a broad overview of known tropical optimization problems and solution methods, including recent results; and second, to derive a direct, complete solution to a new constrained optimization problem as an illustration of the algebraic approach recently proposed to solve tropical optimization problems with nonlinear objective function.

Full work available at URL: https://arxiv.org/abs/1406.1777

Recommendations

• Solution of a tropical optimization problem with linear constraints
• Complete solution of a constrained tropical optimization problem with application to location analysis
• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems

zbMATH Keywords

tropical mathematicsdirect solutionidempotent semifieldlinear inequality constraintmultidimensional optimizationnonlinear objective functiontropical optimization problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Nonlinear programming (90C30) Max-plus and related algebras (15A80)

Cites Work

• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• Linear and combinatorial optimization in ordered algebraic structures
• Minimax algebra and applications
• Minimax algebra
• Max-algebra and pairwise comparison matrices
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• Disjunctive optimization, \(\max\)-separable problems and extremal algebras
• The analytic hierarchy process, max algebra and multi-objective optimisation
• Dioïds and semirings: Links to fuzzy sets and other applications
• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems
• Tropical polyhedra are equivalent to mean payoff games
• A constrained tropical optimization problem: Complete solution and application example
• Duality for max-separable problems
• Non-linear programs with max-linear constraints: a heuristic approach
• Tropical and Idempotent Mathematics
• Title not available (Why is that?)
• Introduction to max-linear programming
• An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem
• A New Matrix Calculus
• Title not available (Why is that?)
• Projections in minimax algebra
• Optimization problems with unimodal functions in max-separabal constraints
• Title not available (Why is that?)
• Tropical linear-fractional programming and parametric mean payoff games
• Title not available (Why is that?)
• Resource optimization and (min,+) spectral theory
• Title not available (Why is that?)
• A multidimensional tropical optimization problem with a non-linear objective function and linear constraints
• Linear Optimization Problems with Inexact Data
• Title not available (Why is that?)
• Title not available (Why is that?)
• On abstract dual linear programs
• Relational and algebraic methods in computer science
• Model predictive control for max-plus-linear discrete event systems
• Algebraic and combinatorial methods in operations research. Proceedings of the Workshop on Algebraic Structures in Operations Research
• Max-algebra and pairwise comparison matrices. II.
• Evaluation of bounds on the mean rate of growth of the state vector of a linear dynamical stochastic system in idempotent algebra

Cited In (15)

• On a tropical dual Nullstellensatz
• A multidimensional tropical optimization problem with a non-linear objective function and linear constraints
• The 2-domination number of cylindrical graphs
• A note on tropical linear and integer programs
• Dynamic resource location with tropical algebra
• Monomial Tropical Cones for Multicriteria Optimization
• Complete solution of a constrained tropical optimization problem with application to location analysis
• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems
• A constrained tropical optimization problem: Complete solution and application example
• Solution of mathematical programming problems using tropical optimization methods
• Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling
• Solution of a tropical optimization problem with linear constraints
• Tropical algebras and the shortest path
• Using tropical optimization to solve minimax location problems with a rectilinear metric on the line
• Solution of a two-facility location problem in a space with Chebyshev distance

This page was built for publication: Algebraic solutions of tropical optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266221)