Discrete Location Problems Benchmark Library

 Multi Stage  Uncapacitated Facility Location Problem Optimization Algorithms   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

• Selection Problem of a Row Set for Pair of Matrices [1]

• Bilevel  Location Problem [2]

• Selection Problem of Tools and Component Parts [1, 3]

• Minimization Problem of Polynomial in (0,1)-Variables [4]

• Index Selection Problem [7]

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]:

(1)

(2)

(3)

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.