Integer programming formulations applied to optimal allocation in stratified sampling 2. Stratified sampling and the optimal allocation problemInteger programming formulations applied to optimal allocation in stratified sampling 2. Stratified sampling and the optimal allocation problem

• Previous
• Next

In stratified sampling (Cochran 1977; Lohr 2010) a population $U$ formed by $N$ units is divided into $H$ strata $U_1,U_2,\dots ,U_H$ having $N_1,N_2,\dots ,N_H$ units respectively. These strata do not overlap (2.1) and together form the entire population (2.2) such that:

$$U_h\cap U_k=\varnothing ,h\ne k(2.1)$$

$${\cup }_{h=1}^H{U}_h=U(2.2)$$

$$N_1+N_2+\dots +N_H={\displaystyle {\sum }_{h=1}^H{N}_h}=N.(2.3)$$

Once the strata are defined, and given an overall sample size $n,$ an independent sample of size $n_h$ is selected from the $N_h$ units in stratum $U_h\left(h=1,\dots ,H\right)$ such that $n_{\min }\le n_h\le N_h\forall h,$ where $n_{\min }$ is the smallest possible sample size in any stratum, and $n_1+n_2+\dots +n_H={\displaystyle {\sum }_{h=1}^H{n}_h}=n.$

A minimum sample size per stratum of $n_{\min }=2$ is considered here, but this value may be changed as needed to accommodate specific survey requirements. A minimum sample size of one per stratum is not recommended because this might lead to solutions that require using approximate methods for variance estimation whenever the allocated sample sizes reach this minimum. In practice, it may even be wise to use $n_{\min }$ larger than 2, because of nonresponse or for other practical reasons.

Assuming full response, the data are collected for all units in the selected sample and used to produce estimates (of totals, say) for a set of $m$ survey variables. Let $y_1,y_2,\dots ,y_m$ denote the survey variables. The variance of variable $y_j$ in stratum $h$ is defined as:

$$S_{hj}^2=\frac{1}{N_h-1}{\displaystyle {\sum }_{i\in U_h}{\left(y_{ij}-{\overline{Y}}_{hj}\right)}^2}(2.4)$$

where $y_{ij}$ is the value of $y_j$ for the $i^{\text{th}}$ population unit, and ${\overline{Y}}_{hj}$ is the population mean for $y_j$ in stratum $h,$ given by

$${\overline{Y}}_{hj}=\frac{1}{N_h}{\displaystyle {\sum }_{i\in U_h}{y}_{ij}}=Y_{hj}/N_h(2.5)$$

for $h=1,\dots ,H$ and $j=1,\dots ,m.$ The population total $Y_j$ for the $j^{\text{th}}$ survey variable is $Y_j={\displaystyle {\sum }_{h=1}^H{\displaystyle {\sum }_{i\in U_h}{y}_{ij}}}={\displaystyle {\sum }_{h=1}^H{Y}_{hj}}.$

Under stratified simple random sampling (STSRS), the variance of the Horvitz-Thompson (HT) estimator $t_j$ of the total for the $j^{\text{th}}$ survey variable (Cochran 1977) is given by:

$$V\left(t_j\right)={\displaystyle {\sum }_{h=1}^H{N}_h^2\left(\frac{1}{n_h}-\frac{1}{N_h}\right)S_{hj}^2}(2.6)$$

where $t_j={\displaystyle {\sum }_{h=1}^H{N}_h/n_h{\displaystyle {\sum }_{i\in s_h}{y}_{ij}}}={\displaystyle {\sum }_{h=1}^H{N}_h}{\overline{y}}_{hj},$ $s_h\subset U_h$ is the set of labels of the $n_h$ units sampled in stratum $h,$ and ${\overline{y}}_{hj}$ is the sample mean in stratum $h.$

Because the values of $N_h$ and $S_{hj}^2$ are fixed after the strata have been defined, the variance of the HT estimator $t_j$ of the total for the $j^{\text{th}}$ survey variable in (2.6) depends only on the sample sizes $n_h$ allocated to the strata. This allocation is important, because it is what enables the survey designer to control the precision of the survey estimates.

