1. Introduction

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 [1] [2] . In 2002 [3] 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 [4] 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. [5] . 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. [6] 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 [7] through a corresponding concave minimization problem defined on a polyhedron. Snyder, Das- kin and Teo [8] 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:

Parameters:

$I$ set of retailers, indexed by i,

$J$ set of candidate DC sites, indexed by j,

$u_i$ mean daily demand of retailer i, for each $i\in I$

${\sigma }_i^2$ variance of daily demand of retailer i, for each $i\in I$ ,

$f_j$ fixed (daliy) demand of locating a DC at candidate site j, for each $j\in J$ ,

$K_j$ fixed cost for DC j to place an order from the supplier, including fixed components of both ordering and transportation costs, for each $j\in J$ ,

$d_{ij}$ cost per unit to ship between retailer i and candiddate DC site j, for each $i\in I$ and $j\in J$ ,

$\theta$ a constant parameter that captures the safety stock costs at candidate sites.

Decision Variables:

$X_j=\{\begin{array}{l}1\text{ifwelocateatcandidatesite}j\\ 0\text{if}\text{not}\end{array}$

$Y_{ij}=\{\begin{array}{l}\text{1}\text{ifdemandsatretailer}i\text{areassignedtoaDCatcandidatesite}j\\ 0\text{ifnot}\end{array}$

Then the model is formulated as follows.

$\text{Minimize}\underset{j\in J}{{\displaystyle \sum }}\left\{f_j{X}_j+\underset{i\in I}{{\displaystyle \sum }}{d}_{ij}{Y}_{ij}+K_j\sqrt{\underset{i\in I}{{\displaystyle \sum }}{u}_i{Y}_{ij}}+\theta \sqrt{\underset{i\in I}{{\displaystyle \sum }}{\sigma }_i^2{Y}_{ij}}\right\}$

$\text{subjectto}\underset{j\in J}{{\displaystyle \sum }}{Y}_{ij}=1,\forall i\in I$

$Y_{ij}\le X_j,\forall i\in I,\forall j\in J$

$X_j\in \left\{0,1\right\},\forall j\in J$

$Y_{ij}\in \left\{0,1\right\},\forall i\in I,\forall j\in J.$

2.2. Linearization of LMRP

To make the objective function linear, we introduce a new parameter ${\gamma }_{jk}$ to represent the cost of safety and cycle stock cost that k retailers are assigned to DC j, that is

${\gamma }_{jk}=K_j\sqrt{ku}+\theta \sqrt{k{\sigma }^2}$

Also we introduce a new decision variable

$Z_{jk}=\{\begin{array}{l}1,\text{ifexactly}k\text{retailersareassignedtoDC}j,\\ 0,\text{if}\text{not}\end{array}$

To associate $Z_{jk}$ with its meaning using linear constraints, we add the constraints

$\underset{k=0}{\overset{\left|I\right|}{{\displaystyle \sum }}}k{Z}_{jk}=\underset{i\in I}{{\displaystyle \sum }}{Y}_{ij},\forall j\in J$

$\underset{k=0}{\overset{\left|I\right|}{{\displaystyle \sum }}}{Z}_{jk}=1,\forall j\in J$

The second constraint says that only one of the $Z_{jk}$ can be equal to 1 for each j and the first constraint makes sure that the 1 appears when $k={\displaystyle {\sum }_{i\in I}{Y}_{ij}}$ which is just how we define the meaning of $Z_{jk}$ .

So the linear model is:

$\text{Minimize}\underset{j\in J}{{\displaystyle \sum }}\left\{f_j{X}_j+\underset{i\in I}{{\displaystyle \sum }}{d}_{ij}{Y}_{ij}+\underset{k\in J}{{\displaystyle \sum }}{\gamma }_{jk}{Z}_{jk}\right\}$

$\text{subject}\text{to}\underset{j\in J}{{\displaystyle \sum }}{Y}_{ij}=1,\forall i\in I$

$Y_{ij}\le X_j,\forall i\in I,\forall j\in J$

$\underset{k=0}{\overset{\left|I\right|}{{\displaystyle \sum }}}k{Z}_{jk}=\underset{i\in I}{{\displaystyle \sum }}{Y}_{ij},\forall j\in J$

$\underset{k=0}{\overset{\left|I\right|}{{\displaystyle \sum }}}{Z}_{jk}=1,\forall j\in J$

$X_j\in \left\{0,1\right\},\forall j\in J$

$Y_{ij}\in \left\{0,1\right\},\forall i\in I,\forall j\in J$

$Z_{jk}\in \left\{0,1\right\},\forall j\in J,\forall k=0,\cdots ,I$

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:

$\begin{array}{l}\text{Minimize}\underset{j\in J}{{\displaystyle \sum }}\left\{f_j{X}_j+\underset{i\in I}{{\displaystyle \sum }}{d}_{ij}{Y}_{ij}+K_j\sqrt{\underset{i\in I}{{\displaystyle \sum }}{u}_i{Y}_{ij}}+\theta \sqrt{\underset{i\in I}{{\displaystyle \sum }}{\sigma }_i^2{Y}_{ij}}\right\}\end{array}$ $+\underset{i\in I}{{\displaystyle \sum }}{\lambda }_I\left(1-\underset{j\in J}{{\displaystyle \sum }}{Y}_{ij}\right)=\text{Minimize}\underset{j\in J}{{\displaystyle \sum }}\{f_j{X}_j+\underset{i\in I}{{\displaystyle \sum }}\left(d_{ij}-{\lambda }_i\right)Y_{ij}$ $+K_j\sqrt{\underset{i\in I}{{\displaystyle \sum }}{u}_i{Y}_{ij}}+\theta \sqrt{\underset{i\in I}{{\displaystyle \sum }}{\sigma }_i^2{Y}_{ij}}\}+\underset{i\in I}{{\displaystyle \sum }}{\lambda }_i$

$\text{subject}\text{to}{Y}_{ij}\in X_j,\forall i\in I,\forall j\in J$

$X_j\in \left\{0,1\right\},\forall j\in J$

$Y_{ij}\in \left\{0,1\right\},\forall i\in I,\forall j\in J$

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 $i\in I$ , ${\sigma }_i^2/u_i=\gamma \le 0$ . 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

$\text{Minimize}{\displaystyle \underset{j\in J}{\sum }\left\{f_j{X}_j+{\displaystyle \underset{i\in I}{\sum }\left(d_{ij}-{\lambda }_i\right)Y_{ij}+K_j\sqrt{{\displaystyle \underset{i\in I}{\sum }{\mu }_i{Y}_{ij}}}+\Theta \sqrt{{\displaystyle \underset{i\in I}{\sum }{\sigma }_i^2{Y}_{ij}}}}\right\}+{\displaystyle \underset{i\in I}{\sum }{\lambda }_i}}$

subject to

$Y_{ij}\le X_j,\forall i\in I,\forall j\in J$

$X_j\in \left\{0,1\right\},\forall j\in J$

$Y_{ij}\in \left\{0,1\right\},\forall i\in I,\forall j\in J.$

To solve this sub-problem, we can divide the objective function into three parts. The X part contains ${\displaystyle {\sum }_{j\in J}{f}_j{X}_j}$ , the Y part contain

${\displaystyle {\sum }_{i\in I}\left\{\left(d_{ij}-{\lambda }_i\right)Y_{ij}+K_j\sqrt{{\displaystyle {\sum }_{i\in I}{\mu }_i{Y}_{ij}}}+\Theta \sqrt{{\displaystyle {\sum }_{i\in I}{\sigma }_i^2{Y}_{ij}}}\right\}}$ and the $\lambda$ part contains

${\displaystyle {\sum }_{i\in I}{\lambda }_i}$ . Since the $\lambda$ part has no decision variables, it can be ignored for the optimization. To minimize the objective function, we decide the value for $X_j$ as follows: for each j, if $f_j$ plus the minimum value of the Y part for that j is negative, we set $X_j$ to 1 and set $Y_{ij}$ to achieve the minimum value; else, we set $X_j$ and $Y_{ij}$ to 0. Therefore the problem reduces to finding the minimum value for the Y part. For given $j\in J$ , let $b_i=d_{ij}-{\lambda }_i,c_i^1=K_j^2{\mu }_i$ , $c_i^2={\Theta }^2{\sigma }_i^2$ and $y_i=Y_{ij}$ . Then the Y part minimization problem can be abstracted into

$\text{Minimize}{\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^1{y}_i}}+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^2{y}_i}}}$

