Vestnik YuUrGU. Ser. Mat. Model. Progr., 2019, Volume 12, Issue 1, Pages 150–155
On the existence of an integer solution of the relaxed Weber problem for a tree network
A. V. Panyukov
South Ural State University, Chelyabinsk, Russian Federation
The problem of finding the optimal arrangement of vertices of a tree network in the installation space representing a finite set is considered. The criterion of optimality is the minimization of the total cost of deployment and the cost of communications. Placement of different tree vertices in one point of the installation space is allowed. This problem is known as Weber problem for a tree network. The statement of Weber problem as an integer linear programming problem is given in this research. It's proved that a set of optimal solutions of corresponding relaxed Weber problem for a tree-network contains the integer solution. This fact allows to prove the existence a saddle point while proving the performance of decomposition algorithms for problems different from problems because of additional restrictions.
itshape allocation problem, linear programming, duality, relaxation, integer solution, polynomial algorithm, Weber problem.
PDF file (154 kB)
MSC: 68Q25, 90C27, 49M20
A. V. Panyukov, “On the existence of an integer solution of the relaxed Weber problem for a tree network”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 12:1 (2019), 150–155
Citation in format AMSBIB
\paper On the existence of an integer solution of the relaxed Weber problem for a tree network
\jour Vestnik YuUrGU. Ser. Mat. Model. Progr.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|