Geodesic
On the existence of an integer solution of the relaxed Weber problem for a tree network
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 1, pp. 150-155

Voir la notice de l'article provenant de la source Math-Net.Ru

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, Weber problem.
Mots-clés : integer solution, polynomial algorithm 
@article{VYURU_2019_12_1_a13,
     author = {A. V. Panyukov},
     title = {On the existence of an integer solution of the relaxed {Weber} problem for a tree network},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {150--155},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a13/}
}
TY  - JOUR
AU  - A. V. Panyukov
TI  - On the existence of an integer solution of the relaxed Weber problem for a tree network
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2019
SP  - 150
EP  - 155
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a13/
LA  - en
ID  - VYURU_2019_12_1_a13
ER  - 
%0 Journal Article
%A A. V. Panyukov
%T On the existence of an integer solution of the relaxed Weber problem for a tree network
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2019
%P 150-155
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a13/
%G en
%F VYURU_2019_12_1_a13
A. V. Panyukov. On the existence of an integer solution of the relaxed Weber problem for a tree network. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 1, pp. 150-155. http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a13/