In “A joint location-inventory model”, an efficient sorting method was introduced to solve this problem under the condition that $c_i^1/c_i^2$ = 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 $c_i^1/c_i^2$ = constant, let's say $\lambda$ , for all i. Now the y part can be rewritten as follows:

$\begin{array}{l}{\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^1{y}_i}}+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^2{y}_i}}}\\ ={\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i}+\sqrt{{\displaystyle \underset{i\in I}{\sum }\gamma c_i^2{y}_i}}+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^2{y}_i}}\\ ={\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i+\left(1+\sqrt{\gamma }\right)\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^2{y}_i}}}.\end{array}$

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:

(P) Minimize

${\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i}+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i{y}_i}}$ (2.1)

subject to

$y_i\in \left\{0,1\right\},\forall i\in I$ (2.2)

where $c_i=c_i^2$

Mark S. Daskin, Collette R. Coullard, and Zuo-Jun Max Shen proved that (P) can be solved efficiently by a sorting method, in ${\rm O}\left(\left|I\right|\log \left|I\right|\right)$ time. The sorting method works as follows:

Let $I^{-}=\left\{i\in I|b_i<0\right\}$ and $I_1^{-}=\left\{i\in I^{-}|b_i>0\right\}$

1. Set $y_i=0$ for all $i\in I^{-}$

