TY - JOUR

T1 - Direct solution to constrained tropical optimization problems with application to project scheduling

AU - Krivulin, Nikolai

PY - 2017/1

Y1 - 2017/1

N2 - We examine a new optimization problem formulated in the tropical mathematics setting as a further extension of certain known problems. The problem is to minimize a nonlinear objective function, which is defined on vectors over an idempotent semifield by using multiplicative conjugate transposition, subject to inequality constraints. As compared to the known problems, the new one has a more general objective function and additional constraints. We provide a complete solution in an explicit form to the problem by using an approach that introduces an auxiliary variable to represent the values of the objective function, and then reduces the initial problem to a parametrized vector inequality. The minimum of the objective function is evaluated by applying the existence conditions for the solution of this inequality. A complete solution to the problem is given by solving the parametrized inequality, provided the parameter is set to the minimum value. As a consequence, we obtain solutions to new special cases of the general problem. To illustrate the application of the results, we solve a real-world problem drawn from time-constrained project scheduling, and offer a representative numerical example.

AB - We examine a new optimization problem formulated in the tropical mathematics setting as a further extension of certain known problems. The problem is to minimize a nonlinear objective function, which is defined on vectors over an idempotent semifield by using multiplicative conjugate transposition, subject to inequality constraints. As compared to the known problems, the new one has a more general objective function and additional constraints. We provide a complete solution in an explicit form to the problem by using an approach that introduces an auxiliary variable to represent the values of the objective function, and then reduces the initial problem to a parametrized vector inequality. The minimum of the objective function is evaluated by applying the existence conditions for the solution of this inequality. A complete solution to the problem is given by solving the parametrized inequality, provided the parameter is set to the minimum value. As a consequence, we obtain solutions to new special cases of the general problem. To illustrate the application of the results, we solve a real-world problem drawn from time-constrained project scheduling, and offer a representative numerical example.

KW - tropical mathematics

KW - idempotent semifield

KW - constrained optimization

KW - complete solution

KW - time-constrained project scheduling

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

U2 - 10.1007/s10287-016-0259-0

DO - 10.1007/s10287-016-0259-0

M3 - Article

VL - 14

SP - 91

EP - 113

JO - Computational Management Science

JF - Computational Management Science

SN - 1619-697X

IS - 1

ER -