The Multiple-Square-Root Minimization Problem (MSR) has an objective function that consists of a sum of a linear term and at least two square root terms. The Lagrangian sub-problem for the LMRP (Location Model with Risk Pooling) is a typical MSR problem, and there are other MSR problems in real life. A simple example is that we add other concave costs besides the safety stock cost to the LMRP, such as the labor cost and even minimize the negation of the revenue. Our focus is on the two-square-root problem in which this assumption does not hold. We address this problem along two directions. The first is to relax the assumption in the LMRP’s Lagrangian method and the second one is to add a condition for the parameters that make the sorting method always optimal.
They proposed an efficient algorithm for the continuous relaxation of this sub-problem. The Maximum Expected Covering Location Problem (MEXCLP) is introduced by Daskin   . In 2002  introduced the LMRP (Location Model with Risk Pooling). The original motivation of the model was a study of a Chicago-area blood bank system. Compared with the UFLP model, the LMRP takes cycle stock and safety stock into account. Ozsen  considered the interdependence between capacity and inventory management in the LMRP. The Lagrangian sub-problem is also a non-linear integer program. A couple of special cases of the Multiple-Square-Root Minimization problem are presented by Shen et al.  . So there are two more non-linear terms in the objective function. Then we proposed a Lagrangian method to solve this model for a special case in which the ratio of the demand variance to the demand mean is identical for all retailers. Then in 2003, Shen et al.  presented a different algorithm for solving the LMRP. They reformulated the model into a set covering problem and applied a column generation algorithm to solve it. The computational results show that this algorithm is fast, but still slower than the Lagrangian method. They also discussed the influence of changing the key parameters. The MEXCLP chooses locations of facilities that can sometimes be unavailable and Daskin artfully replaces the none-linear term in the objective function by a sum of linear terms. That linearizes the model and makes it easier to solve. In our thesis, we apply this method to the LMRP problem. They listed problems like which all had at least two concave (square root) terms in the objective function. Shu developed an efficient algorithm to solve this kind of problem in  through a corresponding concave minimization problem defined on a polyhedron. Snyder, Das- kin and Teo  presented a stochastic version of the LMRP problem, and they developed a Lagrangian method for this problem.
In our thesis, we try to find under what condition the sorting algorithm for the LMRP Lagrangian sub-problem can be applied to the general two square root pricing problem.
2. The Location Model
2.1. The Location Model with Risk Pooling
The LMRP model is an extension of the UFLP that considers uncertain demand. Besides the fixed cost of opening locations and the variable transportation cost, it also includes the cost of cycle stock and safety stock. As a result, the LMRP is structured much like the UFLP model, with two extra non-linear terms in the objective function. Despite its concave objective function, the LMRP problem can be solved by Lagrangian relaxation quite efficiently, just like the UFLP, assuming that the ratio of the customer demand rate and the standard deviation of daily demand are constant. We use the following notations:
set of retailers, indexed by i,
set of candidate DC sites, indexed by j,
mean daily demand of retailer i, for each
variance of daily demand of retailer i, for each ,
fixed (daliy) demand of locating a DC at candidate site j, for each ,
fixed cost for DC j to place an order from the supplier, including fixed components of both ordering and transportation costs, for each ,
cost per unit to ship between retailer i and candiddate DC site j, for each and ,
a constant parameter that captures the safety stock costs at candidate sites.
Then the model is formulated as follows.
2.2. Linearization of LMRP
To make the objective function linear, we introduce a new parameter to represent the cost of safety and cycle stock cost that k retailers are assigned to DC j, that is
Also we introduce a new decision variable
To associate with its meaning using linear constraints, we add the constraints
The second constraint says that only one of the can be equal to 1 for each j and the first constraint makes sure that the 1 appears when which is just how we define the meaning of .
So the linear model is:
From these two formulations, we can see although the second method is linear, it has many more constraints than the original formulation. On the other hand, it can be solved by an off the shelf MIP solver and does not require Lagrangian relaxation as in the original LMRP. So it’s hard to say which computation time would be shorter only by looking at the models. We will test randomly generated examples and compare the solution time of the two methods in Chapter 4.
2.3. The Lagrangian Relaxation Method for the LMRP
Similar to the UFLP, we solve the LMRP by relaxing the assignment constraints Equation (3.2) to obtain the following Lagrangian sub-problem:
Although the sub-problem is a concave integer minimization problem, it can be solved relatively efficiently, using a sorting method developed by Mark S. Daskin, Collette R. Coullard, and Zuo-Jun Max Shen in 2003. The algorithm relies on the assumption that the ratio of the demand variance to the demand mean is a constant for all retailers. That is, for all , . Then we can collapse two square root terms into one and apply the sorting algorithm to solve the resulting sub-problem.
The optimal objective function value of the Lagrangian sub-problem gives us a lower bound of the original problem; then we need an upper bound. There are many ways to find a feasible solution to get the upper bound; in this paper, we use a simple algorithm to generate the solution from the sub-problem result.
3. Model Introduction
3.1. LMRP Model
In the LMRP model, the Lagrangian sub-problem can be written as
To solve this sub-problem, we can divide the objective function into three parts. The X part contains , the Y part contain
and the part contains
. Since the part has no decision variables, it can be ignored for the optimization. To minimize the objective function, we decide the value for as follows: for each j, if plus the minimum value of the Y part for that j is negative, we set to 1 and set to achieve the minimum value; else, we set and to 0. Therefore the problem reduces to finding the minimum value for the Y part. For given , let , and . Then the Y part minimization problem can be abstracted into
In “A joint location-inventory model”, an efficient sorting method was introduced to solve this problem under the condition that = constant for all i. This allows the two square-root terms to be combined into one, which is requires for the algorithms in “A joint location-inventory model”. From the original notation, this condition means that the ratio of the demand variance to the demand mean is a constant for all retailers. This is approximately true for many realistic cases. However, in some cases demand variance can be influenced by factors other than the demand mean and that will violate the condition. One example is selling wine; the demand mean is mostly related to the population that drinks the wine while the demand variance can be influenced by the climate. People tend to buy more when the grapes are good because of good climate, so places with stable climate tend to have a lower demand variance.
As we mentioned in the last paragraph, the method in “A joint location-in- ventory model” works under the condition that = constant, let's say , for all i. Now the y part can be rewritten as follows:
We get rid of one of the square root terms in this way. So the minimization problem of the Y terms can be written as:
Mark S. Daskin, Collette R. Coullard, and Zuo-Jun Max Shen proved that (P) can be solved efficiently by a sorting method, in time. The sorting method works as follows:
1. Set for all
2. Set for all such that .
3. Sort the elements in in increasing order of .
4. For each ,compute
(If , then .)
5. Choose the r that minimizes and set for
The proof for this sorting method only uses the concave property of the square root function and the process also works if we replace the square root terms with any concave function terms.
Without the condition that = constant, we cannot combine the two square root terms into one in the Y part. So the sorting method provided by does not work in these cases. Our focus is on identifying conditions under which the problem can be solved by Mark S. Daskin, Collette R. Coullard, and Zuo-Jun Max Shen the sorting method for problems with two or more square root terms.
3.2. Model Formulation
The general form of the multiple square root (MSR) minimization problem is as follows:
Throughout the analysis below, we assume that for all and . In the case of the LMRP, this assumption holds as long as all of the demand variances are positive. If the assumption does not hold, one can approximate it by setting , for small , if it equals 0. Furthermore, we will assume that for all and . This assumption is not restrictive, since if we can multiply the objective function by some constant M without changing the optimal solution; then becomes . For large enough M, all coefficients are greater than or equal to 1.
Let . Obviously, if than in any optimal solution . Assume without loss of generality that the elements of are sorted such that
Consider the two square root problem, i.e., m = 2. As shown in “A joint location-inventory model”, if = constant for all i, then the sorting method dis-
cussed above works. On the other hand, we know that without this constraint, the sorting method does not hold in general. The question we are interested in is whether the sorting method is guaranteed to work if the ratios are “close enough”.
Suppose that , and with for some constants . Our aim is to identify values for and , which guarantee that the sorting method works.
3.3. Model Analysis
In this section, we modify the proof of the correctness of the sorting method introduced by Mark S. Daskin, Collette R. Coullard, and Zuo-Jun Max Shen to the MSR problem and discuss the bottleneck of the proof.
We assume without loss of generality that the elements of are indexed and sorted such that
Conjecture 2.1 There exists an optimal solution to (PP) such that the following property holds: if for some , then for all .
Start of Proof: Let be an optimal solution to (PP). Assume (for a contradiction) that but for some . Assume that is the optimal solution with the greatest number of components set to 1. We will find a new optimal solution with one more
Component set to one, thus contradicting our assumption.
Let be the objective values corresponding to , respectively. Let , and let . Clearly,
Then from Equation (2.5), we have:
Also, from Equation (2.6), we have:
if we can identify a condition such that
Then conjecture 2.1 would be proved.
From the convexity of the square root function, we have
It is sufficient to find a condition that makes
An instance that satisfies inequality (2.13) must satisfy (2.11). Since by the way is sorted.
Here comes the bottleneck, since inequality (2.13) doesn’t hold for all cases. In Section 2.4 we give a sufficient condition that ensures inequality (2.13) holds, and in Section 2.5 we try an alternate approach.
3.4. A sufficient Condition
As we assumed in Section 5.2, and with . So we change the format of inequality (5.13) and associate it with our assumption.
First note that
Given the assumption, we have:
Since all the terms are greater than zero, we have:
Simplifying the right hand side term, we have:
Combining (5.14), (5.15) and (5.16), we have:
This holds for any . Summing over t, we get :
Given the assumption, we also have:
Since all the terms are positive.
Similarly we have
Given the assumption, we have:
Since all the terms are greater than zero, we have:
Simplifying the right hand side term, we have:
Combining (2.20), (2.21) and (2.22), we have:
This holds for any . Summing over t, we get:
Given the assumption, we also have:
since all the terms are positive, inequality (2.23) and (2.24) imply
From inequalities (2.19) and (2.25), we can see that if we have
then inequality (2.13) will hold. In other word, Conjecture (5.1) holds if we impose (5.16) as an additional condition.
Inequality (2.26) can be reformulated as
For the right hand side of inequality (2.27), needing the minimum value of .
Over all k, l, call it , is easy to accomplish through a simple iterative procedure.
Step 1: Let .
Step 2: Let .
For the left hand side of inequality (2.17), the value is decided by and
the smallest value of this fraction can also be determined from the dataset easily. Given our assumption in Section 2.2, the smallest value of should be the largest ratio of and , for all and ; call it . Also, the largest value of should be the smallest ratio of and , for all and ; call it .So
As a result, in a given dataset, if we have then inequality (2.27)
holds for all k, l, and so inequality (2.13) holds. In this case conjecture (2.1) holds, and the sorting method can be applied to the data set.
The following theorem summaries our analysis:
Theorem 2.4.1. If a data set has the property that , then there ex-
ists an optimal solution y to (PP) such that the following property holds: if for some , then for all .
If the condition in Theorem (5.4.1) holds, then the sorting method can be applied.
3.5. An Alternate Analytical Approach
There is another direction for needing the condition. Continuing the logic from the Section 2.3, let’s start from the simplest case, the two square root case.
First we subtract the left hand side from the right hand side of inequality (2.13);
The denominator is larger than zero as ck and cl are larger than zero. For the numerator, we need to compare.
We need to compare
From here we can see that if we do not add a condition on the relation between and .
The difference between the previous terms can be either positive or negative. So we first add the simple condition that .
So the problem changes to comparing
As these terms are all positive, we can square them without changing their magnitude relation.
The left hand side becomes
The right hand side becomes
which can be written as the same pattern as the left hand side,
The difference between these two sides is
This term’s value is near 0 but can be positive or negative for different data sets. We tried to add some conditions to make this term always negative, but no sufficient condition was found.
However, if we only impose the simple condition that, the sorting method often finds the optimal solution, and when it does not, the error is usually small. This will be shown in the next section.
3.6. A Lower Bound Based on the Sufficient Condition
As we discussed in Theorem 2.4.1, if a data set has the property that ,
then there exists an optimal solution to (PP) such that the following property holds: if for some , then for all .
From the Theorem we can see that in a data set, the will of will de-
cide whether this data set holds the property. Let's name this number as R. So when , the property holds and the sorting method can be applied to this data set. In this section, we discuss a method to get a lower bound through the sorting method when and the gap between the lower bound and optimal solution.
Conjecture 2.2: There exists a lower bound to (PP) such that is the objective value of a feasible solution that the following property holds: if for some , then for all .
Start of Proof: Let be an optimal solution to (PP) and is its objective value. Assume (for a contradiction) that but for some and . We will find a feasible solution with the following property: if for some , then for all that breaks the inequality, thus contradicting our assumption.
as we have
From the Assumption,
From Equation (2.28) we have
Also, we have Equation (2.8)
Based on the way we sort the data,
According to Inequalities (2.19), (2.25), and (2.26), we can imply that,
Combining Inequalities (2.32) and (2.33) we have,
From Inequality (2.29),
There exists a contradiction in inequalities (2.34), (2.35) and (2.36). As a result, Conjecture 2.2 is proved.
3.7. Test on Random Samples
We generate the parameters in our random samples using uniformly distributed random numbers. was generated from and all were generated from and we choose and . There are 600 instances in total. We get the optimal value of the sample instances by enumerating each of the feasible solutions and choosing the ones with the smallest objective value. Then we apply the sorting method to the same instance and compare the result with the enumeration method. Both methods were implemented in MATLAB.
We can see that in most of the two square root cases, 94 out of 100, the sorting methoded the optimal solution. In these samples, 42 instances satisfy the sufficient condition (2.17) and for each of these instances, the sorting method finds the optimal solution, as predicted by Theorem (5.4.1). In the three square root cases, the sorting method works in 73 out of 100 data sets and 15 of them meet condition (2.17). When there are four square root terms, the sorting method works in 56 out of 100 data sets, and there are only 6 cases that meet condition (2.17). The results are shown in Table 1. This shows that the sufficient condition is correct, but not many data sets satisfy it. However, this condition allows slight changes in the ratio of the multiple-square-root parameters, which is typical of realistic data sets. For further research, relaxing the condition so that it applies to more realistic data sets can be a direction.
For the alternate analytical approach in Section 2.5; the accuracy rates are shown in Table 2. We can see that as the complexity of the problem goes up
Table 1. Satisfaction rate for the sufficient condition.
Table 2. Accuracy rate for the alternate analytical approach.
with more square roots, the accuracy rate goes down. However, the rates are acceptable when the number of square roots is not large. For future research, we will search for additional sufficient conditions to guarantee the optimality of the sorting method.
4. Conclusions and Future Research
As for the MSR problem, we discuss a sufficient condition that guarantees the sorting method works, and an alternate analytical approach that makes the sorting method often needs the optimal solution while the average error is low.
For future research, we would like to determine the conditions under which the linearization method will have a shorter solution time than the Lagrangian method does. Searching for relatively relaxed sufficient conditions to guarantee that the sorting method works for the MSR problem is also a direction.