Volume 15, No 4, 2008, P. 3-24

UDC 519.87
V. L. Beresnev
Upper bounds for goal functions of discrete competitive facility location problems

Abstract:
The facility location problems in the presence of competition are considered, when two competitive firms open facilities sequentially and each client selects one of the open facilities according to his preferences and profits either the first firm (Leader) or the second (Follower). The problem is to find a facility location for the Leader which maximizes its profits with the optimal reaction of the Follower taken into account. The formulations which differ in the Follower’s goal function are considered. The models are formulated as bilevel linear integer programming problems and equivalent formulations of these problems are presented in the form of the bilevel pseudo-Boolean programming. A polynomial time algorithm for the problems is presented in the case, where facilities and clients are points of a path. A method of construction of an upper bound for optimal values of the Leader’s profit is proposed. The corresponding algorithm consists in construction of an auxiliary pseudo-Boolean function and computing an optimal solution yielding minimal value of this function. Computational results illustrate the good performance of the upper bound for the test examples of the problem on a path. 
Table 1, illustr. 1, bibl. 8.

Keywords: bilevel programming problem, upper bound, optimal solution, pseudo-Boolean function.

Beresnev Vladimir Leonidovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: beresnev@math.nsc.ru