TY - JOUR

T1 - Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling

AU - Krivulin, Nikolai

N1 - Conference code: 15

PY - 2017/6

Y1 - 2017/6

N2 - Optimization problems are considered in the framework of tropical algebra to minimize and maximize a nonlinear objective function defined on vectors over an idempotent semifield, and calculated using multiplicative conjugate transposition. To find the minimum of the function, we first obtain a partial solution, which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and show that the solution set is closed under vector addition and scalar multiplication. A matrix sparsification technique is proposed to extend the partial solution, and then to obtain a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. As another result, we deduce a complete solution of the maximization problem, given in a compact vector form by the use of sparsified matrices. The results obtained are illustrated with illuminating examples and graphical representations. We apply the results to solve real-world problems drawn from project (machine) scheduling, and give numerical examples.

AB - Optimization problems are considered in the framework of tropical algebra to minimize and maximize a nonlinear objective function defined on vectors over an idempotent semifield, and calculated using multiplicative conjugate transposition. To find the minimum of the function, we first obtain a partial solution, which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and show that the solution set is closed under vector addition and scalar multiplication. A matrix sparsification technique is proposed to extend the partial solution, and then to obtain a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. As another result, we deduce a complete solution of the maximization problem, given in a compact vector form by the use of sparsified matrices. The results obtained are illustrated with illuminating examples and graphical representations. We apply the results to solve real-world problems drawn from project (machine) scheduling, and give numerical examples.

KW - tropical algebra

KW - idempotent semifield

KW - optimization problem

KW - sparse matrix

KW - backtracking

KW - just-in-time scheduling

UR - https://arxiv.org/abs/1504.02602

U2 - 10.1016/j.jlamp.2017.03.004

DO - 10.1016/j.jlamp.2017.03.004

M3 - Article

VL - 89

SP - 150

EP - 170

JO - Journal of Logical and Algebraic Methods in Programming

JF - Journal of Logical and Algebraic Methods in Programming

SN - 2352-2208

T2 - 15th International Conference on Relational and Algebraic Methods in Computer Science

Y2 - 28 September 2015 through 1 October 2015

ER -