A maximization problem in tropical mathematics: a complete solution and application examples

Nikolai Krivulin

Published 2013-04-28Version 1

A multidimensional optimization problem is formulated in the tropical mathematics setting as to maximize a nonlinear objective function, which is defined through a multiplicative conjugate transposition operator on vectors in a finite-dimensional semimodule over a general idempotent semifield. The study is motivated by problems drawn from project scheduling, where the deviation between initiation or completion times of activities in a project is to be maximized subject to various precedence constraints among the activities. To solve the unconstrained problem, we first establish an upper bound for the objective function, and then solve a system of vector equations to find all vectors that yield the bound. As a corollary, an extension of the solution to handle constrained problems is discussed. The results obtained are applied to give complete direct solutions to the motivating problems from project scheduling. Numerical examples of the development of optimal schedules are also presented.