2. Set $y_i=1$ for all $i\in I^{-}$ such that $c_i=0$ .

3. Sort the elements in $I_1^{-}$ in increasing order of $b_i/c_i$ .

4. For each $r\in \left\{0\right\}\cup I_1^{-}$ ,compute

$S_r={\displaystyle \underset{i=1}{\overset{r}{\sum }}{b}_i}+\sqrt{{\displaystyle \underset{i=1}{\overset{r}{\sum }}{c}_i}}$

(If $r=0$ , then $S_r=0$ .)

5. Choose the r that minimizes $S_r$ and set $y_i=1$ for $i=1,\cdots ,r.$

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 $c_i^1/c_i^2$ = 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:

(PP) minimize

$\min {\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^1{y}_i}}+\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^2{y}_i}}+\cdots +\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^m{y}_i}}}={\displaystyle \underset{i\in I}{\sum }{b}_i{y}_i}+{\displaystyle \underset{t=1}{\overset{m}{\sum }}\sqrt{{\displaystyle \underset{i\in I}{\sum }{c}_i^t{y}_i}}}$

subject to

$y_i\in \left\{0,1\right\}$ (2.3)

Throughout the analysis below, we assume that $c_i^t>0$ for all $i\in I$ and $t\in \left\{1,\cdots ,m\right\}$ . 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 $c_i^t=\epsilon$ , for small $\epsilon$ , if it equals 0. Furthermore, we will assume that $c_i^t\ge 1$ for all $i\in I$ and $t\in \left\{1,\cdots ,m\right\}$ . This assumption is not restrictive, since if $0<c_i^t<1$ we can multiply the objective function by some constant M without changing the optimal solution; $c_i^t$ then becomes $M^2{c}_i^t$ . For large enough M, all coefficients are greater than or equal to 1.

Let $I^{-}=\left\{i\in I|b_i\le 0\right\}$ . Obviously, if $i\notin I^{-}$ than $y_i^{*}=0$ in any optimal solution $y^{*}$ . Assume without loss of generality that the elements of $I^{-}$ are sorted such that

$\frac{b_1}{{\displaystyle {\sum }_{t=1}^m{c}_1^t}}\le \frac{b_2}{{\displaystyle {\sum }_{t=1}^m{c}_2^t}}\le \cdots \le \frac{b_n}{{\displaystyle {\sum }_{t=1}^m{c}_n^t}}$

where $n=\left|I^{-}\right|$ .

Consider the two square root problem, i.e., m = 2. As shown in “A joint location-inventory model”, if $\frac{c_i^1}{c_i^2}$ = 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 $c_i^1/c_i^2$ ratios are “close enough”.

Suppose that $\frac{c_i^t}{c_i^1}=\left(1+{\alpha }_i\right)c$ , $t\in \left\{2,\cdots ,m\right\}$ and $\forall i\in I$ with ${\alpha }_i\in \left[\alpha ,\bar{\alpha }\right]$ for some constants ${\alpha }_i,\underset{\_}{\alpha },\bar{\alpha },c$ . Our aim is to identify values for $\underset{\_}{\alpha }$ and $\bar{\alpha }$ , 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 $I^{-}=\left\{i\in I^{-}|b_i<0\right\}$ are indexed and sorted such that

