Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances

Результат исследований: Материалы конференцийтезисы

Аннотация

We propose new algebraic solutions for constrained minimax single-facility location problems in multidimensional spaces with Chebyshev distance, and in the plane with rectilinear distance. We first formulate the location problems in a standard form, and outline existing solutions. Then, the problems are represented in terms of tropical (idempotent) algebra as optimization problems to minimize non-linear objective functions defined on vectors over an idempotent semifield, subject to linear vector inequality and equality constraints. We apply methods and techniques of tropical optimization to obtain direct, explicit solutions of the problems. The results obtained are used to derive solutions of the location problems under consideration in a closed form, which is ready for formal analysis and straightforward computation. We examine extensions of the approach to handle other problems, such as rectilinear single-facility location in high-dimensional spaces and multi-facility location. To illustrate, we present numerical solutions of example location problems and provide graphical representation of these solutions.
Язык оригиналаанглийский
Страницы91
СостояниеОпубликовано - июл 2016
Событие20th Conference of the International Linear Algebra Society - KU Leuven, Leuven, Бельгия
Продолжительность: 11 июл 201615 июл 2016
https://ilas2016.cs.kuleuven.be/

Конференция

Конференция20th Conference of the International Linear Algebra Society
Сокращенный заголовокILAS2016
СтранаБельгия
ГородLeuven
Период11/07/1615/07/16
Адрес в сети Интернет

    Fingerprint

Цитировать

Кривулин, Н. К. (2016). Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances. 91. Выдержка из 20th Conference of the International Linear Algebra Society, Leuven, Бельгия.