Two-stage stochastic facility location model with quantile criterion and choosing reliability level

When planning the development of the company activities, there is a need for planning the opening of new facilities. At the same time, the demand appearing in the future for products is not known at the time of making a decision. It is necessary to select the location of the enterprises such that to receive the maximum income from customers. Due to the random nature of demand, income is also a random value. For mathematical modelling of the decision-making process in this system, it is necessary to formulate an optimality criterion for the chosen strategy. In this case, the criterion in the form of the maximum value of the expectation is not justified, since the average income is of little interest in the case when planning is carried out for a small number of time periods. It is preferable to use a criterion that takes into account reliability requirements, in particular the quantile criterion [1]. The quantile criterion is the minimum level of losses, the non-exceeding of which is guaranteed with a given fixed probability. The use of a quantile criterion requires setting the level of reliability. Choosing the level of reliability largely depends on the specifics of the system under consideration [1], therefore, the study of methods for its determination is a problem of current interest.

Review of mathematical formulations of facility location problems, including stochastic ones, can be found in [2, 3]. Facility location model with quantile criterion was proposed in [4]. The quantile criterion and its convex upper approximation (Conditional Value-at-Risk, CVAR) in stochastic problems of facility location were used in the work [5], in which the problem was solved by reducing it to a mixed integer mathematical programming problem. The CVAR criterion was also used in [6]. In the bilevel competitive location problem, the quantile criterion was used in our previous work [7], a number of ways to obtain estimates for the solution of which is proposed in [8]. A bi-objective generalization of this model was proposed in [9].

In two-stage planning, some decisions are made before the implementation of random factors, while others are made when the implementation of random factors becomes known. In stochastic programming, two-stage problems [10] are used to model such a decisionmaking structure. Two-stage stochastic problems of facility location with a criterion in the form of expectation were proposed in the works [11, 12].

This article proposes a two-stage facility location model with quantile criterion. We propose a setting in which additional optimization is performed according to the reliability level of the quantile criterion. To solve the problem, the method of sample approximations of stochastic programming problems is used [10, 13].

1.    Two-Stage Model of Facility Location with Quantile Criterion

Let us describe a stochastic two-stage model of facility location with quantile criterion.

Denote by I = { 1,...,m } the set of possible locations of facilities, and by J = { 1,..., n } we denote the set of customers.

Assume that the income X ij , j ∈ J , received by the facility i ∈ I from the customer j ∈ J is a random value with realizations denoted by x ij . Let X be a random matrix composed of the values X _ij . The distribution of the matrix X is assumed to be known. Denote realizations of a random matrix X by x. We assume that the random matrix X is given on the probability space ( X , F , P ), where X is a compact set in R ^mxn , F is a complete (with respect to the probability measure P ) σ-algebra of its subsets. For convenience, the space of elementary events is identified with the space of realizations of the random matrix X.

Let a linear order ≻ j be given on the set I, which describes the preferences of the customer j ∈ J. For a given linear order, i ≻ j k means that the customer j chooses the facility i among the two open facilities i ∈ I and k ∈ I .

The decision to open a facility is made in two stages. The realization of random demand becomes known at the second stage, and at the first stage only its distribution is known. Suppose that the vector f = ( f i ), i E I , consists of the known costs of opening of the facilities at the first stage, and the vector g = (g i ), i E I , describes similar costs if the facility is opened at the second stage. Since, at the second stage, the opening of a facility requires a prompt decision-making on the fact of the arising demand, we assume that g i > f i , i ∈ I.

At the first stage, the optimization strategy is the vector u = (ui), i E I, in which ui = 1, if, at the first stage, the facility i E I is opened, and ui = 0, if the i-th facility is not open. The second stage strategy consists of the vector y = (yi), i E I and the matrix Y = (yij), i E I, j E J. If the facility i E I is opened at the second stage, then yi = 1, otherwise yi = 0. The matrix Y describes the assignment of facilities to customers for services. The variable yij shows whether the facility i E I is assigned to serve the customer j E J: yij = 1, if the i-th facility is assigned, and yij = 0, if the i-th facility is not assigned.

The problem of the second stage is solved with the known strategy of the first stage u and the known realization x of the random matrix X :

ф(и,x) =, min. vTu+gTy  52 52 xijУн f ’

(y,Y)GY(u)

i∈I j∈J where Y(u) is the set of pairs (y, Y) E {0,1}m x {0,1}mxn satisfying the constraints