$\frac{b_1}{{\displaystyle {\sum }_{t=1}^m{c}_1^t}}\le \frac{b_2}{{\displaystyle {\sum }_{t=1}^m{c}_2^t}}\le \cdots \le \frac{b_n}{{\displaystyle {\sum }_{t=1}^m{c}_n^t}}$ (2.4)

Conjecture 2.1 There exists an optimal solution $y^{*}$ to (PP) such that the following property holds: if $y_k^{*}=1$ for some $k\in I_1^{-}$ , then $y_l^{*}=1$ for all $l\in \left\{1,\cdots ,k-1\right\}$ .

Start of Proof: Let $y^{*}$ be an optimal solution to (PP). Assume (for a contradiction) that $y_k^{*}=1$ but $y_l^{*}=0$ for some $l\in \left\{1,\cdots ,k-1\right\}$ . Assume that $y^{*}$ 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

${y^{\prime }}_i=\{\begin{array}{l}1,\text{if}i=l\\ y_i^{*},\text{otherwise},\end{array}$

${y^{″}}_i=\{\begin{array}{l}0,\text{if}i=k\\ y_i^{*},\text{otherwise}.\end{array}$

Let $z^{*};z^{\prime };z^{″}$ be the objective values corresponding to $y^{*};y^{\prime };y^{″}$ , respectively. Let $R=\left\{i\in I^{-}\backslash \left\{k,l\right\}|y_i^{*}=1\right\}$ , and let $C^t={\displaystyle {\sum }_{i\in R}{c}_i^t}$ . Clearly,

$z^{\prime }-z^{*}=b_l+{\displaystyle \underset{t=1}{\overset{m}{\sum }}\left[\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\right]}$ (2.5)

$z^{*}-z^{″}=b_k+{\displaystyle \underset{t=1}{\overset{m}{\sum }}\left[\sqrt{C^t+c_k^t}-\sqrt{C^t}\right]}$ (2.6)

Then from Equation (2.5), we have:

$\frac{z^{\prime }-z^{*}}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}=\frac{b_t}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}+\frac{{\displaystyle {\sum }_{t=1}^m\left(\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\right)}}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}$ (2.7)

Also, from Equation (2.6), we have:

$\frac{z^{*}-z^{″}}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}=\frac{b_k}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}+\frac{{\displaystyle {\sum }_{t=1}^m\left(\sqrt{C^t+c_k^t}-\sqrt{C^t}\right)}}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}$

Since

$z^{\prime }\le z^{*}$ and $z^{″}\le z^{*}$ (2.8)

and

$\frac{z^{\prime }-z^{*}}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}>0$ (2.9)

$\frac{z^{*}-z^{″}}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}<0$ (2.10)

if we can identify a condition such that

$\frac{z^{\prime }-z^{*}}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}\le \frac{z^{*}-z^{″}}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}$ (2.11)

Then conjecture 2.1 would be proved.

From the convexity of the square root function, we have

$\frac{\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}}{c_l^t}\le \frac{\sqrt{C^t+c_k^t}-\sqrt{C^t}}{c_k^t}$ (2.12)

It is sufficient to find a condition that makes

$\frac{{\displaystyle {\sum }_{t=1}^m\left(\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\right)}}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}\le \frac{{\displaystyle {\sum }_{t=1}^m\left(\sqrt{C^t+c_k^t}-\sqrt{C^t}\right)}}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}$ (2.13)

An instance that satisfies inequality (2.13) must satisfy (2.11). Since $\frac{b_l}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}\le \frac{b_k}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}$ by the way $I^{-}$ 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, $\frac{c_i^t}{c_i^1}=\left(1+{\alpha }_i\right)c,t\in \left\{1,\cdots ,m\right\}$ and $\forall i\in I$ with ${\alpha }_i\in \left[\underset{\_}{\alpha },\bar{\alpha }\right]$ . So we change the format of inequality (5.13) and associate it with our assumption.

First note that

