| 97 | |
| 98 | template<class Card> |
| 99 | forceinline ExecStatus |
| 100 | Bnd<Card>::lbc(Space& home, int& nb, |
| 101 | HallInfo hall[], Rank rank[], int mu[], int nu[]) { |
| 102 | int n = x.size(); |
| 103 | |
| 104 | /* |
| 105 | * Let I(S) denote the number of variables whose domain intersects |
| 106 | * the set S and C(S) the number of variables whose domain is containded |
| 107 | * in S. Let further min_cap(S) be the minimal number of variables |
| 108 | * that must be assigned to values, that is |
| 109 | * min_cap(S) is the sum over all l[i] for a value v_i that is an |
| 110 | * element of S. |
| 111 | * |
| 112 | * A failure set is a set F if |
| 113 | * I(F) < min_cap(F) |
| 114 | * An unstable set is a set U if |
| 115 | * I(U) = min_cap(U) |
| 116 | * A stable set is a set S if |
| 117 | * C(S) > min_cap(S) and S intersetcs nor |
| 118 | * any failure set nor any unstable set |
| 119 | * forall unstable and failure sets |
| 120 | * |
| 121 | * failure sets determine the satisfiability of the LBC |
| 122 | * unstable sets have to be pruned |
| 123 | * stable set do not have to be pruned |
| 124 | * |
| 125 | * hall[].ps ~ stores the unstable |
| 126 | * sets that have to be pruned |
| 127 | * hall[].s ~ stores sets that must not be pruned |
| 128 | * hall[].h ~ contains stable and unstable sets |
| 129 | * hall[].d ~ contains the difference between interval bounds, i.e. |
| 130 | * the minimal capacity of the interval |
| 131 | * hall[].t ~ contains the critical capacity pointer, pointing to the |
| 132 | * values |
| 133 | */ |
| 134 | |
| 135 | // LBC lower bounds |
| 136 | |
| 137 | int i = 0; |
| 138 | int j = 0; |
| 139 | int w = 0; |
| 140 | int z = 0; |
| 141 | int v = 0; |
| 142 | |
| 143 | //initialization of the tree structure |
| 144 | int rightmost = nb + 1; // rightmost accessible value in bounds |
| 145 | int bsize = nb + 2; |
| 146 | w = rightmost; |
| 147 | |
| 148 | // test |
| 149 | // unused but uninitialized |
| 150 | hall[0].d = 0; |
| 151 | hall[0].s = 0; |
| 152 | hall[0].ps = 0; |
| 153 | |
| 154 | for (i = bsize; --i; ) { // i must not be zero |
| 155 | int pred = i - 1; |
| 156 | hall[i].s = pred; |
nothing calls this directly
no test coverage detected