|
Optimization, System Analysis, and Operations Research
On the existence of an integer solution to the relaxed Weber problem for a tree network
A. V. Panyukov South Ural State University (National Research University), Chelyabinsk, Russia
Abstract:
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.
Keywords:
location problem, integer linear programming problem, relaxed problem, computational complexity, polynomial algorithm.
Citation:
A. V. Panyukov, “On the existence of an integer solution to the relaxed Weber problem for a tree network”, Avtomat. i Telemekh., 2019, no. 7, 134–141; Autom. Remote Control, 80:7 (2019), 1288–1293
Linking options:
https://www.mathnet.ru/eng/at15167 https://www.mathnet.ru/eng/at/y2019/i7/p134
|
Statistics & downloads: |
Abstract page: | 148 | Full-text PDF : | 12 | References: | 21 | First page: | 9 |
|