In general, when performing the allocation, the survey planner seeks a balance between achieving the desired precision for each of the survey variables of interest and the cost of the survey. The importance and computational complexity of this problem have motivated many contributions, which consider one of the two goals of the allocation problem, as described in Section 1. See for example Kokan (1963), Folks and Antle (1965), Kokan and Khan (1967), Huddleston, Claypool and Hocking (1970), Kish (1976), Bethel (1985, 1989), Chromy (1987), Valliant and Gentle (1997), Khan and Ahsan (2003), García and Cortez (2006), Kozak (2006), Day (2010), Khan, Ali and Ahmad (2011), Ismail, Nasser and Ahmad (2011), Khan, Ali, Raghav and Bari (2012).

All of the above apply methods based on linear programming theory, convex programming, dynamic programming, multi-objective programming and heuristics to try and solve the multivariate optimal allocation problem. Here we propose two integer programming formulations to tackle the problem.

Formulation A

$$\text{Minimize }{\displaystyle \sum _{h=1}^H{c}_h{n}_h}(2.7)$$

$$\text{s}\text{.t}\text{. }{n}_{\min }\le n_h\le N_h,h=1,\dots ,H(2.8)$$

$$\sqrt{V\left(t_j\right)}/Y_j\le {\text{CV}}_{j}j=1,\dots ,m(2.9)$$

$$n_h\in Z_{+}h=1,\dots ,H(2.10)$$

where $c_h$ represents the unit level survey cost for sampling from stratum $h.$

In this formulation, the objective function to be minimized (2.7) corresponds to the overall variable cost budget for the survey (which we denote by $C).$ If the unit level survey costs for sampling from the various strata are unknown or are assumed to be the same, then $c_h$ may all be set to one and the alternative objective function to minimize is $n={\displaystyle {\sum }_{h=1}^H{n}_h},$ namely the overall sample size.

Constraint (2.8) ensures that at least $n_{\min }$ units are allocated to each stratum, and that the sample size will not exceed the population size for the stratum.

Constraint (2.9) ensures that the CV of the HT estimator of total for each survey variable is below a pre-specified threshold ${\text{CV}}_j\left(j=1,\dots ,m\right)$ called target CV. Finally, constraint (2.10) ensures that all the allocated sample sizes are integers.

Note that the constraints (2.9) may be rewritten as:

$$\frac{V\text{(}{t}_j\text{)}}{Y_j{}^2{\text{ CV}}_j^2}\le 1\text{ , }j=1,\dots ,m.(2.11)$$

Now replacing the numerator in (2.11) by equation (2.6), leads to:

$${\displaystyle {\sum }_{h=1}^H\left(\frac{N_h^2{S}_{hj}^2}{n_h{Y}_j^2{\text{CV}}_j^2}-\frac{N_h{S}_{hj}^2}{Y_j^2{\text{CV}}_j^2}\right)}\le 1,j=1,\dots ,m.(2.12)$$

Defining

$$p_{hj}=\frac{N_h{S}_{hj}^2}{Y_j^2{\text{ CV}}_j^2}(2.13)$$

the constraints (2.12) may be written as:

$${\displaystyle {\sum }_{h=1}^H\left(\frac{N_h{p}_{hj}}{n_h}-p_{hj}\right)}\le 1,j=1,\dots ,m.(2.14)$$

Formulation B

$$\text{Minimize }{\displaystyle {\sum }_{j=1}^m{w}_j\frac{1}{Y_j^2}\left[{\displaystyle {\sum }_{h=1}^H{N}_h^2}\left(\frac{1}{n_h}-\frac{1}{N_h}\right)S_{hj}^2\right]}(2.15)$$

$$\text{s}\text{.t}\text{. }{n}_{\min }\le n_h\le N_h,h=1,\dots ,H(2.16)$$

