Использование разрежения матриц для решения многомерной задачи тропической оптимизации

Translated title of the contribution: Solution of Multidimensional Tropical Optimization Problem with the Use of Matrix Sparsification

Николай Кимович Кривулин, Владимир Николаевич Сорокин

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Downloads (Pure)


A complete solution is proposed for a problem of vector-valued function minimization with elements from a tropical (idempotent) semifield. The tropical optimization problem, considered here, arises when one needs, for instance, to find the best, in the sense of Chebyshev metric, approximate solution for tropical vector equations, and occurs in various applications, including scheduling, location and decision-making problems. To solve the problem, first, the minimum value of the objective function is obtained, a characterization of the solution set in the form of a system of inequalities is proposed, and one of the solutions is presented. Then, with introduction of matrix sparsification into the problem, an extended set of solutions, and then a complete solution in the form of a family of subsets are derived. Procedures, allowing to reduce the number of subsets, which one needs to examine when constructing the complete solution, are described in the present paper. It is shown how the complete solution can be represented in parametric way in a compact vector form.
Translated title of the contributionSolution of Multidimensional Tropical Optimization Problem with the Use of Matrix Sparsification
Original languageRussian
Title of host publicationInternational Scientific Conference, 13-16 December, 2017, Borovets, Bulgaria. Mathematical Modeling
Subtitle of host publicationTechnological and Socio-Economic Processes. Proceedings
Place of PublicationSofia
PublisherScientific Technical Union of Mechanical Engineering «INDUSTRY 4.0»
StatePublished - 2017
EventInternational Scientific Conference “Mathematical Modeling”
- Sofia, Bulgaria
Duration: 13 Dec 201716 Dec 2017

Publication series

NameInternational Scientific Conference. Mathematical Modeling
PublisherScientific-Technical Union of Mechanical Engineering “INDUSTRY 4.0”
ISSN (Print)2535-0978
ISSN (Electronic)2603-3003


ConferenceInternational Scientific Conference “Mathematical Modeling”
Abbreviated titleMATHMODEL’ 17
Internet address

Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory


  • idempotent semifield
  • tropical optimization
  • Chebyshev approximation
  • complete solution
  • matrix sparsification


Dive into the research topics of 'Solution of Multidimensional Tropical Optimization Problem with the Use of Matrix Sparsification'. Together they form a unique fingerprint.

Cite this