| 135 | |
| 136 | template<class View> |
| 137 | void cbsdistinct(Space&, unsigned int prop_id, const ViewArray<View>& x, |
| 138 | Propagator::SendMarginal send) { |
| 139 | // Computation of Minc and Brégman and Liang and Bai upper bounds for |
| 140 | // the permanent of the whole constraint |
| 141 | struct UB { |
| 142 | double minc; |
| 143 | double liangBai; |
| 144 | }; |
| 145 | |
| 146 | UB ub{1,1}; |
| 147 | for (int i=0; i<x.size(); i++) { |
| 148 | unsigned int s = x[i].size(); |
| 149 | if ((s >= MAX_MINC_FACTORS) || (s >= WIDTH_LIANG_BAI_FACTORS)) |
| 150 | throw Gecode::Exception("Int::Distinct::cbsdistinct", |
| 151 | "Variable cardinality too big for using counting-based" |
| 152 | "search with distinct constraints"); |
| 153 | ub.minc *= getMincFactor(s); |
| 154 | ub.liangBai *= getLiangBaiFactor(i, s); |
| 155 | } |
| 156 | |
| 157 | // Minimum and maximum value of the union of all variable domains |
| 158 | int minVal = std::numeric_limits<int>::max(); |
| 159 | int maxVal = std::numeric_limits<int>::min(); |
| 160 | for (const auto& v : x) { |
| 161 | if (v.assigned()) continue; |
| 162 | minVal = std::min(v.min(), minVal); |
| 163 | maxVal = std::max(v.max(), maxVal); |
| 164 | } |
| 165 | |
| 166 | // For each possible value, we compute the update we have to apply to the |
| 167 | // permanent of the whole constraint to get the new solution count |
| 168 | Region r; |
| 169 | ValToUpdate valToUpdate(x, minVal, maxVal, r); |
| 170 | |
| 171 | // Preallocated memory for holding solution counts for all values of a |
| 172 | // variable during computation |
| 173 | double* solCounts = r.alloc<double>(maxVal - minVal + 1); |
| 174 | |
| 175 | for (int i=0; i<x.size(); i++) { |
| 176 | if (x[i].assigned()) continue; |
| 177 | |
| 178 | // Normalization constant for keeping densities values between 0 and 1 |
| 179 | double normalization = 0; |
| 180 | // We calculate the density for every possible value assignment |
| 181 | for (ViewValues<View> val(x[i]); val(); ++val) { |
| 182 | UB localUB = ub; |
| 183 | int v = val.val(); |
| 184 | unsigned int s = x[i].size(); |
| 185 | |
| 186 | // We update both upper bounds according to the assigned value, yielding |
| 187 | // two new estimations for the upper bound |
| 188 | localUB.minc *= valToUpdate.getMincUpdate(v, s); |
| 189 | localUB.liangBai *= valToUpdate.getLiangUpdate(v, i, s); |
| 190 | |
| 191 | // We take the lower upper bound as our estimation for the permanent |
| 192 | double lowerUB = std::min(localUB.minc, ::sqrt(localUB.liangBai)); |
| 193 | solCounts[val.val() - minVal] = lowerUB; |
| 194 | normalization += lowerUB; |
no test coverage detected