Blame view

src/constraints/at_least.c 11.2 KB
94b2b13d   Pedro Roque   PHACT source
1
2
3
4
/*
 * at_least.c
 *
 *  Created on: 26/03/2017
4d26a735   Pedro Roque   Increased recogni...
5
 *      Author: pedro
94b2b13d   Pedro Roque   PHACT source
6
7
 */

94b2b13d   Pedro Roque   PHACT source
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#ifndef __OPENCL_VERSION__

#include <stddef.h>
#include <stdio.h>

#include "at_least.h"

#include "../bitmaps.h"
#include "../config.h"
#include "../variables.h"

#endif

#include "../kernels/cl_aux_functions.h"
#if CL_D_TYPE == CL_BITMAP
#include "../kernels/cl_bitmaps.h"
#elif CL_D_TYPE == CL_INTERVAL
#include  "../kernels/cl_intervals.h"
#endif
#include "../kernels/cl_constraints.h"
#include "../kernels/cl_variables.h"
#include "../kernels/cl_ttl.h"

#ifndef __OPENCL_VERSION__

/*
 * Creates a new constraint of the at_least type and return the constraint ID
 * #{i | X[i] = k} >= n
 * n - minimum number of variables in X that may contain k
 * X_ids - vector with the ID of the variables that may contain k
 * n_vs - maximum number of variables in X vector
4d26a735   Pedro Roque   Increased recogni...
41
 * k - Value that should be set in at least n variables of X
94b2b13d   Pedro Roque   PHACT source
42
43
44
45
46
47
48
 */
unsigned int c_at_least(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k) {
	unsigned int i;

	// set to include in kernel compilation
	USE_CS[AT_LEAST] = 1;
	USE_NON_CS_REIFI[AT_LEAST] = 1;
4d26a735   Pedro Roque   Increased recogni...
49
	REV = 1;
94b2b13d   Pedro Roque   PHACT source
50
51
52
53
54
55

	unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));

	for (i = 0; i < n_vs; i++) {
		c_vs[i] = X_ids[i];
	}
4d26a735   Pedro Roque   Increased recogni...
56
57

	int consts[2];
94b2b13d   Pedro Roque   PHACT source
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
	consts[0] = (int)n;
	consts[1] = (int)k;

	// creates a new generic constraint
	unsigned int c_id = c_new(c_vs, n_vs, consts, 2, -1);

	// pointers to this type of constraint functions
	CS[c_id].kind = AT_LEAST;
	CS[c_id].check_sol_f = &at_least_check;
	CS[c_id].constant_val = 0;

	free(c_vs);

	return c_id;
}

/*
 * Creates a new reified constraint of the at_least type and return the constraint ID
 * #{i | X[i] = k} >= n
 * n - minimum number of variables in X that may contain k
 * X_ids - vector with the ID of the variables that may contain k
 * n_vs - maximum number of variables in X vector
 * k - Value that should be set in at least n variables of X
4d26a735   Pedro Roque   Increased recogni...
81
 * reif_v_id - ID of the reification variable
94b2b13d   Pedro Roque   PHACT source
82
83
84
85
86
87
 */
unsigned int c_at_least_reif(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k, int reif_v_id) {
	unsigned int i;

	if (VS[reif_v_id].max > 1) {
		v_del_gt(&VS[reif_v_id], 1);
4d26a735   Pedro Roque   Increased recogni...
88
89
90
91
92
93
94
95

		if (VS[reif_v_id].n_vals == 0) {
			fprintf(stderr, "\nError: Constraint AT_LEAST_REIF makes model inconsistent at creation:\n");
			exit(-1);
		}
	}

	// set to include in kernel compilation
94b2b13d   Pedro Roque   PHACT source
96
97
98
99
100
101
102
103
	USE_CS[AT_LEAST] = 1;
	USE_CS_REIFI[AT_LEAST] = 1;
	REV = 1;

	unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));

	for (i = 0; i < n_vs; i++) {
		c_vs[i] = X_ids[i];
4d26a735   Pedro Roque   Increased recogni...
104
	}
94b2b13d   Pedro Roque   PHACT source
105
106
107
108
109
110

	int consts[2];
	consts[0] = (int)n;
	consts[1] = (int)k;

	// creates a new generic constraint
4d26a735   Pedro Roque   Increased recogni...
111
112
	unsigned int c_id = c_new(c_vs, n_vs, consts, 2, reif_v_id);

94b2b13d   Pedro Roque   PHACT source
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
	// pointers to this type of constraint functions
	CS[c_id].kind = AT_LEAST;
	CS[c_id].check_sol_f = &at_least_check;
	CS[c_id].constant_val = 0;

	free(c_vs);

	return c_id;
}

/*
 * Return true if the at_least constraint is respected or false if not
 * #{i | X[i] = k} >= n
 * c - constraint to check if is respected
 * explored - if the CSP was already explored, which mean that all the variables must already be singletons
 * */
