Blame view

src/constraints/at_most.c 11.1 KB
94b2b13d   Pedro Roque   PHACT source
1
2
3
4
/*
 * at_most.c
 *
 *  Created on: 26/03/2017
4d26a735   Pedro Roque   Increased recogni...
5
 *      Author: pedro
94b2b13d   Pedro Roque   PHACT source
6
7
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_most.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_most type and return the constraint ID
 * #{i | X[i] = k} <= n
 * n - maximum 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 most n variables of X
 */
4d26a735   Pedro Roque   Increased recogni...
41
unsigned int c_at_most(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k) {
94b2b13d   Pedro Roque   PHACT source
42
43
44
45
46
47
48
	unsigned int i;

	// set to include in kernel compilation
	USE_CS[AT_MOST] = 1;
	USE_NON_CS_REIFI[AT_MOST] = 1;
	REV = 1;

4d26a735   Pedro Roque   Increased recogni...
49
	unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));
94b2b13d   Pedro Roque   PHACT source
50
51
52
53
54
55

	for (i = 0; i < n_vs; i++) {
		c_vs[i] = X_ids[i];
	}

	int consts[2];
4d26a735   Pedro Roque   Increased recogni...
56
57
	consts[0] = (int)n;
	consts[1] = (int)k;
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

	// 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_MOST;
	CS[c_id].check_sol_f = &at_most_check;
	CS[c_id].constant_val = 0;

	free(c_vs);

	return c_id;
}

/*
 * Creates a new reified constraint of the at_most type and return the constraint ID
 * #{i | X[i] = k} <= n
 * n - maximum 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 most n variables of X
 * reif_v_id - ID of the reification variable
 */
4d26a735   Pedro Roque   Increased recogni...
81
unsigned int c_at_most_reif(unsigned int n, unsigned int* X_ids, unsigned int n_vs, unsigned int k, int reif_v_id) {
94b2b13d   Pedro Roque   PHACT source
82
83
84
85
86
87
	unsigned int i;

	if (VS[reif_v_id].max > 1) {
		v_del_gt(&VS[reif_v_id], 1);

		if (VS[reif_v_id].n_vals == 0) {
4d26a735   Pedro Roque   Increased recogni...
88
89
90
91
92
93
94
95
			fprintf(stderr, "\nError: Constraint AT_MOST_REIF makes model inconsistent at creation:\n");
			exit(-1);
		}
	}

	// set to include in kernel compilation
	USE_CS[AT_MOST] = 1;
	USE_CS_REIFI[AT_MOST] = 1;
94b2b13d   Pedro Roque   PHACT source
96
97
98
99
100
101
102
103
	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
	int consts[2];
94b2b13d   Pedro Roque   PHACT source
105
106
107
108
109
110
	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, reif_v_id);

4d26a735   Pedro Roque   Increased recogni...
111
112
	// pointers to this type of constraint functions
	CS[c_id].kind = AT_MOST;
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
	CS[c_id].check_sol_f = &at_most_check;
	CS[c_id].constant_val = 0;

	free(c_vs);

	return c_id;
}

