RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Vestnik YuUrGU. Ser. Mat. Model. Progr.: Year: Volume: Issue: Page: Find

 Vestnik YuUrGU. Ser. Mat. Model. Progr., 2019, Volume 12, Issue 1, Pages 150–155 (Mi vyuru480)

Short Notes

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

Abstract: 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.

Keywords: itshape allocation problem, linear programming, duality, relaxation, integer solution, polynomial algorithm, Weber problem.

DOI: https://doi.org/10.14529/mmp190114

Full text: PDF file (154 kB)
References: PDF file   HTML file

UDC: 519.688
MSC: 68Q25, 90C27, 49M20
Language:

Citation: 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
\Bibitem{Pan19} \by A.~V.~Panyukov \paper On the existence of an integer solution of the relaxed Weber problem for a tree network \jour Vestnik YuUrGU. Ser. Mat. Model. Progr. \yr 2019 \vol 12 \issue 1 \pages 150--155 \mathnet{http://mi.mathnet.ru/vyuru480} \crossref{https://doi.org/10.14529/mmp190114} \elib{http://elibrary.ru/item.asp?id=37092215}