An Exact Method for Partitioning Dichotomous Items Within the Framework of the Monotone Homogeneity Model

Abstract

The monotone homogeneity model (MHM—also known as the unidimensional monotone latent variable model) is a nonparametric IRT formulation that provides the underpinning for partitioning a collection of dichotomous items to form scales. Ellis (Psychometrika 79:303–316, 2014, doi:10.1007/s11336-013-9341-5) has recently derived inequalities that are implied by the MHM, yet require only the bivariate (inter-item) correlations. In this paper, we incorporate these inequalities within a mathematical programming formulation for partitioning a set of dichotomous scale items. The objective criterion of the partitioning model is to produce clusters of maximum cardinality. The formulation is a binary integer linear program that can be solved exactly using commercial mathematical programming software. However, we have also developed a standalone branch-and-bound algorithm that produces globally optimal solutions. Simulation results and a numerical example are provided to demonstrate the proposed method.

Appendices

Appendix 1

The problem of partitioning a set of binary scale items based on Ellis’ (2014) inequality can be formulated as a BILP. The formulation uses the parameters described in Section 3. The decision variables for the formulation are denoted $y_{jk}$, where $y_{jk} = 1$ if item $j$ is assigned to cluster $k$ and $y_{jk} = 0$, otherwise, $\forall \, 1 \le j \le J$ and $1 \le k \le K$. The partitioning problem can be formulated as a BILP as follows:

$$\begin{aligned} \text {Max: }&f=\sum _{j=1}^J {\sum _{k=1}^K {\eta _k y_{jk} } } \end{aligned}$$

(7)

$$\begin{aligned} \text {subject to:}&\sum _{k=1}^K {y_{jk} \le 1} \,\forall \,1 \le j \le J; \end{aligned}$$

(8)

$$\begin{aligned}&y_{ik}+y_{jk} \le 1, \quad \forall \,1 \le i < j \le J : \Gamma _{ij} = 1, \forall \, 1 \le k \le K; \end{aligned}$$

(9)

$$\begin{aligned}&y_{gk}+y_{ik}+y_{jk} \le 2, \quad \forall \, 1 \le g < i < j \le J : \Phi _{gij} = 1, \forall \, 1 \le k \le K;\quad \quad \end{aligned}$$

(10)

$$\begin{aligned}&y_{jk} \in \{0, 1\}, \quad \forall \, 1 \le j \le J, \forall \, 1 \le k \le K. \end{aligned}$$

(11)

The objective function (7) of the BILP is to maximize the sum of the weighted cluster cardinalities, which is denoted as $f$. Recall from Section 3 that the $\eta _{k}=J^{(-k)}$ are the objective function weights afforded to the assignment of an item to cluster $k, \forall \, 1 \le k \le K$.

Constraint set (8) guarantees that each item is assigned to no more than one cluster. Constraint set (9) prohibits two items, $i$ and $j$, from being placed in the same cluster if their bivariate correlation is negative. Constraint set (10) enforces the restrictions on the partial correlations, as described by Ellis (2014). Constraint (11) requires that the assignment variables are binary.

Appendix 2

The current cluster assignment variables for the branch-and-bound algorithm are denoted $a(j)$, where $a(j)=k$ indicates that item $j$ is assigned to cluster $k, \forall \, 1 \le j \le J$. During the search process, the best-found cluster assignments (i.e., those associated with the current lower bound, $f_{\mathrm{LB}}$) are stored as variables $a^*(j), \forall \, 1 \le j \le J$. The algorithm also makes use of the following auxiliary variables: $q(k)$ is the number of items assigned to cluster $k, \forall \, 1 \le k \le K; \xi (k)$ is a computed upper bound on the number of items that could possibly be assigned to cluster $k, \forall \, 1 \le k \le K$; $\omega (k)$ is a variable that facilitates the computation of $\xi (k), \forall \, 1 \le k \le K$; and $f_{\mathrm{UB}}$ is a computed upper bound on the objective function. The precise steps of the branch-and-bound algorithm are as follows:

• Step 0. INITIALIZATION. Set $j = 0, f = 0, f_{\mathrm{LB}} = -\infty , a(j) = 0\, \forall \,1 \le j \le J, a^*(j) = 0\, \forall \,1 \le j \le J$ and $q(k) = 0 \,\forall \,1 \le k \le K$.

• Step 1. SET CONSTRAINT PARAMETERS. Compute $\Phi _{gij}$ using (2) for all 1 $\le g, i, j \le J$.

• Step 2. STEP FORWARD. Set $j=j + 1, k = 1, a(j)=k$, and $q(k)=q(k) + 1$. If $k=K$, then go to Step 4; otherwise, proceed to Step 3.

• Step 3. FEASIBILITY TESTS. Use the pseudo code in Figure 1 to perform the feasibility tests with respect to pairs formed by item $j$ with previously assigned items ($1 \le i \le j - 1$), as well as triples formed by item $j$ with previously assigned items ($1 \le g < i \le j - 1$). If the result from the pseudo code is “pass” after both tests, then go to Step 4; otherwise, go to Step 6.

