Nikolai Krivulin

Nikolai Krivulin

We examine a multidimensional optimisation problem in the tropical mathematics setting. The problem involves the minimisation of a nonlinear function defined on a finite-dimensional semimodule over an idempotent semifield subject to linear inequality constraints. We start with an overview of known tropical optimisation problems with linear and nonlinear objective functions. A short introduction to tropical algebra is provided to offer a formal framework for solving the problem under study. As a preliminary result, a solution to a linear inequality with an arbitrary matrix is presented. We describe an example optimisation problem drawn from project scheduling and then offer a general representation of the problem. To solve the problem, we introduce an additional variable and reduce the problem to the solving of a linear inequality, in which the variable plays the role of a parameter. A necessary and sufficient condition for the inequality to hold is used to evaluate the parameter, whereas the solution to the inequality is considered a solution to the problem. Based on this approach, a complete direct solution in a compact vector form is derived for the optimisation problem under fairly general conditions. Numerical and graphical examples for two-dimensional problems are given to illustrate the obtained results.

Nikolai Krivulin

We consider optimization problems that are formulated and solved in the framework of tropical mathematics. The problems consist in minimizing or maximizing functionals defined on vectors of finite-dimensional semimodules over idempotent semifields, and may involve constraints in the form of linear equations and inequalities. The objective function can be either a linear function or nonlinear function calculated by means of multiplicative conjugate transposition of vectors. We start with an overview of known tropical optimization problems and solution methods. Then, we formulate certain new problems and present direct solutions to the problems in a closed compact vector form suitable for further analysis and applications. For many problems, the results obtained are complete solutions.

Nikolai Krivulin

We consider multidimensional optimization problems in the framework of tropical mathematics. The problems are formulated to minimize a nonlinear objective function that is defined on vectors over an idempotent semifield and calculated by means of multiplicative conjugate transposition. We start with an unconstrained problem and offer two complete direct solutions to demonstrate different practicable argumentation schemes. The first solution consists of the derivation of a sharp lower bound for the objective function and the solving of an equation to find all vectors that yield the bound. The second is based on extremal properties of the spectral radius of matrices and involves the evaluation of this radius for a certain matrix. This solution is then extended to problems with boundary constraints that specify the feasible solution set by a double inequality, and with a linear inequality constraint given by a matrix. To illustrate one application of the results obtained, we solve problems in project scheduling under the minimum makespan criterion subject to various precedence constraints on the time of initiation and completion of activities in the project. Simple numerical examples are given to show the computational technique used for solutions.

Nikolai Krivulin

We consider problems of rating alternatives based on their pairwise comparison under various assumptions, including constraints on the final scores of alternatives. The problems are formulated in the framework of tropical mathematics to approximate pairwise comparison matrices by reciprocal matrices of unit rank, and written in a common form for both multiplicative and additive comparison scales. To solve the unconstrained and constrained approximation problems, we apply recent results in tropical optimization, which provide new complete direct solutions given in a compact vector form. These solutions extend known results and involve less computational effort. As an illustration, numerical examples of rating alternatives are presented.

Nikolai Krivulin

A new multidimensional optimization problem is considered in the tropical mathematics setting. The problem is to minimize a nonlinear function defined on a finite-dimensional semimodule over an idempotent semifield and given by a conjugate transposition operator. A special case of the problem, which arises in just-in-time scheduling, serves as a motivation for the study. To solve the general problem, we derive a sharp lower bound for the objective function and then find vectors that yield the bound. Under general conditions, an explicit solution is obtained in a compact vector form. This result is applied to provide new solutions for scheduling problems under consideration. To illustrate, numerical examples are also presented.

Nikolai Krivulin

We consider location problems to find the optimal sites of placement of a new facility, which minimize the maximum weighted Chebyshev or rectilinear distance to existing facilities under constraints on a feasible location domain. We examine Chebyshev location problems in multidimensional space to represent and solve the problems in the framework of tropical (idempotent) algebra, which deals with the theory and applications of semirings and semifields with idempotent addition. The solution approach involves formulating the problem as a tropical optimization problem, introducing a parameter that represents the minimum value of the objective function in the problem, and reducing the problem to a system of parametrized inequalities. The necessary and sufficient conditions for the existence of a solution to the system serve to evaluate the minimum, whereas all corresponding solutions of the system present a complete solution of the optimization problem. With this approach we obtain direct, exact solutions represented in a compact closed form which is appropriate for further analysis and straightforward computations with polynomial time complexity. The solutions of the Chebyshev problems are then used to solve location problems with rectilinear distance in the two-dimensional plane. The obtained solutions extend previous results on the Chebyshev and rectilinear location problems without weights and with less general constraints.

