Storage Location Problem: Properties and Computational Aspects

Abstract

Nonlinear programming problem for optimal location of storages is studied so that the total distance, taken into account with coefficients, which are the volumes of products transported from storages to markets (consumers), is minimal. It is shown that the objective function of the problem satisfies a special inequality and, in general case, is a non-smooth nonconvex function. The consistency conditions of linear constraints system of the problem and its variants depending on balance conditions that define degeneracy and non-degeneracy of the constraints system are substantiated. An example of the problem is given when the solver MINOS 5.51 does not obtain a solution to a degenerate problem and obtains a solution to a non-degenerate problem. Work of NEOS server solvers for solving the storage location problem depending on the starting point and degree of degeneracy of the system is studied.

-

problem, transportation problem, nonlinear programming problem, degeneracy of linear constraints system, software, NEOS server, AMPL, MINOS

1. Introduction

Objects location problem belongs to problems of transport and production type and quite often arises in practice in such areas as health care, waste management system, logistics and transportation of products from producers to consumers (or intermediaries with further transportation to consumers), etc. A large number of publications are devoted to theoretical, computational and applied aspects of this problem. In particular, works [1–3] discuss concepts, models, and algorithms for solving facility location problems, works [4, 5] offer new approaches to their solving. The work [6] examines the optimization problems of production and transport type, as well as methods and algorithms for their solving. The work [7] is devoted to solving the problem of m-travelers and nonlinear programming problem using NEOS server solvers. The work [8] considers so called multi-level facility location problems, which extend some classical facility location problems.

Object location problem is closely related to centroid-based clustering problems so that the optimal solution of the first problem corresponds to a certain partition of a set of points into classes, i.e. solution of a clustering problem. In the general formulation, the object location problem is NP-hard, but it can be reduced to other types of problems, in particular to set cover problem [9].

As a partial case of the object location problem, the storage location problem formulated in the book [10, section 14.2, pp. 370–371] can be considered. In this problem, it is needed to choose the optimal coordinates for the storages locations for markets, where the total distance, weighted by the volumes of products that need to be transported to markets (consumers), is minimized. Here, the coordinates of the storages location are not chosen from the set of potential locations of the storages, but can have arbitrary coordinates on the plane.

The material of the article is presented in the following order. In the second section, the formulation of the nonlinear programming problem for the optimal storage location is given. The third section examines the properties of the objective function of this problem and shows that its solution

2023 Copyright for this paper by its authors. may not be unique. The fourth section substantiates the consistency conditions of the constraints system of the problem and gives an example of a problem that the MINOS solver solves in degenerate case, but does not solve in non-degenerate case, determined by the balance conditions of the constraints system of the problem. The fifth chapter deals with nonlinear programming problem for optimal storage location with equality constraints. It is shown that one arbitrary linear constraint is linearly dependent. An example of solving degenerate and non-degenerate variants of the problem, which are determined by the presence or absence of one linearly dependent constraint, using NEOS server solvers is given. The sixth chapter examines the problem of location 5 storages for transporting products to 19 the most common markets of Kyiv and examines the work of NEOS server solvers depending on the starting point and the degeneracy degree of the constraints system.

2. Storage location problem formulation [9]

Let the locations of

markets (consumers) and the volume of demand on each of them be given.

The demand can be satisfied from

storages with given capacities. It is needed to locate these storages so that the total distance, calculated with weighting coefficients equal to the volumes of products transported from storages to markets, is minimal. It is important to emphasize, that in practice such a criterion for solution evaluation is the ton-kilometer indicator.

– known capacity of -th storage ( = ̅1̅̅,̅̅̅); Let us build a model of the problem. The notation is the following: ( , )– unknown coordinated of -th storage ( = 1̅̅̅,̅̅̅); – known volume of -th market ( = ̅1̅̅,̅̅); ( , ) – known coordinates of -th market (consumer) ( = ̅1̅̅,̅̅); 2

