5 Solving the error localisation problem with hard and soft edits

Sander Scholtus

Previous | Next

We shall now describe an adapted version of the branch-and-bound algorithm of De Waal and Quere, which may be used to solve the error localisation problem defined in Section 3. The basic setup of the algorithm is the same as in Section 2.3. In particular, the procedures for eliminating and fixing variables are carried out the same way as in the original algorithm.

The main difference is that now in each node, the current set of edits ${\Psi }_q$ is partitioned into a current set of hard edits ${\Psi }_{qH}$ and a current set of soft edits ${\Psi }_{qS}.$ For the root node, the partition simply follows that of the original set of edits, i.e., ${\Psi }_{0H}={\Psi }_H$ and ${\Psi }_{0S}={\Psi }_S.$ For all other nodes, the partition can be summarised as follows: if an edit is generated only from hard edits, then it is a hard edit; if any soft edits are involved in its generation, then it is a soft edit. Furthermore, for each soft edit ${\psi }_{qS}^k\in {\Psi }_{qS},$ we construct an index set $B_{qS}^k$ $–$ analogous to $B_q^k$ in Section 4 $–$ which contains the indices of all the original soft edits ${\psi }_{0S}^k$ that were involved, directly or indirectly, in its generation.

Having generated ${\Psi }_{qH}$ and ${\Psi }_{qS}$ for a particular node, we can fill in the original values of the variables that have not been treated yet, to check which of these edits are failed. In the old algorithm, this check could have two possible outcomes: either more variables need to be eliminated (at least one of the edits is failed), or a feasible solution has been found (none of the edits are failed). In the new algorithm, three different situations may arise.

First of all, if at least one edit in ${\Psi }_{qH}$ is failed, then the variables that have been eliminated so far cannot be imputed to satisfy the original hard edits. Hence, more variables need to be eliminated. In this case, we continue the generation of branches from the current node.

A second possibility is that none of the edits in ${\Psi }_{qH}$ or ${\Psi }_{qS}$ are failed. This means that the variables that have been eliminated so far can be imputed to satisfy all the original edits, both hard and soft. Thus a feasible solution has been found, for which the value of target function (3.1) equals $D=\lambda D_{\text{FH}}.$ If this value is smaller than or equal to the value of (3.1) for the best solution found so far, say $D_{\min },$ then the new solution is stored. Otherwise, it is discarded. Either way, it is not useful to continue the algorithm from the current node, because if more variables are eliminated, the value of $D$ can only increase. Hence, we return to the last previous branch that has not been completely searched yet and continue the algorithm from there.

The last possibility is that the edits in ${\Psi }_{qH}$ are satisfied, but that at least one edit in ${\Psi }_{qS}$ is failed. In this case, the variables that have been eliminated so far can be imputed to satisfy the original hard edits, but not all the original soft edits. Hence, a feasible solution to the error localisation problem has been found, but the contribution of $D_{\text{soft}}$ to $D$ is non-zero. According to Theorem 1 or Theorem 2, it is possible to satisfy all original soft edits, except those in a representing set $B$ of the index sets $B_{qS}^k$ for all failed edits in ${\Psi }_{qS}.$ Since this property is shared by all representing sets, we are free to choose $B$ in such a way that $D_{\text{soft}}$ is minimised, given the selection of variables to impute. If expression (3.2) is used for $D_{\text{soft}},$ then the optimal choice of $B$ can be found by solving the following minimisation problem:

$\begin{array}{l}\min {\displaystyle \sum _{k=1}^{K_S}{s}_k{z}_k,}\text{ under the conditions that:}\hfill \\ {\displaystyle \sum _{k\in B_{qS}^l}{z}_k\ge 1},\text{ for all failed }{\psi }_{qS}^l\in {\Psi }_{qS},\hfill \\ z_k\in \{0,1\},k=1,\dots ,K_S.\hfill \end{array}$(5.1)

This is a standard binary linear optimisation problem for which algorithms are available (see e.g., Nemhauser and Wolsey 1988). The solution consists of a vector $(z_1^{\ast },\dots ,z_{K_S}^{\ast })$ of zeros and ones. The associated optimal representing set is $B^{*}=\{k:z_k^{\ast }=1\}$ and the associated contribution of $D_{\text{soft}}$ to $D$ is precisely the minimal value of problem (5.1), say

$D_{\text{soft}}^{\ast }={\displaystyle \sum _{k=1}^{K_S}{s}_k{z}_k^{\ast }}={\displaystyle \sum _{k\in B^{*}}{s}_k}.$

As in the previous case, the value $D=\lambda D_{\text{FH}}+(1-\lambda )D_{\text{soft}}^{\ast }$  is compared to $D_{\min }.$ If $D\le D_{\min },$ then the current solution is stored, otherwise it is discarded. Either way, it is meaningful in this case to continue the algorithm from the current node, because eliminating more variables may lead to a lower value of the target function. This can happen because a solution that imputes more variables typically fails fewer soft edits. Therefore, we continue the generation of branches from the current node.

The correctness of this algorithm follows from the correctness of the original algorithm of De Waal and Quere (2003) and the theory presented in Section 4. The index sets $B_q^k$ only have to be computed for the soft edits, because a subset of the variables is never considered a feasible solution to the error localisation problem when at least one of the hard edits remains failed. This means that, in every application of Theorem 1 or Theorem 2, all implied edits in ${\Psi }_{qH}$ must be contained in ${\Psi }_q^{(1)}.$ Finally, we note that the new algorithm reduces to the original algorithm of De Waal and Quere (2003) in the special case that no soft edits have been specified.

Previous | Next