TY - JOUR

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

AU - Кривулин, Николай Кимович

N1 - Conference code: 17

PY - 2020/10

Y1 - 2020/10

N2 - 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.

AB - 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.

KW - tropical optimization

KW - idempotent semifield

KW - constrained optimization problem

KW - single-facility location problem

KW - Chebyshev and rectilinear distances

KW - Idempotence

KW - Minimax

KW - Parametrization

KW - Algebraic solution

KW - Chebyshev filter

KW - Mathematics

KW - Taxicab geometry

KW - Applied mathematics

KW - Computation

KW - Optimization problem

KW - Idempotent semifield

KW - Constrained optimization problem

KW - TROPICAL OPTIMIZATION

KW - Tropical optimization

KW - Single-facility location problem

UR - https://www.mendeley.com/catalogue/44401b31-dba3-3ef0-bf58-49f152d7b53e/

UR - http://www.scopus.com/inward/record.url?scp=85094853213&partnerID=8YFLogxK

U2 - 10.1016/j.jlamp.2020.100578

DO - 10.1016/j.jlamp.2020.100578

M3 - Article

VL - 115

SP - 1

EP - 17

JO - Journal of Logical and Algebraic Methods in Programming

JF - Journal of Logical and Algebraic Methods in Programming

SN - 2352-2208

M1 - 100578

T2 - The 17th International Conference on Relational and Algebraic Methods in Computer Science

Y2 - 29 October 2018 through 1 November 2018

ER -