2 = √( − ) + ( − ) – distance from -th storage to -th market ( = ̅1̅̅,̅̅̅, = ̅1̅̅,̅̅); – volume of products, transported from -th storage to -th market ( = 1̅̅̅,̅̅̅, = ̅1̅̅,̅̅). Then the m storage location problem and determination of products volumes to be transported from storages to markets is formulated as follows: subject to

∑ ≤ , = ̅1̅̅,̅̅̅,

The problem ( 1 ) – ( 4 ) is nonlinear programming problem, for the objective function ( , , ) is nonlinear and non-smooth. Here variables are coordinates of storages ( , ) and transportation volumes . If storages locations are known, then distances are known, and only transportation volumes are to be determined. In this case the problem ( 1 ) – ( 4 ) is opened transportation problem.

3. Properties of objective function of the problem (1) – (4)

For the storage location problem, the objective function ( 1 ), depending on ( + 2) continuous variables, is non-smooth nonlinear function and has the following property.

Lemma 1. For the function ( , , ) = ∑ =1 ∑ =1 √( − ) + ( − )2 and arbitrary 2 ∈ [0,1] the following inequality is true: ( 1 ) ( 2 ) ( 3 ) ( 4 )

=1 =1 =1 =1 ≤ ∑ Opening brackets in the right-hand side of the inequality ( 6 ) and grouping terms, we get: ∑( 1 + (1 − ) 2 )( √( 1 − )2 + ( 1 − )2 + (1 − )√( 2 − )2 + ( 2 − )2) = = ∑

∑( 2 1 √( 1 − )2 + ( 1 − )2 + (1 − ) 1 √( 2 − )2 + ( 2 − )2 + + (1 − ) 2 √( 1 − )2 + ( 1 − )2 + (1 − )2 2 √( 2 − )2 + ( 2 − )2) = = ∑ ∑(( − + 2) 1 √( 1 − )2 + ( 1 − )2 + (1 − ) 1 √( 2 − )2 + ( 2 − )2 + + (1 − ) 2 √( 1 − )2 + ( 1 − )2 + ((1 − )− (1 − )+ +(1 − )2) 2 √( 2 − )2 + ( 2 − )2) = ∑

∑ 1 √( 1 − )2 + ( 1 − )2 + +(1 − ) 2 √( 2 − )2 + ( 2 − )2 + ( − 1) 1 √( 1 − )2 + ( 1 − )2 + + (1 − ) 1 √( 2 − )2 + ( 2 − )2 + (1 − ) 2 √( 1 − )2 + ( 1 − )2 − + ( − 1) 2 √( 2 − )2 + ( 2 − )2 = ∑

∑ 1 √( 1 − )2 + ( 1 − )2 +

+(1 − ) 2 √( 2 − )2 + ( 2 − )2 − (1 − )× − 2 √( 1 − )2 + ( 1 − )

2 + 2 √( 2 − )2 + ( 2 − )2) = = ∑

∑ ( , , )+ (1 − ) ( , , )+ + ( − 1)(√( 1 − ) + ( 1 − )2 − √( 2 − )2 + ( 2 − )2)( 1 − 2 ),

2 from which we get that the inequality ( 5 ) is fulfilled.

In general case, the function ( 1 ) is not convex, and the problem ( 1 ) – ( 4 ) is multiextremal. However, there are partial cases in which the function ( 1 ) may be convex if the last term of the righthand side of the inequality ( 5 ) is negative. For this problem, this condition means that, considering two sets of possible storage locations (two supplier firms), for each “storage – market” pair, the first supplier firm either transports a larger volume of products over a shorter distance, or transports a smaller volume of goods, covering a greater distance than the second supplier firm.

It is easy to demonstrate that in general case the solution of the problem ( 1 ) – ( 4 ) is not unique. Let us consider the problem ( 1 ) – ( 4 ) with = 1 and = 2, i.e. there are 2 markets with coordinates (0,0) and ( 10,0 ). Each market requires the same number of units of the product, for example 10 units. It is needed to choose the location of one storage for transporting products to these two markets (see Fig. 1).

