Volume 16, No 2, 2009, P. 21-41

UDC 519.854.2
I. L.Vasiliev, K. B. Klimentova
A branch and bound method for the facility location problem with customer preferences

Abstract:
The article is focused on computational study of the bilevel facility location problem with customer’s preferences taken into account. Different integer linear programming formulations are considered. The cutting plane method is implemented for the new family of valid inequalities which are based on relation with the problem for a pair of matrices. The optimal solution of the problem is searched by two variants of branch and bound method using the cutting plane method implemented. The upper bounds for these exact methods are found by Simulated Annealing method. The computational experience illustrates the effectiveness of the proposed methods in comparison with the known approaches.
Il. 1, tabl. 7, bibl. 15.

Keywords: bilevel facility location problem, cutting plane method, local search, branch and bound method.

Vasilyev Igor Leonidovich ¹
Klimentova Xenia Borisovna ¹
1. Institute of System Dynamics and Control Theory SB RAS,
134 Lermontov str., 664033 Irkutsk, Russia
e-mail: vil@icc.ru, Xenia.Klimentova@icc.ru