$\begin{array}{l}\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\\ =\frac{\left(\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\right)\left(\sqrt{C^t+c_k^t+c_l^t}+\sqrt{C^t+c_k^t}\right)}{\sqrt{C^t+c_k^t+c_l^t}+\sqrt{C^t+c_k^t}}\\ =\frac{\left(C^t+c_k^t+c_l^t\right)-\left(C^t+c_k^t\right)}{\sqrt{C^t+c_k^t+c_l^t}+\sqrt{C^t+c_k^t}}\\ =\frac{c_l^t}{\sqrt{C^t+c_k^t+c_l^t}+\sqrt{C^t+c_k^t}}\end{array}$ (2.14)

Given the assumption, we have:

$c_l^t\le c\left(1+\bar{\alpha }\right)c_l^1$

$\sqrt{C^t+c_k^t+c_l^t}+\sqrt{C{}^t+c_k^t}\ge \sqrt{c}\sqrt{1-\underset{\_}{\alpha }}\left(\sqrt{C^t+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)$

Since all the terms are greater than zero, we have:

$\frac{c_l^t}{\sqrt{C^t+c_k^t+c_l^t}+\sqrt{C^t+c_k^t}}\le \frac{c\left(1+\bar{\alpha }\right)c_l^1}{\sqrt{c}\sqrt{1-\underset{\_}{\alpha }}\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)}$ (2.15)

Simplifying the right hand side term, we have:

$\begin{array}{l}\frac{c\left(1+\bar{\alpha }\right)c_l^1}{\sqrt{c}\sqrt{1-\underset{\_}{\alpha }}\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)}\\ =\sqrt{c}\frac{1+\bar{\alpha }}{\sqrt{1-\underset{\_}{\alpha }}}\frac{c_l^1\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)}{\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)}\\ =\sqrt{c}\frac{1+\bar{\alpha }}{\sqrt{1-\underset{\_}{\alpha }}}\frac{c_l^1\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)}{c_l^1}\\ =\sqrt{c}\frac{1+\bar{\alpha }}{\sqrt{1-\underset{\_}{\alpha }}}\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)\end{array}$ (2.16)

Combining (5.14), (5.15) and (5.16), we have:

$\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\le \sqrt{c}\frac{1+\bar{\alpha }}{\sqrt{1-\underset{\_}{\alpha }}}\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)$

This holds for any $t\in \left\{1,\cdots ,m\right\}$ . Summing over t, we get :

${\displaystyle \underset{t=1}{\overset{m}{\sum }}\left(\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\right)}\le m\sqrt{c}\frac{1+\bar{\alpha }}{\sqrt{1-\underset{\_}{\alpha }}}\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)$ (2.17)

Given the assumption, we also have:

${\displaystyle \underset{t=1}{\overset{m}{\sum }}{c}_l^t}\ge mc\left(1-\underset{\_}{\alpha }\right)c_l^1$ (2.18)

Since all the terms are positive.

$\begin{array}{l}\frac{{\displaystyle {\sum }_{t=1}^m\left(\sqrt{C^t+c_k^t+c_l^t}-\sqrt{C^t+c_k^t}\right)}}{{\displaystyle {\sum }_{t=1}^m{c}_l^t}}\\ \le \frac{m\sqrt{c}\frac{1+\bar{\alpha }}{\sqrt{1-\underset{\_}{\alpha }}}\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)}{mc\left(1-\underset{\_}{\alpha }\right)c_l^1}\\ =\frac{\left(1+\bar{\alpha }\right)\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)}{\sqrt{c}\sqrt{{\left(1-\underset{\_}{\alpha }\right)}^3}{c}_l^1}\end{array}$ (2.19)

Similarly we have

$\begin{array}{l}\sqrt{C^t+c_k^t}-\sqrt{C^t}\\ =\frac{\left(\sqrt{C^t+c_k^t}-\sqrt{C^t}\right)\left(\sqrt{C^t+c_k^t}+\sqrt{C^t}\right)}{\sqrt{C^t+c_k^t}+\sqrt{C^t}}\\ =\frac{\left(C^t+c_k^t\right)-\left(C^t\right)}{\sqrt{C^t+c_k^t}+\sqrt{C^t}}\\ =\frac{c_k^t}{\sqrt{C^t+c_k^t}+\sqrt{C^t}}\end{array}$ (2.20)

Given the assumption, we have:

$c_k^t\ge c\left(1-\underset{\_}{\alpha }\right)c_k^1$