Nikolai Krivulin

We consider multidimensional optimization problems that are formulated in the framework of tropical mathematics to minimize functions defined on vectors over a tropical semifield (a semiring with idempotent addition and invertible multiplication). The functions, given by a matrix and calculated through multiplicative conjugate transposition, are nonlinear in the tropical mathematics sense. We start with known results on the solution of the problems with irreducible matrices. To solve the problems in the case of arbitrary (reducible) matrices, we first derive the minimum value of the objective function, and find a set of solutions. We show that all solutions of the problem satisfy a system of vector inequalities, and then use these inequalities to establish characteristic properties of the solution set. Furthermore, all solutions of the problem are represented as a family of subsets, each defined by a matrix that is obtained by using a matrix sparsification technique. We describe a backtracking procedure that allows one to reduce the brute-force generation of sparsified matrices by skipping those, which cannot provide solutions, and thus offers an economical way to obtain all subsets in the family. Finally, the characteristic properties of the solution set are used to provide complete solutions in a closed form. We illustrate the results obtained with simple numerical examples.

Nikolai Krivulin

We consider stochastic discrete event dynamic systems that have time evolution represented with two-dimensional state vectors through a vector equation that is linear in terms of an idempotent semiring. The state transitions are governed by second-order random matrices that are assumed to be independent and identically distributed. The problem of interest is to evaluate the mean growth rate of state vector, which is also referred to as the mean cycle time of the system, under various assumptions on the matrix entries. We give an overview of early results including a solution for systems determined by matrices with independent entries having a common exponential distribution. It is shown how to extend the result to the cases when the entries have different exponential distributions and when some of the entries are replaced by zero. Finally, the mean cycle time is calculated for systems with matrices that have one random entry, whereas the other entries in the matrices can be arbitrary nonnegative and zero constants. The random entry is always assumed to have exponential distribution except for one case of a matrix with zero row when the particular form of the matrix makes it possible to obtain a solution that does not rely on exponential distribution assumptions.

Nikolai Krivulin

We consider generalized linear stochastic dynamical systems with second-order state transition matrices. The entries of the matrix are assumed to be either independent and exponentially distributed or equal to zero. We give an overview of new results on evaluation of asymptotic growth rate of the system state vector, which is called the Lyapunov exponent of the system.

Nikolai Krivulin

An approach to schedule development in project management is developed within the framework of idempotent algebra. The approach offers a way to represent precedence relationships among activities in projects as linear vector equations in terms of an idempotent semiring. As a result, many issues in project scheduling reduce to solving computational problems in the idempotent algebra setting, including linear equations and eigenvalue-eigenvector problems. The solutions to the problems are given in a compact vector form that provides the basis for the development of efficient computation procedures and related software applications.

Nikolai Krivulin

The aim of this paper is twofold: first, to extend the area of applications of tropical optimization by solving new constrained location problems, and second, to offer new closed-form solutions to general problems that are of interest to location analysis. We consider a constrained minimax single-facility location problem with addends on the plane with rectilinear distance. The solution commences with the representation of the problem in a standard form, and then in terms of tropical mathematics, as a constrained optimization problem. We use a transformation technique, which can act as a template to handle optimization problems in other application areas, and hence is of independent interest. To solve the constrained optimization problem, we apply methods and results of tropical optimization, which provide direct, explicit solutions. The results obtained serve to derive new solutions of the location problem, and of its special cases with reduced sets of constraints, in a closed form, ready for practical implementation and immediate computation. As illustrations, numerical solutions of example problems and their graphical representation are given. We conclude with an application of the results to optimal location of the central monitoring facility in an indoor video surveillance system in a multi-floor building environment.

Nikolai Krivulin

We apply methods of tropical optimization to handle problems of rating alternatives on the basis of the log-Chebyshev approximation of pairwise comparison matrices. We derive a direct solution in a closed form, and investigate the obtained solution when it is not unique. Provided the approximation problem yields a set of score vectors, rather than a unique (up to a constant factor) one, we find those vectors in the set, which least and most differentiate between the alternatives with the highest and lowest scores, and thus can be representative of the entire solution.

Nikolai Krivulin

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.