$${\displaystyle \sum _{h=1}^H{c}_h{n}_h}\le C(2.17)$$

$$n_h\in Z_{+}h=1,\dots ,H(2.18)$$

$$0<w_j<1\forall j\text{ and }{\displaystyle {\sum }_{j=1}^m{w}_j}=1(2.19)$$

where $w_j$ are variable-specific weights, set a priori to represent the relative importance of the survey variables. The variable-specific weights $w_j$ are set by subject matter experts or the survey designers. If they are not specified, equal relative weights could be assigned to all the survey variables considered.

In this formulation, the objective function (2.15) to be minimized corresponds to a weighted sum of the relative variances of the estimates of total for the $m$ survey variables. We use relative variances because different survey variables may be measured in different units, and thus summing variances is not meaningful. Examining (2.15) it is clear that its minimum is achieved when

$${\displaystyle {\sum }_{j=1}^m{w}_j\frac{1}{Y_j^2}\left[{\displaystyle {\sum }_{h=1}^H{N}_h^2}\left(\frac{1}{n_h}\right)S_{hj}^2\right]}$$

is minimum, since the last term

$${\displaystyle {\sum }_{j=1}^m{w}_j\frac{1}{Y_j^2}\left[{\displaystyle {\sum }_{h=1}^H{N}_h^2}\left(-\frac{1}{N_h}\right)S_{hj}^2\right]}$$

does not depend on the stratum sample sizes. Hence the objective function (2.15) may be rewritten:

$$\text{Minimize }{\displaystyle {\sum }_{j=1}^m{w}_j\frac{1}{Y_j^2}\left({\displaystyle {\sum }_{h=1}^H\frac{N_h^2}{n_h}}{S}_{hj}^2\right)}.(2.20)$$

Constraint (2.16) is the same as constraint (2.8) applied in Formulation A. Constraint (2.17) ensures that the total variable cost of the survey will not exceed the allocated budget $C.$ Like constraint (2.10) in Formulation A, constraint (2.18) ensures that all the allocated sample sizes are integers. Constraint (2.19) ensures that the importance weights are adequate for aggregating the relative variances of the estimated totals for each of the survey variables.

When the unit level survey costs $c_h$ per stratum are not known or may be assumed to be equal, constraint (2.17) may be replaced by ${\displaystyle {\sum }_{h=1}^H{n}_h}\le n$ where $n$ is the (maximum) overall sample size.

Both formulations A and B present non-linearity: constraint (2.9) or (2.14) in Formulation A, and the objective function in Formulation B. Therefore a first alternative one could use to resolve the non-linearity problem in these two Formulations would be one of the methods of non-linear programming or convex programming (Bazaraa, Sheralli and Shetty 2006; Luenberger and Ye 2008) that can deal with constraints, as for example penalty based methods or multiplier methods, amongst others. Nevertheless, application of such methods tends to produce solutions (sets of samples sizes to allocate in the strata) that, in general, are non-integers. In addition, when such solutions are rounded to obtain feasible sample sizes, there’s no guarantee to obtain a global optimum (Wolsey 1998) in terms of minimizing the corresponding objective functions.

Alternatively, given that the solutions (sample sizes) must be integers, one could consider applying integer programming methods, such as $BranchandBound$ (Land and Doig 1960; Wolsey 1998; Wolsey and Nemhauser 1999). However, the non-linearity present in both formulations prevents the immediate application of such methods.

With these issues in mind, in the next section we propose two new formulations for integer programming that circumvent these problems and are equivalent to the Formulation A, defined jointly by (2.7), (2.8), (2.9) and (2.10), and Formulation B, defined jointly by (2.20), (2.16), (2.17), (2.18) and (2.19). More specifically, from the resolution of these new formulations it is possible to obtain integer sample sizes $\left(n_h\right)$ for the sample allocation which satisfy the constraints established for each problem and also lead to a global optimum (Wolsey 1998) either for the objective function defined in (2.7), or for the objective function defined in (2.20), respectively.

• Previous
• Next