A Maximization Problem in Tropical Mathematics: A Complete Solution and Application Examples

Article type: Research Article

Authors: Krivulin, Nikolai

Affiliations: Faculty of Mathematics and Mechanics, Saint Petersburg State University, 28 Universitetsky Ave., St. Petersburg, 198504, Russia. E-mail: nkk@math.spbu.ru

Abstract: An optimization problem is formulated in the tropical mathematics setting to maximize a nonlinear objective function defined by conjugate transposition on vectors in a semimodule over a general idempotent semifield. The study is motivated by problems from project scheduling, where the deviation between completion times of activities is to be maximized subject to precedence constraints. To solve the unconstrained problem, we establish an upper bound for the function, and then obtain a complete solution to a system of vector equations to find all vectors that yield the bound. An extension of the solution to handle constrained problems is discussed. The results are applied to give direct solutions to the motivational problems, and illustrated with numerical examples.

Keywords: tropical mathematics, idempotent semifield, optimization problem, nonlinear objective function, project scheduling

Journal: Informatica, vol. 27, no. 3, pp. 587-606, 2016