4. Properties of the constraints system of the problem (1) – (4)

Linear constraints system ( 2 ) – ( 4 ) depends on variables only and is typical for opened transportation problems with

suppliers (storages) and consistency of the system the following criterion ca be used. Lemma 2. Constraints system ( 2 ) – ( 4 ) is consistent if and only if ∑

Proof. Necessity. Let there exist non-negative ( ̅, ̅ ) and ̅ , ( = ̅1̅̅,̅̅̅, = ̅1̅̅,̅̅) that satisfy the constraints system ( 2 ) – ( 4 ), i.e. the following equalities and inequalities are true: consumers (markets). To clarify the Summing the inequality ( 8 ) with index = ̅1̅̅,̅̅̅ and equality ( 9 ) with index = ̅1̅̅,̅̅, we get:

The same value of the objective function ( 1 ) for two different points of storage location shows that the solution of the problem can be not unique.

However, if we remove the square root in the second multiplier under the sum sign in the function ( , , ), i.e., instead of Euclidean distance (norm) we use norm squared, the function will be as follows: The function ( 7 ) is smooth and non-convex function. For = 1 and = 2 the solution of the problem ( 7 ), ( 2 ) – ( 4 ) is unique.

Using the inequality ( 11 ) and equality ( 12 ), and changing indices order, we get the following inequalities chain:

, ̃ ) are arbitrary. Let us show that these variables satisfy constraints ( 2 ) – ( 4 ).

= ∙ ≤ , = ̅1̅̅,̅̅̅, ∑ =1 =1

∑ =1 =1

∑ = , = ̅1̅̅,̅̅. ≥ 0, since ≥ 0, ≥ 0, = 1̅̅̅,̅̅̅, = ̅1̅̅,̅̅. The magnitude ∑ =1 > 0 by assumption, i.e., total capacity of all the storages is non-zero.

Hence, the system ( 2 ) – ( 4 ) has the feasible point ( 14 ), so it is consistent.

If the inequality constraints ( 2 ) of the problem ( 1 ) – ( 4 ) are transformed into equality constraints by introducing additional variables, then the constraints system ( 2 ) – ( 4 ) is non-degenerate. However, if the equality ∑ =1 =

∑ =1 holds, then the coefficients matrix of the basis variables is not degenerate, but it may contain zero coefficients for additional variables. Such a situation can impair work of methods based on using basis matrix, for example, the simplex method. If the inequality ∑ =1 >

∑ =1 holds, this situation is unlikely since basis variables coefficients are non-zero. Therefore, in order to improve performance of methods, which are working with basis matrix, it is advisable to ensure that the condition consider the following example.

∑

=1 > ∑ =1 is fulfilled. To demonstrate this effect, let us Example 1. Let us consider the problem ( 1 ) – ( 4 ) with = 4 and = 24, i.e. there are 4 storages and 24 markets. Each market needs 10 units of products, each storage contains 40 units of products. The location of the markets with the specified coordinates is shown in Figure 2 (marked in blue). For such a problem, there is an analytical solution, according to which the optimal locations of the storages have the following coordinates:

( ∗, ∗) = ((50,50), (50,250), (50,450),(250,50), (250,250), (250,450)), marked with orange crosses in Figure 2. Optimal value of the function ∗( ∗, ∗, ∗)for such a configuration of the problem equals 16970,6.

To solve the problem the MINOS 5.51 solver [11] from NEOS server [12] is used. To formulate the problem the AMPL language [13] is used. The initial data are as follows: = 40, = 1̅̅̅,̅̅̅, = 10, = ̅1̅̅,̅̅. The starting point ( 0, 0, 0) for the MINOS solver is obtained using pseudorandom number generator. The problem is solved in two variants: when the condition ∑

=1 = ∑ =1 is fulfilled and the condition

∑ =1 > ∑ =1 is true. In the first case = 40, = ̅1̅̅,̅̅̅, in the second

inequality case – = 40.4, = ̅1̅̅,̅̅̅, i.e., each storage capacities are increased in 1 % to ensure that the ∑ =1 >

