Integer programming formulations applied to optimal allocation in stratified sampling 3. Proposed formulationsInteger programming formulations applied to optimal allocation in stratified sampling 3. Proposed formulations

• Previous
• Next

From an optimization point of view, solving the problems defined by (2.7) $-$ (2.10) or by (2.16) $-$ (2.20) consists of determining $n_1,n_2,\dots n_H$ chosen from the sets defined by $A_h=\left\{n_{\min },\dots ,N_h\right\},$ $h=1,\dots ,H,$ that the constraints in each of these problems are satisfied and the corresponding objective function is minimized. As already indicated, a standard minimum sample size per stratum of $n_{\min }=2$ is considered here to define the sets $A_h,$ but this value may be changed as needed to accommodate specific survey requirements.

Taking this approach, a new formulation may be considered where the decision variables are indicator variables of which elements of the sets $A_h\left(h=1,\dots ,H\right)$ will be chosen. For this purpose, we introduce the binary variable $x_{hk}$ taking the value 1 if the sample size $k\in A_h$ is allocated to stratum $h,$ and value 0 if this sample size is not allocated to stratum $h,h=1,\dots ,H.$

Considering the formulations previously presented and these new binary variables, we may write two integer programming formulations where the decision variables (i.e., the unknowns to be determined) are of the $0-1$ type, therefore configuring a binary integer programming problem (Wolsey and Nemhauser 1999). The formulation equivalent to Formulation A is given by:

Formulation C

$$\text{Minimize }{\displaystyle {\sum }_{h=1}^H{c}_h\left({\displaystyle {\sum }_{k=n_{\min }}^{N_h}k{x}_{hk}}\right)}(3.1)$$

$$\text{s}\text{.t}\text{. }{\displaystyle {\sum }_{k=n_{\min }}^{N_h}{x}_{hk}}=1\forall h=1,\dots ,H(3.2)$$

$${\displaystyle {\sum }_{h=1}^H{N}_h{p}_{hj}\left({\displaystyle \sum _{k=n_{\min }}^{N_h}\frac{x_{hk}}{k}}\right)}-{\displaystyle {\sum }_{h=1}^H{p}_{hj}}\le 1,j=1,\dots ,m(3.3)$$

$$x_{hk}\in \left\{0,1\right\},k=n_{\min },\dots ,N_h,h=\text{1,}\dots ,H.(3.4)$$

In Formulation C, constraint (3.2) ensures that, for each of the strata, there will be exactly one $x_{hk}$ variable taking the value one. This is equivalent to ensuring the choice of only one value $k$ (the sample size) from each set $A_h\left(h=1,\dots ,H\right).$ Constraint (3.3) is equivalent to constraint (2.9) or its equivalent (2.14) in Formulation A. This formulation contemplates potentially varying unit survey costs for the various strata. If this is not necessary, the objective function in (3.1) may be redefined as

$$\text{Minimize }{\displaystyle {\sum }_{h=1}^H{\displaystyle {\sum }_{k=n_{\min }}^{N_h}k{x}_{hk}}.}(3.5)$$

In order to help with the understanding of the proposed formulation, consider the following example.

Example 1: Suppose that there are three population strata $\left(H=3\right)$ with $N_1=3,N_2=5$ and $N_3=4,$ that the unit survey costs are the same across strata (say $c_h=1\forall h)$ and only one survey variable $\left(m=1\right).$ Formulation C would then look like:

$$\text{Minimize }1x_{11}+2x_{12}+3x_{13}+1x_{21}+2x_{22}+3x_{23}+4x_{24}+5x_{25}+1x_{31}+2x_{32}+3x_{33}+4x_{34}(3.6)$$

$$\text{s}\text{.t}\text{. }{x}_{11}+x_{12}+x_{13}=1(3.7)$$

$$x_{21}+x_{22}+x_{23}+x_{24}+x_{25}=1(3.8)$$

$$x_{31}+x_{32}+x_{33}+x_{34}=1(3.9)$$

$$\begin{array}{ll}{N}_1{p}_{11}\left(1x_{11}+\frac{1}{2}{x}_{12}+\frac{1}{3}{x}_{13}\right)-p_{11}+\hfill & N_2{p}_{21}\left(1x_{21}+\frac{1}{2}{x}_{22}+\frac{1}{3}{x}_{23}+\frac{1}{4}{x}_{24}+\frac{1}{5}{x}_{25}\right)-p_{21}+\hfill \\ \hfill & N_3{p}_{31}\left(1x_{31}+\frac{1}{2}{x}_{32}+\frac{1}{3}{x}_{33}+\frac{1}{4}{x}_{34}\right)-p_{31}\le 1\hfill \end{array}(3.10)$$