E yij < 1, j E J;

i ∈ I

Ui + yi > yij, i E I, j E J;

ui + yi + ^2 ylj < 1, i E I, j E J- l|i≻j l

In the objective function of problem (1), the first two sums express the costs of opening the facilities at the first stage and the second stage, respectively, and the third sum expresses the income received from customers. This means that at the second stage, the profit taken with the opposite sign is minimized. Constraint (2) forbids the assignment of more than one facility to serve the j -th customer. Constraint (3) allows to assign only facilities opened at the first or second stage to serve the customers. Constraint (4) forbids to open the i -th facility at the second stage, if it was already opened at the first stage. Also, this constraint forbids assigning the facilities that less preferable for the j -th customer than the facility with the number i , if it is opened at the first or second stage, to service the j -th customer.

For each u E { 0,1 } ^m , we can consider the random value Ф(и, X). Define the quantile of the leader objective function:

^ _a (u) — min { ^ E R | Р { Ф(и, x) <  ^ } >  a } ,                   (5)

where a E (0,1] is the given level of reliability. The minimum possible value of the loss function is denoted by ^ o (u) — inf Ф(и,х).

x ∈ X

The two-stage problem of the location of facilities (the problem of the first stage) is formulated as follows:

U * — Arg min ^ a (u), ^a         uG{0,1} ^m

^ a ^{— mi}n A a ^(u). uG{0,1} ^m

2.    Optimization by Reliability Level

Note that, in problem (6), the choice of the reliability level α can lead to significant changes in the structure of the solution. In this regard, a modification of problem (6) is proposed, the purpose of which is to relieve the need to pre-install the level α. To formulate this problem, we introduce the value у = min у0 (u),

• — uG{0,1} ^m

which is equal to the minimum possible loss, and the values у^ = f Tu, which are equal to the maximum losses arising at zero demand for products. Note that the value ya(u) — у characterizes the excess of the minimum possible level by the losses under a favorable scenario guaranteed with the probability α (in this case, the losses are replaced by their upper estimation ya(u)), and the value у^) — у is the expected excess of the minimum possible level by the losses in an unfavorable scenario. To prevent losses in an unfavorable scenario from having a significant effect on the total amount of losses, taking into account the probabilities of favorable and unfavorable scenarios, we require that

^a^ - У) >  (1 - «)№) - у)-                  ⁽⁷⁾

The set of values (u, a) G { 0,1 } ^m x [2 , 1], satisfying constraint (7), we denote by V . The levels for which a <  2 are of no practical interest, and they do not satisfy constraint (7).

Thus, the optimization problem is proposed for consideration:

V * = Arg min y _a (u),                               (8)

(u,a)eV

A * = min y _a ( u ) .

(u,a) EV

Along with constraint (7), we consider the constraint of the form

2⁽ У а ^{( и )} - У) >  ⁽¹ - ^а) ⁽ У - у),                            ⁽⁹⁾

where у = v «1 = E f, i∈I are the maximum possible losses, which appear with the opening of all facilities and zero demand for products. Note that constraint (9) is a strengthening of inequality (7). The set of (u, a) satisfying (9) is an inner approximation of the set described by (7). This follows from the fact that 2(ya(u) — у) < a(ya(u) — у) and у^) < у. It should be noted that constraint (9) is satisfied when a = 1, which means that it describes a non-empty set. The set of pairs (u, a) G {0,1}m x [2, 1] satisfying constraint (9), we denote by W.

Further, along with problem (8), we consider the problem

W * = Arg min у _а (и),                          (10)

(u,a) EW

• 6* = min у _а (u).

(u,a)GW

Problems (8) and (10) are particular cases of the problem

U * = Arg min ^ _a (u), (u,a)eU

A = min ^a(u), (u,a)eU where

U - |(u,a) G { 0,1 } ^m

X 2, ¹ I G ^{( u,a,}^_l

’a^(u)) >  ⁰} ,

for each u G { 0,1 } ^m the function (a, ^) ^ G(u, a, ^) is continuous and non-decreasing in each argument such that

G