∑ =1 is fulfilled. The results of problem solving using the MINOS 5.51 solver are given in Table 1. Here ̂∗( , , ) is the objective function value, obtained with the solver, Δ =

5. Modification of the problem (1) – (4) for equality constraints

Similarly to closed transportation problems the problem ( 1 ) – ( 4 ) can be reformulated using equality constraints: ∑ = , = ̅1̅̅,̅̅̅, problem (15) – (18) the following lemma is true.

Lemma 3. Constraints system (16) – (18) contains + − 1 linear independent equations.

Proof. The statement of the lemma is proved in the book [14, p. 198].

Degeneracy of the system (16) – (18) can significantly affect the process of solving the problem (15) – (18) using simplex-type methods, which are based on transition from one basis matrix to another. To overcome the degeneracy of the system (16) – (18), it is advisable to exclude one arbitrary linearly dependent constraint from it. The choice of such a constraint will affect the convergence rate of the method. Let us demonstrate it with the following example.

Example 2. Let us consider the problem (15) – (18) for = 3, = 12. Markets locations with known coordinates are given in Figure 3 (marked in blue). (15) (16) (17) (18) using pseudorandom number generator.

We will solve the problem with different options for extracting one linearly dependent constraint for storages from the constraints system of the problem. For this, we will build four problems. Problem A is the problem (15) – (18). Problems B, C, and D are the problem A, with the first, second, and third constraints removed from the constraints group (16) respectively.

Storage capacities and demand of each market are selected similarly to the previous example, i.e. = 40, = 1̅̅̅,̅̅̅, = 10, = ̅1̅̅,̅̅. For such input data of the problem, the optimal location of the storages is shown in Figure 3 (marked with orange crosses). Herewith, the optimal value of the objective function ∗( ∗, ∗, ∗) = 8485,28. The starting point ( 0, 0, 0 ) for solvers is obtained

Results of the MINOS solver work for the problems А, В, С, D are given in Table 2. Here iter is the number of iteration performed be the solver; obj is the number of the objective function value calculations; grad is the number of gradient calculations; = ( ̂ ∗( , , )− ∗( ∗, ∗, ∗))/ ∗( ∗, ∗, ∗) is relative error of the objective function value for the solution obtained by the solver; time is the time of solving the problem by the solver in seconds.

Results of solving the problems А, B, C, D using the MINOS 5.51 solver

iter obj grad

Solving time (sec)

Problem А

Problem B

Problem C

Problem D 47 45 44 46 40 39 33 24 23 41 42 41 8.36043e-15 largest error is achieved in problem C and is 10−14. MINOS spent the most computational resources on solving the degenerate problem, namely 47 iterations, 45 calculations of the objective function values, and 44 calculations of its gradient. For all non-degenerate problems, MINOS consumed less computational resources. The best result is achieved when solving problem C: 33 iterations, 24 calculations of the objective function value, and 23 calculations of the gradient. Let us solve problems А, B, C, D using the following list of solvers from the “Nonlinearly Constrained Optimization” section on NEOS server: Knitro 13.2.0, SNOPT 7.6.1, CONOPT 3.17A, LANCELOT, filterSQP (20020316), Ipopt 3.14.12, LOQO 7.00, OCTERACT Engine 4.4.0. Relative errors of the objective function value for the solution obtained by the solvers are given in Table 3. Table 3 results show that only Knitro, SNOPT, filter, Ipopt, and LOQO solvers successfully solved all problems, and filter shows the smallest relative error Δ among them. The filter solver is the only solver from the list that showed better accuracy than MINOS (see Table 2). When solving the degenerate problem A, Knitro printed messages suffix feaserror OUT; suffix opterror OUT; suffix numfcevals OUT; suffix numiters OUT, and Ipopt printed messages suffix ipopt_zU_out OUT; suffix ipopt_zL_out OUT. Such messages indicate problems related to degeneracy of the problem constraint system.

