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

Research output

### Abstract

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.
Original language English 91 Published - Jul 2016 20th Conference of the International Linear Algebra Society - KU Leuven, LeuvenDuration: 11 Jul 2016 → 15 Jul 2016https://ilas2016.cs.kuleuven.be/

### Conference

Conference 20th Conference of the International Linear Algebra Society ILAS2016 Belgium Leuven 11/07/16 → 15/07/16 https://ilas2016.cs.kuleuven.be/

### Fingerprint

Minimax Problems
Location Problem
Chebyshev
Optimization Techniques
Facility Location
Idempotent
Semifield
Scientific notation
Facility Location Problem
Formal Analysis
Graphical Representation
Equality Constraints
Inequality Constraints
Explicit Solution
Minimax
Nonlinear Function
Closed-form
High-dimensional
Objective function
Numerical Solution

### Cite this

Кривулин, Н. К. (2016). Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances. 91. Abstract from 20th Conference of the International Linear Algebra Society, Leuven, .
@conference{12b11dbb149e41cdbb4b9404d745030c,
title = "Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances",
abstract = "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.",
author = "Кривулин, {Николай Кимович}",
note = "Book of Abstracts. 20th ILAS Conference, 11—15 July 2016, KU Leuven; 20th Conference of the International Linear Algebra Society, ILAS2016 ; Conference date: 11-07-2016 Through 15-07-2016",
year = "2016",
month = "7",
language = "English",
pages = "91",
url = "https://ilas2016.cs.kuleuven.be/",

}

2016. 91 Abstract from 20th Conference of the International Linear Algebra Society, Leuven, .

Research output

TY - CONF

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

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

N1 - Book of Abstracts. 20th ILAS Conference, 11—15 July 2016, KU Leuven

PY - 2016/7

Y1 - 2016/7

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

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

M3 - Abstract

SP - 91

ER -

Кривулин НК. Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances. 2016. Abstract from 20th Conference of the International Linear Algebra Society, Leuven, .