(u, 2,A i/2 ^(u2)

< 0,

G(u, 1, ^ 1 (u)) > 0.

3. Construction of Sample Approximations

Let (X ^v ), v G N , be a sequence of independent identically distributed matrices whose distribution coincides with the distribution of the matrix X . We assume that this sequence is defined on some complete probability space (Q, F , P ‘ ). Using the sample (X ₁ ,X ₂ ,... , X N ), we construct an approximation of the quantile function:

'(u) - min{^ G R | PN(u) > a}, where PN(u) is the estimator for P{Ф(u,X) < ^}:

N

P N (u) - NN Ex («»l (Ф^V)),

V = 1

X A ^(a) = ।

1  if a G A;

0  if a G A.

Sample approximation of problem (6) has the form

U N - Arg min A N (u), ^a          ue{a,i} m

N A • AG \ Aa = min ^a ^(u) . ue{a,i}^m

Let us write a sample approximation of problem (11), special cases of which are problems (8) and (10):

U *N ^- Arg min ^ N ^(u), (u,a) EU ^N

where

W A • ЛГ/ \ ^A =, min ^a ^(u) , (u,a) EU ^N

U N - |(u,a) G { 0,1 } ^m X [2, 11 I G(u,a,_V N (u)) >  al.

Note that the function a ^ / _a (u) is piecewise-constant function, which ensures that the minimum in (13) is attainable.

Let us investigate the question of convergence of the constructed sample approximations. The theorem on the convergence of solutions to stochastic programming problems with quantile criterion was proved in [14].

• Theorem 1. Let the following assumptions be fulfilled:

• 1)    the set of feasible values of the variable u is compact and non-empty;

• 2)    the function ( u,x ) ^ Ф(и, x) is continuous in u and measurable in ( u,x ) ;

• 3)    for all e > 0 , there exists a pair ( u, /5) such that

I / - / a i< e, Р { Ф(и,Х) <  / } > a.

Then lim /N = /a P'-almost surely (a.s.), lim D(UN,Ua) = 0 P'-a.s.,

N >ro where

