Volume 21, No 3, 2014, P. 64-75

UDC 519.863
A. V. Panyukov and R. E. Shangin
An exact algorithm for solving the discrete weber problem for a k-tree

Abstract:
We consider the discrete Weber problem. A consistent deterministic algorithm for finding an exact solution to the problem for a k-tree and a finite set of placement positions is suggested. The algorithm is based on the idea of dynamic programming with a decomposition tree. A numerical experiment was performed to examine the effectiveness of the proposed algorithm in comparison with IBM ILOG CPLEX. 
Ill. 2, bibliogr. 23.

Keywords: Weber problem, k-tree, dynamic programming, decomposition tree, exact algorithm.

Panyukov Anatoliy Vasilievich ¹
Shangin Roman Eduardovich ¹
1. South Ural State University,
76 Lenin Ave., 454080 Chelyabinsk, Russia
e-mail: a_panyukov@mail.ru, shanginre@gmail.com