BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nikolai Krivulin

Nikolai Krivulin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCSystems and ControlDiscrete MathematicsComputationeess.SYmath.PRApplicationsmath.ACMethodology

Catalog footprint

What is connected

27works
9topics
2close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2021arXiv

Algebraic solution to constrained bi-criteria decision problem of rating alternatives through pairwise comparisons

We consider a decision-making problem to evaluate absolute ratings of alternatives from the results of their pairwise comparisons according to two criteria, subject to constraints on the ratings. We formulate the problem as a bi-objective optimization problem of constrained matrix approximation in the Chebyshev sense in logarithmic scale. The problem is to approximate the pairwise comparison matrices for each criterion simultaneously by a common consistent matrix of unit rank, which determines the vector of ratings. We represent and solve the optimization problem in the framework of tropical (idempotent) algebra, which deals with the theory and applications of idempotent semirings and semifields. The solution involves the introduction of two parameters that represent the minimum values of approximation error for each matrix and thereby describe the Pareto frontier for the bi-objective problem. The optimization problem then reduces to a parametrized vector inequality. The necessary and sufficient conditions for solutions of the inequality serve to derive the Pareto frontier for the problem. All solutions of the inequality, which correspond to the Pareto frontier, are taken as a complete Pareto-optimal solution to the problem. We apply these results to the decision problem of interest and present illustrative examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algebraic solution of minimax single-facility constrained location problems with Chebyshev and rectilinear distances

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Complete solution of tropical vector inequalities using matrix sparsification

We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, remark on its computational complexity and illustrate this technique with numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tropical optimization technique in bi-objective project scheduling under temporal constraints

We consider a project that consists of a set of activities performed in parallel under constraints on their start and finish times, including start-finish precedence relationships, release start times, release end times, and deadlines. The problems of interest are to decide on the optimal schedule of the activities to minimize both the maximum flow-time over all activities, and the project makespan. We formulate these problems as bi-objective optimization problems in the framework of tropical mathematics which investigates the theory and applications of algebraic systems with idempotent operations and has various applications in management science and operations research. Then, the use of methods and techniques of tropical optimization allows to derive complete Pareto-optimal solutions of the problems in a direct explicit form ready for further analysis and straightforward computation. We discuss the computational complexity of the solution and give illustrative examples.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Tropical implementation of the Analytical Hierarchy Process decision method

We apply methods and techniques of tropical optimization to develop a new theoretical and computational framework for the implementation of the Analytic Hierarchy Process in multi-criteria problems of rating alternatives from pairwise comparison data. In this framework, we first consider the minimax Chebyshev approximation of pairwise comparison matrices by consistent matrices in the logarithmic scale. Recasting this approximation problem as a problem of tropical pseudo-quadratic programming we then write out a closed-form solution to it. This solution might be either a unique score vector (up to a positive factor) or a set of different score vectors. To handle the problem when the solution is not unique, we develop tropical optimization techniques of maximizing and minimizing the Hilbert seminorm to find those vectors from the solution set that are the most and least differentiating between the alternatives with the highest and lowest scores, and thus are well representative of the entire solution set.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rating alternatives from pairwise comparisons by solving tropical optimization problems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Complete solution of a constrained tropical optimization problem with application to location analysis

We present a multidimensional optimization problem that is formulated and solved in the tropical mathematics setting. The problem consists of minimizing a nonlinear objective function defined on vectors over an idempotent semifield by means of a conjugate transposition operator, subject to constraints in the form of linear vector inequalities. A complete direct solution to the problem under fairly general assumptions is given in a compact vector form suitable for both further analysis and practical implementation. We apply the result to solve a multidimensional minimax single facility location problem with Chebyshev distance and with inequality constraints imposed on the feasible location area.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Extremal properties of tropical eigenvalues and solutions to tropical optimization problems

An unconstrained optimization problem is formulated in terms of tropical mathematics to minimize a functional that is defined on a vector set by a matrix and calculated through multiplicative conjugate transposition. For some particular cases, the minimum in the problem is known to be equal to the tropical spectral radius of the matrix. We examine the problem in the common setting of a general idempotent semifield. A complete direct solution in a compact vector form is obtained to this problem under fairly general conditions. The result is extended to solve new tropical optimization problems with more general objective functions and inequality constraints. Applications to real-world problems that arise in project scheduling are presented. To illustrate the results obtained, numerical examples are also provided.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tropical optimization problems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A constrained tropical optimization problem: complete solution and application example

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A multidimensional tropical optimization problem with nonlinear objective function and linear constraints

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Direct solutions to tropical optimization problems with nonlinear objective functions and boundary constraints

We examine two multidimensional optimization problems that are formulated in terms of tropical mathematics. The problems are to minimize nonlinear objective functions, which are defined through the multiplicative conjugate vector transposition on vectors of a finite-dimensional semimodule over an idempotent semifield, and subject to boundary constraints. The solution approach is implemented, which involves the derivation of the sharp bounds on the objective functions, followed by determination of vectors that yield the bound. Based on the approach, direct solutions to the problems are obtained in a compact vector form. To illustrate, we apply the results to solving constrained Chebyshev approximation and location problems, and give numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Explicit solution of a tropical optimization problem with application to project scheduling

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Solution of linear equations and inequalities in idempotent vector spaces