CONOPT and LANCELOT solvers were able to solve only problem D and problem C, respectively. This demonstrates expediency of excluding one linearly dependent constraint to overcome degeneracy of the problem. When solving problems A, B and D using LANCELOT, the maximum number of iterations (1000 iterations) was exceeded, so no solution was found. When solving problems A, B, CONOPT displayed message Evaluation error limit; 2 failed evaluations, which indicates problems with evaluating the value of the objective function. OCTERACT could not solve the problem in 5 minutes, so it was not included in the table.

Illis

Shpalernyi

Borshchahivskyi

Rechovyi

Stolychnyi

Sevastopolskyi

Kurenivskyi

Solomianskyi

Lukianivskyi

Hurtovyi (18,81) (21,74) (22,71) (26,79) (33,56) (37,69) (38,93) (42,68) (42,81) (43,75) # 11 12 13 14 15 16 17 18 19

Zhytnii

Hospodarskyi

Volodymyrskyi

Bessarabskyi

Ovochevyi

Troieshchynskyi

Pecherskyi

Lisovyi

Darnytskyi (46,82) (46,88) (46,67) (48,75) (64,79) (63,92) (52,72) (69,81) (71,71)

6. Computational experiment for the problem (1) – (4):

= , =

Example 3. Let us consider the problem ( 1 ) – ( 4 ) for location 5 storages for products transportation to 19 the most common markets in Kyiv (see Figure 4). For this, on the map of Kyiv with its surroundings a coordinate grid is superimposed containing 120 squares of size 10 × 10 with a maximum coordinate of 100 along the abscissa axis and 120 along the ordinate axis. The origin of the coordinates is in the lower left corner. Markets coordinates were determined visually using the grid constructed. Table 4 shows names and coordinates of 19 markets obtained under this scheme.

Storages capacities and demand of each market are chosen similarly to the previous examples 1 and 2, i.e., = 40, = ̅1̅,̅5̅, = 10, = ̅1̅,̅1̅̅9̅. Starting storages coordinates ( 0, 0) are determined visually. Starting products volumes for transportation 0 are obtained using a pseudorandom number generator on the interval [0,20]. For the input data objective function value equals 19218.92 and the inequality ∑

=1 > ∑ =1 is fulfilled, since ∑ =1 40 = 200 > ∑1=91 10 = 190, so the problem is

5 non-degenerate.

To solve the problem, NEOS server solvers from the “Nonlinearly Constrained Optimization” section with default parameters were used. Only the filter and Knitro solvers successfully solved the problem, while the solutions and the value of ̂∗( , , ) for both solvers coincide and are equal to 1015.9. All other solvers did not solve the problem and displayed messages indicating problems with solving the problem. In particular, CONOPT displayed the message Evaluation Error Limit, 2 failed evaluations, and Ipopt displayed message Invalid number in NLP function or derivative detected. suffix ipopt_zU_out OUT; suffix ipopt_zL_out OUT. yellow), and locations of storages obtained using the filter and Knitro solvers (marked in black). problem using filter and Knitro, three storages are located in the central cluster and one each in the western and eastern clusters. Figure 4 allows you to visually assess the connection between storage location problem and centroid-based clustering problem.

To test dependence of solvers work on choice of starting point, the problem was solved using filter and Knitro solvers with 5 different starting points obtained using a pseudorandom number generator. The results of filter and Knitro work for this case are shown in Table 5.

The first line of Table 5 shows the number of the starting point, the second and fourth lines show value of the objective function of the problem obtained by filter and Knitro, respectively, and the third and fifth lines show the number of iterations required by filter and Knitro, respectively. The sixth starting point was used in the previous calculation and is given above.

The results show that in 5 runs from different starting points, the filter and Knitro could not obtain a smaller value of the objective function than the value obtained by the solvers starting from the above point #6.

The solvers obtained the highest value of the objective function when starting from the starting point #2, and filter performed 84 iterations, Knitro – 39 iterations. Starting from the starting point #6, filter and Knitro performed 58 and 77 iterations, respectively, obtaining the same value of the objective function equal to 1015.9. This effect can be explained by the close connection of the storage location problem with centroid-based clustering problems, the objective functions of which are multiextreme, and the solutions of the problem are its local minima.

