# Algebraic solution of weighted minimax single-facility constrained location problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Scopus citations

## Abstract

We consider location problems to find the optimal sites of placement of a new facility, which minimize the maximum weighted Chebyshev or rectilinear distance to existing facilities under constraints on the feasible location domain. We examine a Chebyshev location problem in multidimensional space to represent and solve the problem in the framework of tropical (idempotent) algebra, which deals with the theory and applications of semirings and semifields with idempotent addition. The solution approach involves formulating the problem as a tropical optimization problem, introducing a parameter that represents the minimum value in the problem, and reducing the problem to a system of parametrized inequalities. The necessary and sufficient conditions for the existence of a solution to the system serve to evaluate the minimum, whereas all corresponding solutions of the system present a complete solution of the optimization problem. With this approach, we obtain a direct, exact solution represented in a compact closed form, which is appropriate for further analysis and straightforward computations with polynomial time complexity. The solution of the Chebyshev problem is then used to solve a location problem with rectilinear distance in the two-dimensional plane. The obtained solutions extend previous results on the Chebyshev and rectilinear location problems without weights.
Original language English Relational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Proceedings 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 – November 1, 2018, Proceedings Walter Guttmann, Jules Desharnais, Stef Joosten Cham Springer Nature 19 317-332 16 978-3-030-02149-8 978-3-030-02148-1 https://doi.org/10.1007/978-3-030-02149-8_19 Published - Oct 2018 The 17th International Conference on Relational and Algebraic Methods in Computer Science - Open University of The Netherlands, Groningen, NetherlandsDuration: 29 Oct 2018 → 1 Nov 2018Conference number: 17http://www.ramics-conference.org/

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11194 LNCS 0302-9743 1611-3349

### Conference

Conference The 17th International Conference on Relational and Algebraic Methods in Computer Science RAMiCS Netherlands Groningen 29/10/18 → 1/11/18 http://www.ramics-conference.org/

## Scopus subject areas

• Control and Optimization
• Algebra and Number Theory
• Management Science and Operations Research
• Theoretical Computer Science
• Computer Science(all)

## Keywords

• tropical mathematics
• idempotent semifield
• constrained optimization problem
• single-facility location problem
• Idempotent semifield
• Constrained optimization problem
• Tropical mathematics
• Single-facility location problem

## Fingerprint Dive into the research topics of 'Algebraic solution of weighted minimax single-facility constrained location problems'. Together they form a unique fingerprint.

• ### The 17th International Conference on Relational and Algebraic Methods in Computer Science

Николай Кимович Кривулин (Participant)

29 Oct 20181 Nov 2018

Activity: Attendance typesParticipating in a conference, workshop, ...

• ### Algebraic solution of weighted minimax single-facility constrained location problems

Николай Кимович Кривулин (Speaker)

29 Oct 2018

Activity: Talk typesOral presentation