Linear vector equations and inequalities are considered defined in terms of idempotent mathematics. To solve the equations, we apply an approach that is based on the analysis of distances between vectors in idempotent vector spaces. The approach reduces the solution of the equation to that of an optimization problem in the idempotent algebra setting. Based on the approach, existence and uniqueness conditions are established for the solution of equations, and a general solution to both linear equations and inequalities are given. Finally, a problem of simultaneous solution of equations and inequalities is also considered.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A complete closed-form solution to a tropical extremal problem

A multidimensional extremal problem in the idempotent algebra setting is considered which consists in minimizing a nonlinear functional defined on a finite-dimensional semimodule over an idempotent semifield. The problem integrates two other known problems by combining their objective functions into one general function and includes these problems as particular cases. A new solution approach is proposed based on the analysis of linear inequalities and spectral properties of matrices. The approach offers a comprehensive solution to the problem in a closed form that involves performing simple matrix and vector operations in terms of idempotent algebra and provides a basis for the development of efficient computational algorithms and their software implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A new algebraic solution to multidimensional minimax location problems with Chebyshev distance

Both unconstrained and constrained minimax single facility location problems are considered in multidimensional space with Chebyshev distance. A new solution approach is proposed within the framework of idempotent algebra to reduce the problems to solving linear vector equations and minimizing functionals defined on some idempotent semimodule. The approach offers a solution in a closed form that actually involves performing matrix-vector multiplications in terms of idempotent algebra for appropriate matrices and vectors. To illustrate the solution procedures, numerical and graphical examples of two-dimensional problems are given.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A solution of a tropical linear vector equation

A linear vector equation is considered defined in terms of idempotent mathematics. To solve the equation, we apply an approach that is based on the analysis of distances between vectors in idempotent vector spaces and reduces the solution of the equation to that of a tropical optimization problem. Based on the approach, existence and uniqueness conditions are established for the solution, and a general solution to the equation is given.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A tropical extremal problem with nonlinear objective function and linear inequality constraints

We consider a multidimensional extremal problem formulated in terms of tropical mathematics. The problem is to minimize a nonlinear objective function, which is defined on a finite-dimensional semimodule over an idempotent semifield, subject to linear inequality constraints. An efficient solution approach is developed which reduces the problem to that of solving a linear inequality with an extended set of unknown variables. We use the approach to obtain a complete solution to the problem in a closed form under quite general assumptions. To illustrate the obtained results, a two-dimensional problem is examined and its numerical solution is given.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Algebraic solution to a constrained rectilinear minimax location problem on the plane

We consider a constrained minimax single facility location problem on the plane with rectilinear distance. The feasible set of location points is restricted to rectangles with sides oriented at a 45 degrees angle to the axes of Cartesian coordinates. To solve the problem, an algebraic approach based on an extremal property of eigenvalues of irreducible matrices in idempotent algebra is applied. A new algebraic solution is given that reduces the problem to finding eigenvalues and eigenvectors of appropriately defined matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Algebraic solutions to multidimensional minimax location problems with Chebyshev distance

Multidimensional minimax single facility location problems with Chebyshev distance are examined within the framework of idempotent algebra. A new algebraic solution based on an extremal property of the eigenvalues of irreducible matrices is given. The solution reduces both unconstrained and constrained location problems to evaluation of the eigenvalue and eigenvectors of an appropriate matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An algebraic approach to multidimensional minimax location problems with Chebyshev distance

Minimax single facility location problems in multidimensional space with Chebyshev distance are examined within the framework of idempotent algebra. The aim of the study is twofold: first, to give a new algebraic solution to the location problems, and second, to extend the area of application of idempotent algebra. A new algebraic approach based on investigation of extremal properties of eigenvalues for irreducible matrices is developed to solve multidimensional problems that involve minimization of functionals defined on idempotent vector semimodules. Furthermore, an unconstrained location problem is considered and then represented in the idempotent algebra settings. A new algebraic solution is given that reduces the problem to evaluation of the eigenvalue and eigenvectors of an appropriate matrix. Finally, the solution is extended to solve a constrained location problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An algebraic approach to project schedule development under precedence constraints

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An analysis of the least median of squares regression problem

The optimization problem that arises out of the least median of squared residuals method in linear regression is analyzed. To simplify the analysis, the problem is replaced by an equivalent one of minimizing the median of absolute residuals. A useful representation of the last problem is given to examine properties of the objective function and estimate the number of its local minima. It is shown that the exact number of local minima is equal to $ {p+\lfloor (n-1)/2 \rfloor \choose{p}} $, where $ p $ is the dimension of the regression model and $ n $ is the number of observations. As applications of the results, three algorithms are also outlined.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Evaluation of the Lyapunov exponent for generalized linear second-order exponential systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Evaluation of the mean cycle time in stochastic discrete event dynamic systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Unbiased estimates for gradients of stochastic network performance measures

Three classes of stochastic networks and their performance measures are considered. These performance measures are defined as the expected value of some random variables and cannot normally be obtained analytically as functions of network parameters in a closed form. We give similar representations for the random variables to provide a useful way of analytical study of these functions and their gradients. The representations are used to obtain sufficient conditions for the gradient estimates to be unbiased. The conditions are rather general and usually met in simulation study of the stochastic networks. Applications of the results are discussed and some practical algorithms of calculating unbiased estimates of the gradients are also presented.

0 citations0 reviewsNo code linkedOpen access