Complete solution of an optimization problem in tropical semifield

Research output

2 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationRelational and Algebraic Methods in Computer Science
Subtitle of host publication16th International Conference, RAMiCS 2017, Lyon, France, May 15-18, 2017, Proceedings
EditorsPeter Höfner, Damien Pous, Georg Struth
Place of PublicationCham
PublisherSpringer Nature
Pages226-241
ISBN (Electronic)978-3-319-57418-9
ISBN (Print)978-3-319-57417-2
DOIs
Publication statusPublished - 2017
EventThe 16th International Conference on Relational and Algebraic Methods in Computer Science - Université de Lyon, Lyon
Duration: 15 May 201718 May 2017
Conference number: 16
http://www.ens-lyon.fr/LIP/PLUME/RAMiCS17/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume10226
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 16th International Conference on Relational and Algebraic Methods in Computer Science
Abbreviated titleRAMiCS 2017
CountryFrance
CityLyon
Period15/05/1718/05/17
Internet address

Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Complete solution of an optimization problem in tropical semifield'. Together they form a unique fingerprint.

Cite this