$\sqrt{C^t+c_k^t}+\sqrt{C^t}\le \sqrt{c}\sqrt{1+\bar{\alpha }}\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)$

Since all the terms are greater than zero, we have:

$\frac{c_k^t}{\sqrt{C^t+c_k^t}+\sqrt{C^t}}\ge \frac{c\left(1-\underset{\_}{\alpha }\right)c_k^1}{\sqrt{c}\sqrt{1+\bar{\alpha }}\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)}$ (2.21)

Simplifying the right hand side term, we have:

$\begin{array}{l}\frac{c\left(1-\underset{\_}{\alpha }\right)c_k^1}{\sqrt{c}\sqrt{1+\bar{\alpha }}\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)}\\ =\sqrt{c}\frac{1-\underset{\_}{\alpha }}{\sqrt{1+\bar{\alpha }}}\frac{c_k^1\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}{\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}\\ =\sqrt{c}\frac{1-\underset{\_}{\alpha }}{\sqrt{1-\bar{\alpha }}}\frac{c_k^1\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}{c_k^1}\\ =\sqrt{c}\frac{1-\underset{\_}{\alpha }}{\sqrt{1+\bar{\alpha }}}\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)\end{array}$ (2.22)

Combining (2.20), (2.21) and (2.22), we have:

$\sqrt{C^t+c_k^t}-\sqrt{C^t}\ge \sqrt{c}\frac{1-\underset{\_}{\alpha }}{\sqrt{1+\bar{\alpha }}}\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)$

This holds for any $t\in \left\{1,\cdots ,m\right\}$ . Summing over t, we get:

${\displaystyle \underset{t=1}{\overset{m}{\sum }}\left(\sqrt{C^t+c_k^t}-\sqrt{C^t}\right)\ge m\sqrt{c}\frac{1-\underset{\_}{\alpha }}{\sqrt{1+\bar{\alpha }}}\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}$ (2.23)

Given the assumption, we also have:

${\displaystyle \underset{t=1}{\overset{m}{\sum }}{c}_k^t}\le mc\left(1+\bar{\alpha }\right)c_k^1$ (2.24)

since all the terms are positive, inequality (2.23) and (2.24) imply

$\begin{array}{l}\frac{{\displaystyle {\sum }_{t=1}^m\left(\sqrt{C^t+c_k^t}-\sqrt{C^t}\right)}}{{\displaystyle {\sum }_{t=1}^m{c}_k^t}}\\ \ge \frac{m\sqrt{c}\frac{1-\underset{\_}{\alpha }}{\sqrt{1+\bar{\alpha }}}\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}{mc\left(1+\bar{\alpha }\right)c_k^1}\\ =\frac{\left(1-\underset{\_}{\alpha }\right)\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}{\sqrt{c}\sqrt{{\left(1+\bar{\alpha }\right)}^3{c}_k^1}}\end{array}$ (2.25)

From inequalities (2.19) and (2.25), we can see that if we have

$\frac{\left(1+\bar{\alpha }\right)\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)}{\sqrt{c}\sqrt{{\left(1-\underset{\_}{\alpha }\right)}^3}{c}_l^1}\le \frac{\left(1-\underset{\_}{\alpha }\right)\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)}{\sqrt{c}\sqrt{{\left(1+\bar{\alpha }\right)}^3}{c}_k^1}$ (2.26)

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

$\begin{array}{c}\frac{\sqrt{{\left(1+\bar{\alpha }\right)}^5}}{\sqrt{{\left(1-\underset{\_}{\alpha }\right)}^5}}\le \frac{\frac{\sqrt{C^1+c_k^1}-\sqrt{C^1}}{c_k^1}}{\frac{\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}}{c_l^1}}\\ =\frac{\frac{\left(\sqrt{C^1+c_k^1}-\sqrt{C^1}\right)\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)}{c_k^1\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)}}{\frac{\left(\sqrt{C^1+c_k^1+c_l^1}-\sqrt{C^1+c_k^1}\right)\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)}{c_l^1\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)}}\\ =\frac{\frac{c_k^1}{c_k^1\left(\sqrt{C^1+c_k^1}+\sqrt{C^1}\right)}}{\frac{c_l^1}{c_l^1\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}\right)}}=\frac{\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}}{\sqrt{C^1+c_k^1}+\sqrt{C^1}}\end{array}$ (2.27)

