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

A. V. Panyukov

doi:10.14529/mmp190114

Authors

A. V. Panyukov South Ural State University

DOI:

https://doi.org/10.14529/mmp190114

Keywords:

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

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.

Author Biography

A. V. Panyukov, South Ural State University

Doctor of Physico-Mathematical Sciences, Professor

References

Beresnev V.L., Diskretnye zadachi razmeshcheniya i polinomy ot bulevykh peremennykh [Discrete Location Problems and Polynomials of Boolean Variables]. Novosibirsk, Sobolev Institute Press, 2005. (in Russian)

Nickel S., Puerto J. Location Theory. Heidelberg, Springer, 2005.

Zabudskii G.G., Veremchuk N.S. An Algorithm for Finding an Approximate Solution to the Weber Problem on a Line with Forbidden Gaps. Journal of Applied and Industrial Mathematics, 2016, vol. 10, no. 1, pp. 136–144. DOI: 10.1134/S1990478916010154

Zabudskii G.G., Koval A.A. Solving a Maximin Location Problem on the Plane with Given Accuracy. Automation and Remote Control, 2014, vol. 75, pp. 1221–1230. DOI:10.1134/S0005117914070042

Panyukov A.V., Pelzwerger B.V. Polynomial Algorithms to Finite Weber Problem for a Tree Network. Journal of Computational and Applied Mathematics, 1991, vol. 35, pp. 291–296.

DOI:10.1016/0377-0427(91)90215-6

Ivanko E.E. Iterative Equitable Partition of Graph as a Model of Constant Structure Discrete Time Closed Semantic System. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2017, vol. 10, no. 4, pp. 26–34. DOI: 10.14529/mmp170403

Panyukov A.V. The Relaxation Polyhedron of Weber Problem. Non-Smooth and Discontinuous Problems of Control and Optimization, Chelyabinsk, 1998, pp. 171–174.

Panyukov A.V. Location of a Tree Network for a Finite Set. Abstracts of the Seventh Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications, Kosice, Safary University, 2013, p. 64.