Discrete Location Problems ballred.gif (861 bytes) Benchmark Library

Multi Stage  Uncapacitated

Facility Location Problem

ballred.gif (861 bytes)  Home Benchmark Library

ballred.gif (861 bytes)  Optimization Algorithms

ballred.gif (861 bytes)  Benchmarks:

    R4-GapA     St4-GapC    R4-Eucl    R4-Unif     3-Galax

In the Multi Stage Uncapacitated Facility Location Problem we are given a set of facilities and a set of customers. Each customer must be serviced by a sequence of different facilities. These sequences are defined by hierarchy of production and distribution system and can be presented as facility paths. The set of admissible facility paths is given. Each facility has fixed cost. Each customer has transportation costs for servicing by the facility paths. The problem is to select facilities in order to service the customers with minimal total cost.

Now we present an example of hierarchical multi stage production system. A feasible solution of the problem is marked by black.       


Pic. Feasible solution of the problem

The Multi Stage Uncapacitated Facility Location Problem is NP-hard in strong sence. The following problems

can be reduced to the Multi Stage Uncapacitated Facility Location Problem. Mathematical formulation can be written as the mixed integer linear programming problem. Let us define the following notations: 

J = {1, ... , J}  is the set of customers;

I = {1, ... , I}   is the set of facilities;

L = {1, ... , L} is the set of admissible facility paths;

Li Ì L   is the set of facility paths contained the facility i;

fi ³ 0     is fixed cost of facility i;

clj ³  is service cost of customer j by facility path l.

The problem variables:

The Multi Stage Uncapacitated Facility Location Problem can be written as follows [5, 6]:




                      xlj, yiÎ{0,1}, lÎL,  jÎJiÎI                   (4)


The objective function (1) is the total cost of opening facilities and servicing the customers. The equations (2) guarantee that all customers are served. The conditions (3) require the fixed cost of facility if it is used for servicing the customers.


  1. V.L. Beresnev, E.Kh. Gimadi, and V.T. Dement'ev Extremal Standardization Problems. Novosibirsk: Nauka, 1978 (in Russian).

  2. L. Gorbachevskaya, V. Dement'ev, Yu. Shamardin. Bilevel  Standardization Problem with condition of unique optimal customers' choise. Discrete Analysis and Operations Research. Ser. 2. v 6 (1999), N2. pp 3-11 (in Russian).

  3. V. Beresnev Selection Problem of Tools and Component Parts. Upravlyaemye Sistemy. V.16 (1977), pp 35-46 (in Russian).

  4. V. Beresnev Minimization Algorithms for Polynomials in Boolean Variables. Problems of Cybernetics. V.36 (1979), pp 225-246 (in Russian).

  5. V. Beresnev, E. Goncharov  Heuristic Algorithm for the Minimization Problem for Polynomials in Boolean variables. Discrete Analysis and Operations Research. Ser. 2. v 5 (1998), N2. pp 3-19 (in Russian).

  6. E. Goncharov, Yu. Kochetov  Probabilistic Tabu Search Algorithm for the Multi-Stage Uncapacitated Facility Location Problem. Operations Research Proceedings 2000, Springer, Berlin, (2001), pp 65-70.

  7. S. Finkelstein, M. Schkolnik, and P. Tiberio Physical database design for relational databases. ACM Transactions on Database Systems, v.13 (1988), pp.91-128. 


line.jpg (1129 bytes)