bool at_least_check(constr* c, bool explored) {
	var** X = c->c_vs;
	var* x;
	int n = c->c_consts[0];
4d26a735   Pedro Roque   Increased recogni...
133
134
135
136
	int k = c->c_consts[1];
	int set = 0;
	unsigned int i;

94b2b13d   Pedro Roque   PHACT source
137
138
139
140
141
	for (i = 0; i < c->n_c_vs; i++) {
		x = X[i];

#if CHECK_SOL_N_VALS
		if (x->to_label && x->n_vals != 1) {
4d26a735   Pedro Roque   Increased recogni...
142
143
144
145

			if (explored) {
				fprintf(stderr, "\nError: Constraint AT_LEAST not respected:\n");

94b2b13d   Pedro Roque   PHACT source
146
				for (i = 0; i < c->n_c_vs; i++) {
4d26a735   Pedro Roque   Increased recogni...
147
148
149
150
151
152
					fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id, b_get_min_val(&c->c_vs[i]->domain_b),
							b_get_max_val(&c->c_vs[i]->domain_b),
							b_cnt_vals(&c->c_vs[i]->domain_b));
				}
			}
			return false;
94b2b13d   Pedro Roque   PHACT source
153

4d26a735   Pedro Roque   Increased recogni...
154
155
156
157
158
		} else
#endif
		if (x->min == k) {
			set++;
		}
94b2b13d   Pedro Roque   PHACT source
159
	}
94b2b13d   Pedro Roque   PHACT source
160
161
162
163
164
165

	// if less than n variables are set to k
	if (set < n) {

		if (explored) {
			fprintf(stderr, "\nError: Constraint AT_LEAST (%d) not respected:\n", c->c_id);
4d26a735   Pedro Roque   Increased recogni...
166

94b2b13d   Pedro Roque   PHACT source
167
168
			for (i = 0; i < c->n_c_vs; i++) {
				fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id, b_get_min_val(&c->c_vs[i]->domain_b),
4d26a735   Pedro Roque   Increased recogni...
169
170
171
172
173
174
175
176
177
						b_get_max_val(&c->c_vs[i]->domain_b),
						b_cnt_vals(&c->c_vs[i]->domain_b));
			}
		}
		return false;
	}
	return true;
}

94b2b13d   Pedro Roque   PHACT source
178
179
180
#endif