• Step 4. BOUND TEST. Use the pseudo code in Figure 2 to perform the bound test. If “pass,” then go to Step 5; otherwise, go to Step 6.

• Step 5. NEW BEST-FOUND SOLUTION. If $j < J$, then proceed to Step 2; otherwise set $a^*(i)=a(i)$ for $1 \le i \le J, f_{\mathrm{LB}}=f_{\mathrm{UB}}$, and proceed to Step 6.

• Step 6. LAST CLUSTER? If $k=K$, then go to Step 8; otherwise, go to Step 7.

• Step 7. BRANCH RIGHT. Set $q(k)=q(k) - 1, k=k + 1, a(j)=k$, and $q(k)=q(k) + 1$, and return to Step 3.

• Step 8. RETRACTION. Set $a(j) = 0, q(k)=q(k) - 1$, and $j=j - 1$. If $j = 0$, then return $a^*(i)$ for $1 \le i \le J, f_{\mathrm{LB}}$, and STOP; otherwise, identify $k : a(j)=k$ and go to Step 6.

Fig. 1

Pseudo code for the FEASIBILITY TEST (Step 3) of the branch-and-bound algorithm.

Fig. 2

Pseudo code for the BOUND TEST (Step 4) of the branch-and-bound algorithm.

The algorithm begins in Step 0 with the initialization of all parameters and arrays. The $\Phi _{gij}$ parameters are computed using (2) in Step 1. Step 2 increments the item pointer index ($j$), sets the cluster index to one ($k = 1$), assigns item $j$ to cluster $k\,(a(j)=k)$, and increments the counter for the number of items in cluster $k\,(q(k)=q(k) + 1)$. Step 3 uses the pseudo code in Figure 1 to ensure that item $j$ is positively correlated to other items assigned to cluster $k$, and to determine whether Ellis’ (2014) partial correlation condition is satisfied if item $j$ is assigned to cluster $k$. This latter component of the feasibility test is accomplished via the examination of all partial correlations associated with item $j$ and all possible pairs of items ($g, i$) previously assigned to cluster $k$. If any triple (g, $i, j$) violates the condition, then the result of the test is “fail”; otherwise, the result is “pass.” Note that Step 3 is not performed if $k=K$ because that cluster is reserved for unscaled items that do not have to satisfy any conditions.

Step 4 uses the pseudo code in Figure 2 to perform a test to determine whether completion of the current partial solution can possibly produce an objective function value that exceeds the current lower bound on the objective function value. Part of the upper bound ($f_{\mathrm{UB}}$) is computed from the direct assignments of the first $j$ items, whereas the remainder of the bound stems from the potential contributions of the yet unassigned items. The second component of the bound is determined based on the feasibility of assigning the yet unassigned items to each cluster. If the feasibility and bound tests in Steps 3 and 4 are “passed,” then a check is made in Step 5 to determine if the assignment of items is complete. If not all of the $J$ items have been assigned to clusters (i.e., $j < J$), then control returns to Step 2 to assign the next item. However, if $j=J$, then the current assignment is installed as the best-found assignment ($a$*($j$), for 1 $\le j \le J$) and the lower bound is set equal to the upper bound ($f_{\mathrm{LB}}=f_{\mathrm{UB}}$).

The current cluster assignment for item $j$ determines the processing at Step 6. If $k < K$, then a branch right operation occurs at Step 7 whereby item $j$ is moved from cluster $k$ to cluster $k+1$, and control is subsequently passed to Step 3 for the feasibility test. However, if $k=K$ at Step 5, then it is not possible to branch right because there is no cluster index $K+1$ and, therefore, depth retraction occurs in Step 8. This occurs by removing the assignment for item $j$ and then reducing the item index pointer ($j=j - 1$). The algorithm terminates when $j = 0$, which indicates that all partitions have been either implicitly or explicitly evaluated. The incumbent best-found assignment is returned as the optimal partition, and $f_{\mathrm{LB}}$ is the optimal value of the objective function ($f^*$).

Given that cluster $K$ is reserved for unscaled items, it is helpful to determine what occurs when too many or too few clusters are selected. Suppose we have $J = 10$ items, and there is one four-item scale, one three-item scale, and three items that cannot be scaled. If we specify two clusters, only the four-item scale is found and the other six items are placed in the cluster of unscaled items. If we specify three clusters, then cluster sizes are {4, 3, 3}, with the last cluster containing the three unscaled items. If we specify too many clusters, say 4, 5, or 6, then the sizes of the clusters would be {4, 3, 1, 2}, {4, 3, 1, 1, 1} and {4, 3, 1, 1, 1, 0}, respectively. Succinctly, the last cluster always contains unscaled items, and any item that is the only item in a cluster is also an unscaled item.