Solving a tropical optimization problem via matrix sparsification

Nikolai Krivulin

Published 2015-04-10Version 1

A multidimensional optimization problem, which arises in just-in-time scheduling in the form of minimization of span seminorm, is considered in the framework of tropical (idempotent) mathematics. The problem is formulated to minimize a nonlinear function defined on vectors over an idempotent semifield, and calculated by means of multiplicative conjugate transposition. To solve the problem, we first find the minimum of the objective function and give a particular solution. Then, we reduce the problem to the solution of simultaneous equation and inequality, and investigate properties of the solution set. Furthermore, a new matrix sparsification technique is proposed and used to obtain an extended solution to the problem, and to derive a complete solution as a family of solution sets. Finally, we describe a backtracking procedure that generates all members of the family, and then offer an explicit representation for the complete solution in a compact vector form. Numerical examples and graphical illustrations of the results are also presented.