7. Conclusions.

The article investigates nonlinear programming problem for the optimal location of storages so that the total distance, calculated with weighting coefficients equal to the volumes of products transported from storages to markets, is minimal. It is shown that the objective function of the problem in general case is a non-smooth non-convex function, and the solution of the problem is nonunique. The consistency conditions of the constraints system of this problem are substantiated and its options are considered depending on the balance conditions that determine degeneracy and nondegeneracy of constraints system. The statement of Lemma 1 can serve as a tool for choosing a starting point. Research in this direction is currently underway.

Three examples of solving the storage location problem using NEOS server solvers from the “Nonlinearly Constrained Optimization” section are considered. The first example shows that the MINOS solver does not solve a problem with a degenerate constraint system of the problem defined by the balance condition and solves a problem with a non-degenerate constraint system. The second example shows that exclusion of one arbitrary linearly dependent constraint from the problem constraint system allows it to be solved faster than a degenerate problem. The third example is related to the optimal location of 5 storages for products transportation to 19 the most common markets in Kyiv. The results of solving this problem by solvers filter and Knitro show that the solution they found depends on the choice of the starting point.

8. Acknowledgements.

The authors are pleased to acknowledge the support by the Volkswagen Foundation under grant number 97 775 and by the project of research works of young scientists №07-02/03-2023/ВМ 120.34.

9. Reference

References

[1] R. Zanjirani Farahani , M. Hekmatfar , Facility Location: Concepts , Models, Algorithms and Case Studies , Springe-Verlag Berlin Heidelberg, 2009 .

[2] R. Zanjirani Farahani , M. Hekmatfar , B. Fahimnia , N. Kazemzadeh , Hierarchical Facility Location Problem: Models, Classifications, Techniques, and Applications , Computers & Industrial Engineering 68 ( 2014 ) 104 - 117 .

[3] Z. Drezner , H.W. Hamacher , Facility Location: Application and Theory , Berlin, Springer, 2001 .

[4] L.-Y. Wu , X.-S. Zhang , J.-L. Zhang, Capacitated Facility Location Problem with General Setup Cost, Computers & Operations Research 33.5 ( 2006 ) 1226 - 1241 .

[5] K. Jain , M. Mahdian , A. Saberi , A new greedy approach for facility location problems in Proceedings of the thirty-fourth annual ACM symposium on Theory of computing ( STOC '02) ( 2002 ), Association for Computing Machinery , New York, USA.

[6] V.S. Mikhalevych , V.A. Trubin , N.Z. Shor , Optimization problems of production and transport planning: Models, methods and algorithms , Nauka, 1986 .

[7] G.D. Bila , O.O. Korchynsky , P.I. Stetsyuk , O.M. Khomiak , S.B. Shekhovtsov , Using NEOS server for solving two classes of optimization problems , Cybernetics and Computer Technologies 4 ( 2022 ) 56 - 81 .

[8] C. Ortiz-Astorquiza , I. Contreras, G. Laporte, Multi-level facility location problems , European Journal of Operational Research 267 : 3 ( 2018 ) 791 - 805 .

[9] E.M. Kiseleva , N.Z. Shor , Continuous problems of optimal set partition: theory, algorithms , applications, Naukova dumka, 2005 .

[10] A.F. Gametsky. D.I Solomon , Operational Research, Part II , Academy of Economical Knowledge of Moldova, Academy of Transport, Informatics and Communications, Evrica, 2008 .

[11] MINOS. https://neos-server.org/neos/solvers/nco:MINOS/AMPL.html

[12] NEOS Solver . https://neos-server.org/

[13] AMPL - Optimizing the World's Most Complex Tasks . https://ampl.com/

[14] A.F. Gametsky. D.I Solomon , Operational Research, Part I , Academy of Economical Knowledge of Moldova, Academy of Transport, Informatics and Communications, Evrica, 2004 .