Application of tropical optimization techniques to the solution of location problems

Research output

Abstract

We consider minimax single-facility location problems in multidimensional spaces with Chebyshev and rectilinear distances. Both unconstrained problems and problems with constraints imposed on the feasible location area are under examination. We start with the description of the location problems in a standard form, and then represent them in the framework of tropical (idempotent) algebra as constrained tropical optimization problems. These problems involve the minimization of non-linear objective functions defined on vectors over an idempotent semifield, subject to vector inequality and equality constraints. We apply methods and results of tropical optimization to obtain direct, explicit solutions to the problems. To solve the problem, we introduce a variable to represent the minimum value of the objective function, and then reduce the optimization problem to an inequality with the new variable in the role of a parameter. The existence conditions for the solution of the inequality serve to evaluate the parameter, whereas the solutions of the inequality are taken as a complete solution to the problem. We use the results obtained to derive solutions of the location problems of interest in a closed form, which is ready for immediate computation. Extensions of the approach to solve other problems, including minimax multi-facility location problems, are discussed. Numerical solutions of example problems are given, and graphical illustrations are presented.
Original languageEnglish
Pages95
Publication statusPublished - Jul 2016
Event28th European Conference on Operational Research - Poznan
Duration: 3 Jul 20166 Jul 2016
http://www.euro2016.poznan.pl/

Conference

Conference28th European Conference on Operational Research
Abbreviated titleEURO2016
CountryPoland
CityPoznan
Period3/07/166/07/16
Internet address

Fingerprint

Location Problem
Optimization Techniques
Facility Location Problem
Idempotent
Objective function
Optimization Problem
Semifield
Minimax Problems
Scientific notation
Equality Constraints
Inequality Constraints
Explicit Solution
Chebyshev
Minimax
Nonlinear Function
Closed-form
Numerical Solution
Algebra
Optimization
Evaluate

Scopus subject areas

  • Management Science and Operations Research
  • Control and Optimization
  • Algebra and Number Theory

Cite this

Кривулин, Н. К. (2016). Application of tropical optimization techniques to the solution of location problems. 95. Abstract from 28th European Conference on Operational Research, Poznan, .
@conference{5a7bc447799c4f778df8f068419c5166,
title = "Application of tropical optimization techniques to the solution of location problems",
abstract = "We consider minimax single-facility location problems in multidimensional spaces with Chebyshev and rectilinear distances. Both unconstrained problems and problems with constraints imposed on the feasible location area are under examination. We start with the description of the location problems in a standard form, and then represent them in the framework of tropical (idempotent) algebra as constrained tropical optimization problems. These problems involve the minimization of non-linear objective functions defined on vectors over an idempotent semifield, subject to vector inequality and equality constraints. We apply methods and results of tropical optimization to obtain direct, explicit solutions to the problems. To solve the problem, we introduce a variable to represent the minimum value of the objective function, and then reduce the optimization problem to an inequality with the new variable in the role of a parameter. The existence conditions for the solution of the inequality serve to evaluate the parameter, whereas the solutions of the inequality are taken as a complete solution to the problem. We use the results obtained to derive solutions of the location problems of interest in a closed form, which is ready for immediate computation. Extensions of the approach to solve other problems, including minimax multi-facility location problems, are discussed. Numerical solutions of example problems are given, and graphical illustrations are presented.",
author = "Кривулин, {Николай Кимович}",
note = "28th European Conference on Operational Research (EURO2016), Poznan 3-6 July 2016. Conference Handbook; 28th European Conference on Operational Research, EURO2016 ; Conference date: 03-07-2016 Through 06-07-2016",
year = "2016",
month = "7",
language = "English",
pages = "95",
url = "http://www.euro2016.poznan.pl/",

}

Application of tropical optimization techniques to the solution of location problems. / Кривулин, Николай Кимович.

2016. 95 Abstract from 28th European Conference on Operational Research, Poznan, .

Research output

TY - CONF

T1 - Application of tropical optimization techniques to the solution of location problems

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

N1 - 28th European Conference on Operational Research (EURO2016), Poznan 3-6 July 2016. Conference Handbook

PY - 2016/7

Y1 - 2016/7

N2 - We consider minimax single-facility location problems in multidimensional spaces with Chebyshev and rectilinear distances. Both unconstrained problems and problems with constraints imposed on the feasible location area are under examination. We start with the description of the location problems in a standard form, and then represent them in the framework of tropical (idempotent) algebra as constrained tropical optimization problems. These problems involve the minimization of non-linear objective functions defined on vectors over an idempotent semifield, subject to vector inequality and equality constraints. We apply methods and results of tropical optimization to obtain direct, explicit solutions to the problems. To solve the problem, we introduce a variable to represent the minimum value of the objective function, and then reduce the optimization problem to an inequality with the new variable in the role of a parameter. The existence conditions for the solution of the inequality serve to evaluate the parameter, whereas the solutions of the inequality are taken as a complete solution to the problem. We use the results obtained to derive solutions of the location problems of interest in a closed form, which is ready for immediate computation. Extensions of the approach to solve other problems, including minimax multi-facility location problems, are discussed. Numerical solutions of example problems are given, and graphical illustrations are presented.

AB - We consider minimax single-facility location problems in multidimensional spaces with Chebyshev and rectilinear distances. Both unconstrained problems and problems with constraints imposed on the feasible location area are under examination. We start with the description of the location problems in a standard form, and then represent them in the framework of tropical (idempotent) algebra as constrained tropical optimization problems. These problems involve the minimization of non-linear objective functions defined on vectors over an idempotent semifield, subject to vector inequality and equality constraints. We apply methods and results of tropical optimization to obtain direct, explicit solutions to the problems. To solve the problem, we introduce a variable to represent the minimum value of the objective function, and then reduce the optimization problem to an inequality with the new variable in the role of a parameter. The existence conditions for the solution of the inequality serve to evaluate the parameter, whereas the solutions of the inequality are taken as a complete solution to the problem. We use the results obtained to derive solutions of the location problems of interest in a closed form, which is ready for immediate computation. Extensions of the approach to solve other problems, including minimax multi-facility location problems, are discussed. Numerical solutions of example problems are given, and graphical illustrations are presented.

M3 - Abstract

SP - 95

ER -

Кривулин НК. Application of tropical optimization techniques to the solution of location problems. 2016. Abstract from 28th European Conference on Operational Research, Poznan, .