Complete solution of an optimization problem in tropical semifield

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийглава/разделнаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

We consider a multidimensional optimization problem that is formulated in the framework of tropical mathematics to minimize a function defined on vectors over a tropical semifield (a semiring with idempotent addition and invertible multiplication). The function, given by a matrix and calculated through a multiplicative conjugate transposition, is nonlinear in the tropical mathematics sense. We show that all solutions of the problem satisfy a vector inequality, and then use this inequality to establish characteristic properties of the solution set. We examine the problem when the matrix is irreducible. We derive the minimum value in the problem, and find a set of solutions. The results are then extended to the case of arbitrary matrices. Furthermore, we represent all solutions of the problem as a family of subsets, each defined by a matrix that is obtained by using a matrix sparsification technique. We describe a backtracking procedure that offers an economical way to obtain all subsets in the family. Finally, the characteristic properties of the solution set are used to provide a complete solution in a closed form.
Язык оригиналаанглийский
Название основной публикацииRelational and Algebraic Methods in Computer Science
Подзаголовок основной публикации16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings
РедакторыPeter Höfner, Damien Pous, Georg Struth
Место публикацииCham
ИздательSpringer Nature
Страницы226-241
ISBN (электронное издание)978-3-319-57418-9
ISBN (печатное издание)978-3-319-57417-2
DOI
СостояниеОпубликовано - 2017
СобытиеThe 16th International Conference on Relational and Algebraic Methods in Computer Science - Université de Lyon, Lyon, Франция
Продолжительность: 15 мая 201718 мая 2017
Номер конференции: 16
http://www.ens-lyon.fr/LIP/PLUME/RAMiCS17/

Серия публикаций

НазваниеLecture Notes in Computer Science
ИздательSpringer International Publishing
Том10226
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференцияThe 16th International Conference on Relational and Algebraic Methods in Computer Science
Сокращенный заголовокRAMiCS 2017
СтранаФранция
ГородLyon
Период15/05/1718/05/17
Адрес в сети Интернет

Предметные области Scopus

  • Теория оптимизации
  • Теория управления и исследование операций
  • Алгебра и теория чисел

Fingerprint Подробные сведения о темах исследования «Complete solution of an optimization problem in tropical semifield». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать