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

Research output: Contribution to conferenceAbstractpeer-review

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
StatePublished - Jul 2016
Event20th Conference of the International Linear Algebra Society - KU Leuven, Leuven, Belgium
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 Dive into the research topics of 'Tropical optimization techniques for solving minimax location problems with Chebyshev and rectilinear distances'. Together they form a unique fingerprint.

Cite this