/*
 * Return true if the at_most 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_most_check(constr* c, bool explored) {
	var** X = c->c_vs;
	var* x;
	int n = c->c_consts[0];
	int k = c->c_consts[1];
	int set = 0;
4d26a735   Pedro Roque   Increased recogni...
133
134
135
136
	unsigned int i;

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

#if CHECK_SOL_N_VALS
		if (x->to_label && x->n_vals != 1) {

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

				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),
94b2b13d   Pedro Roque   PHACT source
146
							b_get_max_val(&c->c_vs[i]->domain_b),
4d26a735   Pedro Roque   Increased recogni...
147
148
149
150
151
152
							b_cnt_vals(&c->c_vs[i]->domain_b));
				}
			}
			return false;

		} else
94b2b13d   Pedro Roque   PHACT source
153
#endif
4d26a735   Pedro Roque   Increased recogni...
154
155

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

	// if more than n variables are set to k
	if (set > n) {

		if (explored) {
			fprintf(stderr, "\nError: Constraint AT_MOST (%d) not respected:\n", c->c_id);

4d26a735   Pedro Roque   Increased recogni...
166
			for (i = 0; i < c->n_c_vs; i++) {
94b2b13d   Pedro Roque   PHACT source
167
168
				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));
4d26a735   Pedro Roque   Increased recogni...
169
170
171
172
173
174
175
176
177
			}
		}
		return false;
	}
	return true;
}

#endif

94b2b13d   Pedro Roque   PHACT source
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#if CS_AT_MOST == 1
/*
 * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_most 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
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_most_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) {

	int n = c_consts[0];
	int k = c_consts[1];
94b2b13d   Pedro Roque   PHACT source
195
	int set = 0;
4d26a735   Pedro Roque   Increased recogni...
196
	int possible = 0;
94b2b13d   Pedro Roque   PHACT source
197
	bool contains;
94b2b13d   Pedro Roque   PHACT source
198
199
	int x_id;
	bool changed = 0;
4d26a735   Pedro Roque   Increased recogni...
200
	int i;
94b2b13d   Pedro Roque   PHACT source
201

4d26a735   Pedro Roque   Increased recogni...
202
203
	for (i = 0; i < current_cs->n_c_vs; i++) {
		CHECK_TTL(ttl_ctr, 40)
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
		x_id = vs_per_c_idx[i];

		// if more than n 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, remove k from the other variables
	if (set == n) {

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

			CHECK_TTL(ttl_ctr, 41)
			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
	}
}

#if CS_R_AT_MOST == 1
/*
 * Validate at_most 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_most_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];
	int k = c_consts[1];
	int set = 0;
	int possible = 0;
4d26a735   Pedro Roque   Increased recogni...
260
	bool contains;
94b2b13d   Pedro Roque   PHACT source
261
262
263
264
	int x_id;
	int i;

	for (i = 0; i < current_cs->n_c_vs; i++) {
4d26a735   Pedro Roque   Increased recogni...
265
266
		CHECK_TTL(ttl_ctr, 42)
		x_id = vs_per_c_idx[i];
94b2b13d   Pedro Roque   PHACT source
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283

		// if more than n 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) {
				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

				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++;
4d26a735   Pedro Roque   Increased recogni...
284
				}
94b2b13d   Pedro Roque   PHACT source
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
			}
		}
	}

	// constraint already fixed
	if (set + possible <= n) {
		cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 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
	}
}

/*
 * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_most opposite constraint
 * #{i | X[i] = k} > n
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
4d26a735   Pedro Roque   Increased recogni...
304
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
94b2b13d   Pedro Roque   PHACT source
305
306
307
308
309
310
311
312
313
314
315
316
317
 * 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_most_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) {

	int n = c_consts[0];
	int k = c_consts[1];
	int set = 0;
	int possible = 0;
	bool contains;
94b2b13d   Pedro Roque   PHACT source
318
319
	int x_id;
	bool changed = 0;
4d26a735   Pedro Roque   Increased recogni...
320
	int i;
94b2b13d   Pedro Roque   PHACT source
321

4d26a735   Pedro Roque   Increased recogni...
322
323
	for (i = 0; i < current_cs->n_c_vs; i++) {
		CHECK_TTL(ttl_ctr, 206)
94b2b13d   Pedro Roque   PHACT source
324
325
326
327
328
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
		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+1, assign all of them to k
	if (set + possible == n + 1) {

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

			CHECK_TTL(ttl_ctr, 205)
			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
	}
}

#endif

CUDA_FUNC void at_most_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_MOST == 0
	at_most_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_MOST == 1
	if (current_cs->reified == 1) {
		if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) {
			at_most_reif(vs_per_c_idx, c_consts, vs_prop_, current_cs, vs_id_to_prop_ CS_IGNORE_CALL TTL_CTR_V);
4d26a735   Pedro Roque   Increased recogni...
381
382
383
384
385
386
387
388
389
390
391

		} else {
			if (V_MIN(vs_prop_[current_cs->reif_var_id]) == 1) {
				at_most_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_most_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
			*propagated = true;
#endif
		}
94b2b13d   Pedro Roque   PHACT source
392
393
394
395
396
397
	} else {
		at_most_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
	}
4d26a735   Pedro Roque   Increased recogni...
398
#endif
94b2b13d   Pedro Roque   PHACT source
399
400
401
}

#endif