Discrete Location Problems ballred.gif (861 bytes) Benchmarks Library
line.jpg (1129 bytes)

P-Median Problem 
with Users Preferences

ballred.gif (861 bytes)  Home

ballred.gif (861 bytes)  Optimization algorithms

ballred.gif (861 bytes)  Benchmarks

ballred.gif (861 bytes)  Russian page


In the classical facility location models there is one decision maker only. As a rule, this person is a top manager which selects sites for facilities to service the clients. The set of possible sites I = {1,…, n}  and the set of clients J = {1,…, m} are given. The decision maker can open p > 0 facilities and knows the production–transportation costs cij ³ 0 for each pair (i, j), iÎI, jÎJ. The problem is to find a subset S Ì I, | S | = p of opening facilities in order to minimize the total cost for servicing all clients, i.e.

Note that for given set S, each client is serviced from the cheapest facility. It is regular for a centralized economy. But in the market economy, each client can select a facility according to own preferences. For this case, the mathematical model can be represented as a two persons game. The first decision maker is the top manager of the firm. He (she) is a Leader and makers decision at first. The second decision maker (Follower) is a person which represents the clients. He (she) knows the set S of opening facilities and selects a provider for each client. These models are known as Stakelberger games [4].

Let (dij) denote the client preferences for the set of facilities. If  then client j prefers the facility i1For simplicity we assume that all elements dij are different in each column jÎJ. Otherwise, we have to introduce optimistic and pessimistic strategies and consider cooperative and noncooperative games [2, 4].  So, the goal of Leader is to service all clients with minimal total cost, but now the Leader has to take into account the client preferences.  

Let us introduce two sets of variables:




Now the mathematical model can be presented as the bilevel programming problem [1, 3, 4]:


xi Î {0,1},  iÎI

where xij*(xi)  is the optimal solution of the Follower problem:


xij £ xi,   iÎI,   jÎJ;

xij Î {0,1},   iÎI,   jÎJ.

As before, the objective function of the Leader defines the total cost for servicing all clients. The difference from the classical model consists of in new definition of the feasible domain. Now it is described by the standard restrictions: Boolean variables (correspond to S Ì I) and number of opening facilities is  p (| | = p) and extremal restriction: optimization problem of the Follower. In this auxiliary problem the vector xi is given [3].

The first facility location models with client preferences were considered in [6]. There are different reductions of this bilevel programming problem to the integer programming problem [2, 4, 5]. It is known that the problem can be rewritten as a minimization problem for pseudo–Boolean function or the selection rows problem for the pair of matrices [1, 2]. Polynomially solvable cases are founded in [2]. If cij = dij, iÎI, jÎ J then this problem coincides with the classical p-median problem.


  1. Beresnev V.L.  Discrete location problems and polynomial s in Boolean variables. Novosibirsk . Sobolev Institute Press. 2005. (in Russian)

  2. Gorbachevskaya L.E. Polynomially solvable and NP-hard bilevel standardization problems. PhD  Thesis, Sobolev Institute of Mathematics. Novosibirsk . 1998. (in Russian)

  3. Kochetov Yu.A. The bilevel facility location problems. Proceedings   of ICM&MG. Informatics. V. 6. 2006. (in Russian)

  4. Moulin H. Théorie des Jeux Pour L’économie et la politique. Hermann. Paris . 1981.

  5. Hansen P., Kochetov Yu., Mladenovic N. Lower bounds for the uncapacitated facility location problem with user preferences. Proceedings of Discrete Optimization Methods in Production and Logistics (DOM'2004) 2nd International Workshop, Omsk . 2004. P. 50–55.

  6. Hanjoul P., Peeters D. A facility location problem with clients' preference orderings, Regional Science and Urban Economics. 1987. v. 17, P. 451–473.

ballred.gif (861 bytes) Home ballred.gif (861 bytes)