For the right hand side of inequality (2.27), needing the minimum value of $\frac{\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}}{\sqrt{C^1+c_k^1}+\sqrt{C^1}}$ .

Over all k, l, call it $R^{*}$ , is easy to accomplish through a simple iterative procedure.

For every $t\in 1,\cdots ,m$

Step 1: Let $l=\underset{1\le i\le k-1}{\arg \min }\left\{c_i^t\right\}$ .

Step 2: Let $k=\underset{2\le i\le n}{\arg \min }\left\{\frac{\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^1+c_k^1}}{\sqrt{C^1+c_k^1}+\sqrt{C^1}}\right\}$ .

For the left hand side of inequality (2.17), the value is decided by $\frac{1+\bar{\alpha }}{1-\bar{\alpha }}$ 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 $c\left(1+\bar{\alpha }\right)$ should be the largest ratio of $c_i^1$ and $c_i^t$ , for all $i\in I$ and $t\in 2,\cdots ,m$ ; call it $\bar{\gamma }$ . Also, the largest value of $c\left(1+\bar{\alpha }\right)$ should be the smallest ratio of $c_i^1$ and $c_i^t$ , for all $i\in I$ and $t\in 2,\cdots ,m$ ; call it $\underset{}{\underset{︸}{\gamma }}$ .So

$\frac{1+\bar{\alpha }}{1-\underset{\_}{\alpha }}=\frac{c\left(1+\bar{\alpha }\right)}{c\left(1-\underset{\_}{\alpha }\right)}\ge \frac{\bar{r}}{\underset{\_}{r}}$

As a result, in a given dataset, if we have ${\left(\frac{\bar{\gamma }}{\gamma }\right)}^{2.5}\le R$ 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 ${\left(\frac{\bar{\gamma }}{\gamma }\right)}^{2.5}\le R$ , then there ex-

ists an optimal solution y to (PP) such that the following property holds: if $y_k^{*}=1$ for some $k\in I_1^{-}$ , then $y_l^{*}=1$ for all $l\in \left\{1,\cdots ,k-1\right\}$ .

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);

$\begin{array}{l}\frac{\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^2+c_k^2+c_l^2}-\sqrt{C^1+c_k^1}-\sqrt{C^2+c_k^2}}{c_l^1+c_l^2}-\frac{\sqrt{C^1+c_k^1}+\sqrt{C^2+c_k^2}-\sqrt{C^1}-\sqrt{C^2}}{c_k^1+c_k^2}\\ =\frac{\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^2+c_k^2+c_l^2}-\sqrt{C^1+c_k^1}-\sqrt{C^2+c_k^2}\right)\left(c_k^1+c_k^2\right)-\left(\sqrt{C^1+c_k^1}+\sqrt{C^2+c_k^2}-\sqrt{C^1}-\sqrt{C^2}\right)\left(c_l^1+c_l^2\right)}{\left(c_l^1+c_l^2\right)\left(c_k^1+c_k^2\right)}\end{array}$

The denominator is larger than zero as c_k and c_l are larger than zero. For the numerator, we need to compare.

We need to compare

$\left(\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^2+c_k^2+c_l^2}\right)\left(c_k^1+c_k^2\right)+\left(\sqrt{C^1}+\sqrt{C^2}\right)\left(c_l^1+c_l^2\right)$

and

$\left(\sqrt{C^1+c_k^1}+\sqrt{C^2+c_k^2}\right)\left(c_k^1+c_k^2+c_l^1+c_l^2\right)$ .

From here we can see that if we do not add a condition on the relation between $c_k^1+c_k^2$ and $c_l^1+c_l^2$ .

The difference between the previous terms can be either positive or negative. So we first add the simple condition that ${\displaystyle {\sum }_{t=1}^m{c}_l^t}={\displaystyle {\sum }_{t=1}^m{c}_k^t}$ .

So the problem changes to comparing

$\sqrt{C^1+c_k^1+c_l^1}+\sqrt{C^2+c_k^2+c_l^2}+\sqrt{C^1}+\sqrt{C^2}$

and

$2\left(\sqrt{C^1+c_k^1}+\sqrt{C^2+c_k^2}\right)$

As these terms are all positive, we can square them without changing their magnitude relation.

The left hand side becomes