4d26a735   Pedro Roque   Increased recogni...
181
#if CS_AT_LEAST == 1
94b2b13d   Pedro Roque   PHACT source
182
183
184
185
186
187
188
189
190
/*
 * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_least constraint
 * #{i | X[i] = k} >= n
 * prop_ok will be set to 1 if success or to 0 if any domain became empty
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
 * vs_prop_ - all CSP variables with current step values
 * prop_v_id - variable ID to propagate
 * current_cs - constraint that should be propagated for the variable with prop_v_id ID
94b2b13d   Pedro Roque   PHACT source
191
192
193
194
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_least_prop(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok CS_IGNORE_FUNC TTL_CTR) {
94b2b13d   Pedro Roque   PHACT source
195

4d26a735   Pedro Roque   Increased recogni...
196
	int n = c_consts[0];
94b2b13d   Pedro Roque   PHACT source
197
	int k = c_consts[1];
94b2b13d   Pedro Roque   PHACT source
198
199
	int set = 0;
	int possible = 0;
4d26a735   Pedro Roque   Increased recogni...
200
	bool contains;
94b2b13d   Pedro Roque   PHACT source
201
	int x_id;
4d26a735   Pedro Roque   Increased recogni...
202
203
	bool changed = 0;
	int i;
94b2b13d   Pedro Roque   PHACT source
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

	for (i = 0; i < current_cs->n_c_vs; i++) {
		CHECK_TTL(ttl_ctr, 37)
		x_id = vs_per_c_idx[i];

		// number of variables already set to k
		if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
			set++;
			// number of variables that may be set to k
		} else {
			cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
			if (contains) {
				possible++;
			}
		}
	}

	// if there are not enough variables to set to k
	if (set + possible < n) {
		*prop_ok = 0;
		return;
	}

	// if the sum of the variables that contain k are n, assign all of them to k
	if (set + possible == n) {

		for (i = 0; possible > 0; i++) {
			x_id = vs_per_c_idx[i];

			CHECK_TTL(ttl_ctr, 38)
			if (V_N_VALS(vs_prop_[x_id]) > 1) {
				cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);

				if (contains) {
					cl_v_del_all_except_val_m(&changed, &vs_prop_[x_id], k TTL_CTR_V);
					possible--;
					v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id);
				}
			}
		}
#if CL_CS_IGNORE
		cs_ignore[current_cs->c_id] = 1;
#endif
	}
}

#if CS_R_AT_LEAST == 1
/*
 * Validate at_least constraint to be normally propagated, when reified
 * #{i | X[i] = k} >= n
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
 * vs_prop_ - all CSP variables with current step values
 * current_cs - constraint that should be propagated for the variable with prop_v_id ID
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_least_reif( CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_ CS_IGNORE_FUNC TTL_CTR) {

	int n = c_consts[0];
4d26a735   Pedro Roque   Increased recogni...
264
	int k = c_consts[1];
94b2b13d   Pedro Roque   PHACT source
265
266
267
268
	int set = 0;
	int possible = 0;
	bool contains;
	int x_id;
4d26a735   Pedro Roque   Increased recogni...
269
270
	int i;

94b2b13d   Pedro Roque   PHACT source
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
	for (i = 0; i < current_cs->n_c_vs; i++) {
		CHECK_TTL(ttl_ctr, 39)
		x_id = vs_per_c_idx[i];

		// number of variables already set to k
		if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
			set++;
			// number of variables that may be set to k
		} else {
			cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
			if (contains) {
				possible++;
			}
		}
	}

	// if there are not enough variables to set to k
	if (set + possible < n) {
		cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 1 TTL_CTR_V);
		v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));

#if CL_CS_IGNORE
		cs_ignore[current_cs->c_id] = 1;
#endif
	}

	// constraint already fixed
	if (set >= n) {
4d26a735   Pedro Roque   Increased recogni...
299
		cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 TTL_CTR_V);
94b2b13d   Pedro Roque   PHACT source
300
301
302
303
304
305
306
307
308
		v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));

#if CL_CS_IGNORE
		cs_ignore[current_cs->c_id] = 1;
#endif
	}
}

/*
4d26a735   Pedro Roque   Increased recogni...
309
 * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_least opposite constraint
94b2b13d   Pedro Roque   PHACT source
310
311
312
313
314
315
316
317
318
319
320
 * #{i | X[i] = k} < n
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
 * vs_prop_ - all CSP variables with current step values
 * prop_v_id - variable ID to propagate
 * current_cs - constraint that should be propagated for the variable with prop_v_id ID
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_least_prop_opposite(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok CS_IGNORE_FUNC TTL_CTR) {

4d26a735   Pedro Roque   Increased recogni...
321
	int n = c_consts[0];
94b2b13d   Pedro Roque   PHACT source
322
	int k = c_consts[1];
94b2b13d   Pedro Roque   PHACT source
323
324
	int set = 0;
	int possible = 0;
4d26a735   Pedro Roque   Increased recogni...
325
	bool contains;
94b2b13d   Pedro Roque   PHACT source
326
	int x_id;
4d26a735   Pedro Roque   Increased recogni...
327
328
	bool changed = 0;
	int i;
94b2b13d   Pedro Roque   PHACT source
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

	for (i = 0; i < current_cs->n_c_vs; i++) {
		CHECK_TTL(ttl_ctr, 206)
		x_id = vs_per_c_idx[i];

		// if more than n-1 variables are already set to k, return 0
		if (V_N_VALS(vs_prop_[x_id]) == 1 && V_MIN(vs_prop_[x_id]) == k) {
			if (++set >= n) {
				*prop_ok = 0;
				return;
			}
			// number of variables that may be set to k
		} else {
			cl_v_contains_val_m(&contains, &vs_prop_[x_id], k TTL_CTR_V);
			if (contains) {
				possible++;
			}
		}
	}

	// if all the variables already assigned to k are n-1, remove k from the other variables
	if (set == n - 1) {

		for (i = 0; possible > 0; i++) {
			x_id = vs_per_c_idx[i];

			CHECK_TTL(ttl_ctr, 207)
			if (V_N_VALS(vs_prop_[x_id]) > 1) {

				cl_v_del_val_m(&changed, &vs_prop_[x_id], k TTL_CTR_V);
				if (changed) {
					possible--;
					v_add_to_prop(vs_id_to_prop_, vs_prop_, x_id);
				}
			}
		}

#if CL_CS_IGNORE
		cs_ignore[current_cs->c_id] = 1;
#endif
	}
}
#endif

CUDA_FUNC void at_least_propagate(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok PROPAGATED_FUNC CS_IGNORE_FUNC TTL_CTR) {

#if CS_R_AT_LEAST == 0
	at_least_prop(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
#if CL_STATS == 1
	*propagated = true;
#endif
#elif CS_R_AT_LEAST == 1
4d26a735   Pedro Roque   Increased recogni...
382
383
384
385
386
387
388
389
390
391
392
	if (current_cs->reified == 1) {
		if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) {
			at_least_reif(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_ CS_IGNORE_CALL TTL_CTR_V);

		} else {
			if (V_MIN(vs_prop_[current_cs->reif_var_id]) == 1) {
				at_least_prop(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
			} else {
				at_least_prop_opposite(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
			}
#if CL_STATS == 1
94b2b13d   Pedro Roque   PHACT source
393
394
395
396
397
398
			*propagated = true;
#endif
		}
	} else {
		at_least_prop(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_, prop_ok CS_IGNORE_CALL TTL_CTR_V);
#if CL_STATS == 1
4d26a735   Pedro Roque   Increased recogni...
399
		*propagated = true;
94b2b13d   Pedro Roque   PHACT source
400
401
402
403
404
#endif
	}
#endif
}
#endif
4d26a735   Pedro Roque   Increased recogni...

94b2b13d   Pedro Roque   PHACT source