A constrained tropical optimization problem: complete solution and application example

Abstract

The paper focuses on a multidimensional optimization problem, which is formulated in terms of tropical mathematics and consists in minimizing a nonlinear objective function subject to linear inequality constraints. To solve the problem, we follow an approach based on the introduction of an additional unknown variable to reduce the problem to solving linear inequalities, where the variable plays the role of a parameter. A necessary and sufficient condition for the inequalities to hold is used to evaluate the parameter, whereas the general solution of the inequalities is taken as a solution of the original problem. Under fairly general assumptions, a complete direct solution to the problem is obtained in a compact vector form. The result is applied to solve a problem in project scheduling when an optimal schedule is given by minimizing the flow time of activities in a project under various activity precedence constraints. As an illustration, a numerical example of optimal scheduling is also presented.

20 pages, accepted for publication in Contemporary Mathematics

References in corpus (7)

• Tropical linear-fractional programming and parametric mean payoff games
• Algebraic solutions to multidimensional minimax location problems with Chebyshev distance
• The Analytic Hierarchy Process, Max Algebra and Multi-objective Optimisation
• An algebraic approach to multidimensional minimax location problems with Chebyshev distance
• A new algebraic solution to multidimensional minimax location problems with Chebyshev distance
• A tropical extremal problem with nonlinear objective function and linear inequality constraints
• A complete closed-form solution to a tropical extremal problem

Cited by in corpus (12)

• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems
• Tropical optimization problems with application to project scheduling with minimum makespan
• Direct solution to constrained tropical optimization problems with application to project scheduling
• Complete solution of a constrained tropical optimization problem with application to location analysis
• Tropical optimization problems in time-constrained project scheduling
• Tropical optimization problems
• Rating alternatives from pairwise comparisons by solving tropical optimization problems
• Algebraic solutions of tropical optimization problems
• Tropical optimization technique in bi-objective project scheduling under temporal constraints
• Minimizing maximum lateness in two-stage projects by tropical optimization
• Algebraic solution to box-constrained bi-criteria problem of rating alternatives through pairwise comparisons
• Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games