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 languageEnglish
Pages91
Publication statusPublished - Jul 2016
Event20th Conference of the International Linear Algebra Society - KU Leuven, Leuven
Duration: 11 Jul 201615 Jul 2016
https://ilas2016.cs.kuleuven.be/

Conference

Conference20th Conference of the International Linear Algebra Society
Abbreviated titleILAS2016
CountryBelgium
CityLeuven
Period11/07/1615/07/16
Internet address

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/",

}

Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances. / Кривулин, Николай Кимович.

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