On the Existence of an Integer Solution to the Relaxed Weber Problem for a Tree Network

Autor:	Anatoly V. Panyukov
Rok vydání:	2019
Předmět:	Set (abstract data type) Tree (descriptive set theory) Mathematical optimization Optimality criterion Linear programming Control and Systems Engineering Tree network Weber problem Electrical and Electronic Engineering Finite set Mathematics Integer (computer science)
Zdroj:	Automation and Remote Control. 80:1288-1293
ISSN:	1608-3032 0005-1179
DOI:	10.1134/s0005117919070063
Popis:	The problem of finding an optimal location of the vertices of a tree network in an assembly space representing a finite set is considered. The optimality criterion is the minimum total cost of location and communications in all points of this space. Different vertices of the tree can be located in a single point of the assembly space. This problem is well-known as the Weber problem. The representation of the Weber problem as a linear programming problem is given. It is proved that the set of all optimal solutions to the corresponding relaxed Weber problem for the tree network contains an integer solution. This fact can be used to improve the efficiency of algorithms for the problems differing from the Weber problem by the presence of additional constraints: it allows us to find the optimal value of the objective function, which in turn significantly reduces the complexity of calculating the optimal solution itself, e.g., by the branch-and-bound method.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7777734599d305995d74cbe390770113 https://doi.org/10.1134/s0005117919070063 Zobrazit plný text záznamu Plný text ve formátu PDF