Using tropical optimization to solve minimax location problems with a rectilinear metric on the line

Standard

Using tropical optimization to solve minimax location problems with a rectilinear metric on the line. / Krivulin, N. K.; Plotnikov, P. V.

In: Vestnik St. Petersburg University: Mathematics, Vol. 49, No. 4, 2016, p. 340-349.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{7610b35bc8984f3691e0ae330603e60f,

title = "Using tropical optimization to solve minimax location problems with a rectilinear metric on the line",

abstract = "Methods of tropical (idempotent) mathematics are applied to the solution of minimax location problems under constraints on the feasible location region. A tropical optimization problem is first considered, formulated in terms of a general semifield with idempotent addition. To solve the optimization problem, a parameter is introduced to represent the minimum value of the objective function, and then the problem is reduced to a parametrized system of inequalities. The parameter is evaluated using existence conditions for solutions of the system, whereas the solutions of the system for the obtained value of the parameter are taken as the solutions of the initial optimization problem. Then, a minimax location problem is formulated to locate a single facility on a line segment in the plane with a rectilinear metric. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. For the location problems, where the location region is restricted to a line segment, a new solution is obtained, based on the representation of the problems in the form of the tropical optimization problem considered above. Explicit solutions of the problems for various positions of the line are given both in terms of tropical mathematics and in the standard form.",

keywords = "tropical optimization, idempotent semifield, rectilinear metric, Rawls location problem with constraints",

author = "Krivulin, {N. K.} and Plotnikov, {P. V.}",

note = "Krivulin, N.K., Plotnikov, P.V. Using tropical optimization to solve minimax location problems with a rectilinear metric on the line. Vestnik St.Petersb. Univ.Math. 49, 340–349 (2016). https://doi.org/10.3103/S1063454116040087",

year = "2016",

doi = "10.3103/S1063454116040087",

language = "English",

volume = "49",

pages = "340--349",

journal = "Vestnik St. Petersburg University: Mathematics",

issn = "1063-4541",

publisher = "Pleiades Publishing",

number = "4",

}

RIS

TY - JOUR

T1 - Using tropical optimization to solve minimax location problems with a rectilinear metric on the line

AU - Krivulin, N. K.

AU - Plotnikov, P. V.

N1 - Krivulin, N.K., Plotnikov, P.V. Using tropical optimization to solve minimax location problems with a rectilinear metric on the line. Vestnik St.Petersb. Univ.Math. 49, 340–349 (2016). https://doi.org/10.3103/S1063454116040087

PY - 2016

Y1 - 2016

N2 - Methods of tropical (idempotent) mathematics are applied to the solution of minimax location problems under constraints on the feasible location region. A tropical optimization problem is first considered, formulated in terms of a general semifield with idempotent addition. To solve the optimization problem, a parameter is introduced to represent the minimum value of the objective function, and then the problem is reduced to a parametrized system of inequalities. The parameter is evaluated using existence conditions for solutions of the system, whereas the solutions of the system for the obtained value of the parameter are taken as the solutions of the initial optimization problem. Then, a minimax location problem is formulated to locate a single facility on a line segment in the plane with a rectilinear metric. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. For the location problems, where the location region is restricted to a line segment, a new solution is obtained, based on the representation of the problems in the form of the tropical optimization problem considered above. Explicit solutions of the problems for various positions of the line are given both in terms of tropical mathematics and in the standard form.

AB - Methods of tropical (idempotent) mathematics are applied to the solution of minimax location problems under constraints on the feasible location region. A tropical optimization problem is first considered, formulated in terms of a general semifield with idempotent addition. To solve the optimization problem, a parameter is introduced to represent the minimum value of the objective function, and then the problem is reduced to a parametrized system of inequalities. The parameter is evaluated using existence conditions for solutions of the system, whereas the solutions of the system for the obtained value of the parameter are taken as the solutions of the initial optimization problem. Then, a minimax location problem is formulated to locate a single facility on a line segment in the plane with a rectilinear metric. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. For the location problems, where the location region is restricted to a line segment, a new solution is obtained, based on the representation of the problems in the form of the tropical optimization problem considered above. Explicit solutions of the problems for various positions of the line are given both in terms of tropical mathematics and in the standard form.

KW - tropical optimization

KW - idempotent semifield

KW - rectilinear metric

KW - Rawls location problem with constraints

U2 - 10.3103/S1063454116040087

DO - 10.3103/S1063454116040087

M3 - Article

VL - 49

SP - 340

EP - 349

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 4

ER -

ID: 7660817