$\begin{array}{l}{C}^1+c_k^1+c_l^1+C^2+c_k^2+c_l^2+C^1+C^2+2\left(\sqrt{C^1+c_k^1+c_l^1}\sqrt{C^2+c_k^2+c_l^2}\right)\\ +\left(\sqrt{C^1}\sqrt{C^2}\right)+\left(\sqrt{C^1+c_k^1+c_l^1}\sqrt{C^1}\right)+\left(\sqrt{C^2+c_k^2+c_l^2}\sqrt{C^2}\right)\\ +\left(\sqrt{C^1+c_k^1+c_l^1}\sqrt{C^2}\right)+\left(\sqrt{C^2+c_k^2+c_l^2}\sqrt{C^1}\right)\end{array}$

The right hand side becomes

$4\left(C^1+c_k^1+C^2+c_k^2+2\left(\sqrt{C^1+c_k^1}\sqrt{C^2+c_k^2}\right)\right)$

which can be written as the same pattern as the left hand side,

$\begin{array}{l}{C}^1+c_k^1+C^2+c_k^2+C^1+c_k^1+C^2+c_k^2+2\left(\sqrt{C^1+c_k^1}\sqrt{C^2+c_k^2}\right)\\ +\left(\sqrt{C^1+c_k^1}\sqrt{C^2+c_k^2}\right)+\left(\sqrt{C^1+c_k^1}\sqrt{C^1+c_k^1}\right)+\left(\sqrt{C^2+c_k^2}\sqrt{C^2+c_k^2}\right)\\ +\left(\sqrt{C^1+c_k^1}\sqrt{C^2+c_k^2}\right)+\left(\sqrt{C^1+c_k^1}\sqrt{C^2+c_k^2}\right)\end{array}$

The difference between these two sides is

$\begin{array}{l}\left(\sqrt{C^1+c_k^1+c_l^1}\sqrt{C^2+c_k^2+c_l^2}\right)+\left(\sqrt{C^1}\sqrt{C^2}\right)\\ +\left(\sqrt{C^1+c_k^1+c_l^1}\sqrt{C^1}\right)+\left(\sqrt{C^2+c_k^2+c_l^2}\sqrt{C^2}\right)\\ +\left(\sqrt{C^1+c_k^1+c_l^1}\sqrt{C^2}\right)+\left(\sqrt{C^2+c_k^2+c_l^2}\sqrt{C^1}\right)-4\left(\sqrt{C^1+c_k^1}\sqrt{C^2+c_k^2}\right).\end{array}$

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 ${\left(\frac{\bar{r}}{\underset{\_}{r}}\right)}^{2.5}\le R^{*}$ ,

then there exists an optimal solution $y^{*}$ to (PP) such that the following property holds: if $y_k^{*}=1$ for some $k\in I_1^{-}$ , then $y_l^{*}=1$ for all $l\in \left\{1,\cdots ,k-1\right\}$ .

From the Theorem we can see that in a data set, the will of $R^{*}{\left(\frac{\bar{r}}{\underset{\_}{r}}\right)}^{-2.5}$ will de-

cide whether this data set holds the property. Let's name this number as R. So when $R\ge 1$ , 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 $0<R<1$ and the gap between the lower bound and optimal solution.

Conjecture 2.2: There exists a lower bound $z_{lb}=z^{\prime }+\left(\frac{1-R}{R}\right)\min \left\{b_i\left(i\in 1,\cdots ,k-1\right)\right\}$ to (PP) such that $z^{\prime }$ is the objective value of a feasible solution $y^{\prime }$ that the following property holds: if ${y^{\prime }}_k^{=1}$ for some $k\in I_1^{-}$ , then $y^{l^{\prime }=1}$ for all $l\in \left\{1,\cdots ,k-1\right\}$ .

Start of Proof: Let $y^{*}$ be an optimal solution to (PP) and $z^{*}$ is its objective value. Assume (for a contradiction) that $y_k^{*}=1$ but $y_l^{*}=0$ for some $l\in \left\{1,\cdots ,k-1\right\}$ and $z^{*}<z_{lb}$ . We will find a feasible solution $y^{\prime }$ with the following property: if ${y^{\prime }}_k^{=1}$ for some $k\in I_1^{-}$ , then ${y^{\prime }}_t^{=1}$ for all $l\in \left\{1,\cdots ,k-1\right\}$ that breaks the inequality, thus contradicting our assumption.