$$x_{11},x_{12},x_{13},x_{21},x_{22},x_{23},x_{24},x_{25},x_{31},x_{32},x_{33},x_{34}\in \left\{0,1\right\}.(3.11)$$

Formulation B may also be translated to this new approach of using the binary variables as follows.

Formulation D

$$\text{Minimize }{\displaystyle {\sum }_{j=1}^m{w}_j\frac{1}{Y_j^2}{\displaystyle {\sum }_{h=1}^H\left({\displaystyle {\sum }_{k=n_{\min }}^{N_h}\frac{x_{hk}}{k}}\right)N_h^2{S}_{hj}^2}(3.12)}$$

$$\text{s}\text{.t}\text{. }{\displaystyle {\sum }_{k=n_{\min }}^{N_h}{x}_{hk}}=1\forall h=1,\dots ,H(3.13)$$

$${\displaystyle {\sum }_{h=1}^H{c}_h\left({\displaystyle {\sum }_{k=n_{\min }}^{N_h}k{x}_{hk}}\right)}\le C(3.14)$$

$$x_{hk}\in \left\{0,1\right\}\text{, }k=n_{\min },\dots ,N_h,h=\text{1,}\dots \text{,}H\text{.}(3.15)$$

In Formulation D the objective function (3.12) is equivalent to the objective function (2.20). Constraint (3.13) is equivalent to constraint (2.16). Constraint (3.14) is equivalent to constraint (2.17) and ensures that the total variable cost of the survey will not exceed the allocated budget $C.$ In case we do not have information on unit survey costs per strata, or wish to consider that they are the same across the strata, we replace constraint (3.14) by

$${\displaystyle {\sum }_{h=1}^H{\displaystyle {\sum }_{k=n_{\min }}^{N_h}k{x}_{hk}}}\le n.(3.16)$$

In order to illustrate the proposed formulation, consider the following example.

Example 2: Suppose that there are two population strata $\left(H=2\right)$ with $N_1=3$ and $N_2=4,$ with two survey variables $\left(m=2\right),$ equal unit survey costs for both strata, importance weights $w_j$ equal to $\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$ for both survey variables and a total sample size of $n=5.$ Formulation D would then look like:

$$\begin{array}{ll}\text{Minimize}\hfill & \left[x_{11}\frac{N_1^2}{1}+x_{12}\frac{N_1^2}{2}+x_{13}\frac{N_1^2}{3}\right]\frac{\text{1}}{\text{2}}\left(\frac{S_{11}^2}{Y_1^2}+\frac{S_{12}^2}{Y_2^2}\right)+\hfill \\ \hfill & \left[x_{21}\frac{N_2^2}{1}+x_{22}\frac{N_2^2}{2}+x_{23}\frac{N_2^2}{3}+x_{24}\frac{N_2^2}{4}\right]\frac{\text{1}}{\text{2}}\left(\frac{S_{21}^2}{Y_1^2}+\frac{S_{22}^2}{Y_2^2}\right)\hfill \end{array}(3.17)$$

$$\text{s}\text{.t}\text{. }{x}_{11}+x_{12}+x_{13}=1(3.18)$$

$$x_{21}+x_{22}+x_{23}+x_{24}=1(3.19)$$

$$1x_{11}+2x_{12}+3x_{13}+1x_{21}+2x_{22}+3x_{23}+4x_{24}\le 5(3.20)$$

$$x_{11},x_{12},x_{13},x_{21},x_{22},x_{23},x_{24}\in \left\{0,1\right\}.(3.21)$$

In this paper, these two formulations were resolved applying a method of implicit enumeration called $BranchandBound.$ $BranchandBound$ (Wolsey 1998, Wolsey and Nemhauser 1999) methods obtain the optimal solution for binary integer programming problems efficiently, by considering the resolution of a subset of problems associated with the feasible region for the problem. These methods were developed from the pioneer work of Land and Doig (1960).

The solutions for both Formulations C and D of the approach, labelled BSSM (the initials for Brito, Silva, Semaan and Maculan), were obtained using the R package $Rglpk.$ The R code we developed is available on request. The package $Rglpk$ contains a set of procedures that can be applied for solving linear and integer programming problems.

For comparison purposes in the case of our Formulation C, we also considered in our numerical illustrations an algorithm proposed by (Bethel 1985 and 1989) which is available in the R package $SamplingStrata.$ This algorithm relies on the Kuhn-Tucker Theorem, and uses the Lagrange multipliers (Bazaraa, et al. 2006). In the case of our Formulation D, we compared our approach with a ‘textbook method’ proposed in Cochran (1977, Section 5.A.4), as suggested by the Associate Editor.

• Previous
• Next