D(UNTO 4 sup inf# ||u - u'^ ueuN u eUa is the deviation of the set UN from the set U*.

It is easy to see that the first two conditions of Theorem 1 are satisfied for problem (6). Condition 3 of Theorem 1 is satisfied, for example, when X = { x G R ^mxn \ x ij G [ a ij , b ij ] } , where a ij <  b ij , and the measure of any open subset of X is positive.

Let us present the conditions for the convergence of sample approximations of problem (11).

Theorem 2. Let X = {x G Rmxn \ xij g [aij,bij]}, where aij < bij, and the measure of any open subset of X is positive. Then lim /N = /* P'-a.s.,                               (14)

lim D (U N , U * ) = 0 P ' -a.s.                           (15)

N ^ro

Proof. As follows from [1, Lemmas 2.1, 2.2], the quantile function a ^ / _a (u) is continuous and non-decreasing, therefore it is possible to define correctly

a ^* ( u )

= min {a G [1, 1^

\ G^(u,a,/ N ^(u)) >  ⁰

I

Moreover, a ^* ( u ) is the only root of the equation

G(u, a, / N (u)) = 0.

Note that, for u G U * , the pair (u-a * (u)) is optimal in problem (8). Let

a ** (u) = max

{a g [I - о

| ^ a (u) = V a * (u)

(u)^ •

By Theorem 1, for all u G {0- 1}m and for all a G [j-1), the following convergence takes place:

lim v N (u) = V _a ( u )  P ’ -a.s.

N→∞

It follows that there exists a set of elementary events Q‘ C Q of probability measure 1, where the convergence takes place lim VN(u) = Va(u)

N→∞ for all u G {0- 1}m, a G [ j-1) П Q.

Let e > 0 be an arbitrary constant. Due to the continuity of v _a (u) by a (and hence to the uniform continuity on any segment in [j-1)) we can choose 5 G (0-e) such that | v _a±5 (u) — V _a (u) l < e. Choose the values a(u) G Q , a(u) G Q such that

a * (u) — 5 <  a(u) < a * (u)-   a ** (u) < a(u) < a ** (u) + 5.

Then, on the set Q ‘ , starting from some number N , for all N > N the following conditions hold:

(u-a(u)) GU ⁿ - ( u-a ( u )) / U ^N -                        (17)

| V Nu) ^{(u) —} V a(u) ^(u) | < ^e-    | V N(u) ^{(u) —} V a(u) ^(u) | < ^e

Let

A N (u) = Arg min { v N (u) | (u-a) G U} . a_G [ 2,1 )

Let a ^N G A N (u). Due to (17), a ^N > a(u). From the continuity of a ^ v _a (u) and convergence of (16), it follows that for sufficiently large N (say, N > N ^′ ) the inequality a ^N < a(u) holds. Then, for N > max(N -N ‘ ),

V N N ^{( u ) —} V a * (u) ^{( u )} <  V N(u) ^{(u) —} V a(u) ^{( u )} <  V N(u) ^{(u) —} V a(u) ^(u) + ^2e <  3^e.

On the other hand,

• V a * (u) ^{(u) —} V N N ^(u) <  V a(u) ^{(u) —} V N(u) ^(u) <  V a(u) + ^{2e —} V N(u) ^{( u )} <  ^3e.

Since ǫ is arbitrary, lim VaNN (u) = Va* (u) (u) N→∞ on the set Q‘ of probability measure 1, which proves the convergence of (14).

Since the set of possible values of u is finite, on the set Q‘ lim vN = lim min vNN (u) = min va*(u)(u) = V*. N^^       N^^ uG{0,1}m a        uG{0,1}m    ( )

Setting sufficiently small e > 0, we obtain that, starting from some number N , for all N > IV и ( u ^N -a ^N ) G U N , there exists a strategy (u * -a * ) G U * such that u * = u ^N , a ^N G (a(u * )-a(u * )), which means that | a ^N — a * | < e. Thus, convergence (15) is true.

----------------------------------------------------------a

Вестник ЮУрГУ. Серия ≪ Математическое моделирование                                  ₁₁

и программирование ≫ (Вестник ЮУрГУ ММП). 2021. Т. 14, № 3. С. 5–17

Therefore, we can formulate a corollary to Theorem 2 on the convergence of sample approximations of problems (8) and (10). Let

V N = Arg min v N (u), ^A N ^ min v N (u), (u,a)EV ^N                     (u,a) EV ^N

W N = Arg min v N (u),   9 ^N = min v N (u),

*         (u,a)EWN                  (u,a)EWN where

V ^N ^ |(u,a) G { 0,1 } ^m x

2,1 1 ^{a (} ^ N cu) - v) >  (i - «^ ( u ) - £)|,

W ^N ^ |(u,a) G { 0,1 } ^m x

П 1

₂, i I      ' (u)

-

v >  2⁽ⁱ - ^(v - v)}.

Corollary 1. Let the conditions of Theorem 2 be satisfied. Then lim AN = A* P’-a.s

N→∞ lim D(VN, V*)=0 P’-a.s.,

N→∞ lim 9N = 9* P’-a.s.,

N→∞ lim D(WN, W*) = 0 P’-a.s.

N→∞

Proof. Problems (8) and (10) are the special cases of (11), therefore Theorem 2 is valid for them.

□4. Solving Approximating Problems

For a fixed realization of the sample (x ¹ ,x ² ,..., x ^N ), sample approximations of the problems under consideration can be considered as stochastic programming problems with a discrete distribution of random parameters concentrated on the set of sampling realizations. This allows to reduce the problems to mixed integer programming problems using the technique described in [13, 15].

Introduce the variables y ^v G { 0,1 } ^m , Y ^v G { 0,1 } ^mxn , v G { 1,..., N } , corresponding to the strategies of the second stage in the realization of the random factors x ^ν , and also the vector of variables 5 G { 0,1 } ^N , in which 5 _V = 1, if for the realization Ф(u,x ^v ) <  v N (u)). Problem (12) is reduced to a mixed integer linear programming problem

V ^             min uEU, VER, (y1 ,Y 1),...,(yN,yN)EY(u), 5g{0,1}n subject to

• fTu + gTyv - ^^xVyvj < v + (1 -5v)(V- v), vG {1,...,N};

i ∈ I j ∈ J

1 ^N

N δ ≥ α.(20)

• ^V V =1

In this case, the optimal value of the variable ϕ is equal to ϕ _α ^N , and the set of optimal values of the variable u coincides with the set U _α ^N .

If the conditions of Theorem 2 are satisfied, then the value ш = minuE{0j1}m Ш0(u) can be found as a solution to the integer linear programming problem ш = min < fTu + gTy — > > Ьцуц > .

- uE{o,i}m,(y,Y)ey(u)V У У к                    iEl jEJ )

To solve problem (13), it is necessary to choose the minimum of the values ^ N (u) that satisfies the constraint

G(u,a,vN (u)) > 0.(21)

Unfortunately, even under constraint (9), the resulting problem is nonconvex. However, we can consider the problem ш ^                min uEU, ^ER, (y1 ,Y1),...,(yN,yN)EY(u), 5e{0,i}n, ae[2,1)

under constraints (19), (20) and

G(u,a,^) > 0.(23)

If the obtained solution to problem (22) has the property that among constraints (19) there exists an active constraint corresponding to 5 _V = 1, i.e.

max v E{ 1,...,N }

|f ^T u+ g ^T y"

-          xiνjyiνj | δν iEl jEJ

= ш,

then the optimal value of the variable ϕ in this problem is equal to the optimal solution ϕ ^N to problem (13).

When approximating problem (8), constraint (23) takes the form

а(ш - ш) > (1 - a)Mu) - ш), while approximating problem (10) constraint (23) takes the form

Ш — ш >  2(1 — а^ш — ш).

Thus, the approximation of problem (10) is carried out by a mixed integer linear programming problem, and the solution to the problem approximating (8) requires the use of nonlinear optimization methods.

If condition (24) is not fulfilled, then we can propose a way to find the upper bound for the optimal solution to problem (13). Let the solutions to problem (18) or several levels а be found, denote them by а ₁ ,..., а _м . Then, among them, choose the minimum a k at which G(u ^k , a k , y N k ) >  0, where u k is the optimal value of the variable u in problem (18). The found solution u = u k , a = a k provides an upper bound for the optimal solution to problem (13). Taking into account the monotonicity of the function G , the proposed procedure can be accelerated by using the dichotomy method.

5.    Numerical Experiment

To illustrate the obtained results, let us consider the problem for the following data: m = 4, n = 3, f = (1, 2, 3,4) ' , g = (7, 8,15,12) ' . Customers’ preferences are as follows: 1 ^ 1 2 ^ 1 3 ^ 1 4, 4 ^ 2 2 G 2 3 ^ 2 1, 3 ^ 3 1 ^ 3 2 ^ 3 4. The random values X ij are independent and distributed uniformly on the segments [0, b ij ]. The values b ij form the matrix

10 8   5

4 4 14

12 10 8   '

2 18 5

Results of solving problem (22) with constraint (25), approximating problem (10), are shown in Table.

Table

Solving approximating problems

N	u N	a N	6 N	Time, seconds	Feasibility
100	(0,0,1, 0)'	0,7261	- 8, 5407	10	+
200	(0,0,1, 0)'	0,7300	- 8, 8600	105	-
300	(0,0,1, 0)'	0,7327	- 9, 0808	313	+
400	(0,0,1,0) '	0,7325	- 8, 9716	1658	+
500	(0,0,1, 0) '	0,7320	- 8, 8900	6789	+

Table shows that the obtained solution for the sample size N >  300 changes insignificantly. The solutions given are ( u ^N ,a ^N ) G W N . In the column “feasibility” of the plus sign means, constraint (24) is satisfied for the resulting solution. Note that, for all N except 200, this restriction is satisfied, which means that the obtained solutions for the given N are optimal in the problem approximating problem (10). The calculations were performed on Intel Core i5-6300U CPU, 2,40GHz, 8Gb RAM. The mixed integer linear programming problem was solved using the Gurobi solver.

The results obtained show the effectiveness of the approach already with the sample size of N = 300. Note that a further increase in the sample size leads to a significant increase in the computational time, which can be seen from Table.

Conclusion

The work proposes a two-stage model for the location of facilities with quantile criterion. We propose approaches to modelling, which optimize not only the value of the quantile, but also the level of reliability. To solve the obtained optimization problems, the method of sample approximations was used. The problem with quantile criterion at a fixed level of reliability is reduced to a mixed integer linear programming problem. For the problem with the choice of reliability, a mathematical programming problem is proposed, which, when the condition (24) is fulfilled, gives the sample approximation solution to the problem. The question of sufficient conditions for the fulfillment of (24) in terms of the original problem requires further study. Numerical experiments show that this condition is fulfilled for many problems. Further research will study not only the issue of convergence of the constructed sample approximations, but also the question of their accuracy, as well as a sufficient sample size for their construction. Numerical experiments show encouraging results in this direction. Due to the difficulty of solving approximating problems for large sample sizes, it is of interest to develop fast (possibly heuristic) methods for solving the problem.

Acknowledgements. The work was funded by RFBR according to the research project No. 19-07-00436.