1 #include <map>
2 #include <chuffed/vars/int-var.h>
3 #include <chuffed/mip/mip.h>
4 #include <sstream>
5
6 // When set, branch variable (first_fail) and value (indomain_median,
7 // indomain_split, indomain_reverse_split) specifications will count domain
8 // sizes by the number of active values rather than the bounds (max-min).
9 // (There is not too much penalty if INT_DOMAIN_LIST enabled in int-var.h).
10 #define INT_BRANCH_HOLES 0
11
12 using namespace std;
13
14 map<int,IntVar*> ic_map;
15
16 extern std::map<IntVar*, std::string> intVarString;
17
IntVar(int _min,int _max)18 IntVar::IntVar(int _min, int _max) :
19 var_id(engine.vars.size())
20 , min(_min)
21 , max(_max)
22 , min0(_min)
23 , max0(_max)
24 , shadow_val(0)
25 , in_scip(false)
26 , all_in_scip(true)
27 , should_be_learnable(true)
28 , should_be_decidable(true)
29 , vals(NULL)
30 , preferred_val(PV_MIN)
31 , activity(0)
32 , in_queue(false)
33 {
34 assert(min_limit <= min && min <= max && max <= max_limit);
35 engine.vars.push(this);
36 changes = EVENT_C | EVENT_L | EVENT_U;
37 if (isFixed()) changes |= EVENT_F;
38 }
39
40 // Allocate enough memory to specialise IntVar later using the same memory block
newIntVar(int min,int max)41 IntVar* newIntVar(int min, int max) {
42 size_t size = sizeof(IntVar);
43 if (sizeof(IntVarEL) > size) size = sizeof(IntVarEL);
44 if (sizeof(IntVarLL) > size) size = sizeof(IntVarLL);
45 if (sizeof(IntVarSL) > size) size = sizeof(IntVarSL);
46 void *mem = malloc(size);
47 IntVar *var = new (mem) IntVar(min, max);
48 return var;
49 }
50
getConstant(int v)51 IntVar* getConstant(int v) {
52 map<int,IntVar*>::iterator it = ic_map.find(v);
53 if (it != ic_map.end()) return it->second;
54 IntVar *var = newIntVar(v,v);
55
56 std::stringstream ss;
57 ss << "constant_" << v;
58 intVarString[var] = ss.str();
59
60 var->specialiseToEL();
61 ic_map.insert(pair<int,IntVar*>(v, var));
62
63
64 return var;
65 }
66
specialiseToEL()67 void IntVar::specialiseToEL() {
68 switch (getType()) {
69 case INT_VAR_EL: return;
70 case INT_VAR_SL: return;
71 case INT_VAR: new (this) IntVarEL(*((IntVar*) this)); break;
72 default: NEVER;
73 }
74 }
75
specialiseToLL()76 void IntVar::specialiseToLL() {
77 switch (getType()) {
78 case INT_VAR_EL: return;
79 case INT_VAR_SL: return;
80 case INT_VAR: new (this) IntVarLL(*((IntVar*) this)); break;
81 default: NEVER;
82 }
83 }
84
specialiseToSL(vec<int> & values)85 void IntVar::specialiseToSL(vec<int>& values) {
86 if (getType() == INT_VAR_EL) return;
87 if (getType() == INT_VAR_SL) return;
88 assert(getType() == INT_VAR);
89
90 vec<int> v = values;
91 std::sort((int*) v, (int*) v + v.size());
92 int i, j;
93 for (i = j = 0; i < v.size(); i++) {
94 if (i == 0 || v[i] != v[i-1]) v[j++] = v[i];
95 }
96 v.resize(j);
97
98
99 // for (int i = 0; i < values.size(); i++) printf("%d ", values[i]);
100 // printf("\n");
101
102 // determine whether it is sparse or dense
103 if (v.last()-v[0] >= v.size() * mylog2(v.size())) {
104 // fprintf(stderr, "SL\n");
105 new (this) IntVarSL(*((IntVar*) this), v);
106 } else {
107 new (this) IntVarEL(*((IntVar*) this));
108 if (!allowSet(v)) TL_FAIL();
109 }
110 }
111
initVals(bool optional)112 void IntVar::initVals(bool optional) {
113 if (vals) return;
114 if (min == min_limit || max == max_limit) {
115 if (optional) return;
116 CHUFFED_ERROR("Cannot initialise vals in unbounded IntVar\n");
117 }
118 vals = (Tchar*) malloc((max-min+2) * sizeof(Tchar));
119 if (!vals) { perror("malloc()"); exit(1); }
120 memset(vals, 1, max-min+2);
121 if (!(vals -= min)) vals++; // Hack to make vals != NULL whenever it's allocated
122 #if INT_DOMAIN_LIST
123 vals_list = (Tint*) malloc(2*(max-min) * sizeof(Tint));
124 if (!vals_list) { perror("malloc()"); exit(1); }
125 vals_list -= 2*min+1;
126 for (int i = min; i < max; ++i) {
127 vals_list[2*i+1].v = i+1; // forward link
128 vals_list[2*i+2].v = i; // backward link from next value
129 }
130 vals_count.v = max+1-min;
131 #endif
132 }
133
attach(Propagator * p,int pos,int eflags)134 void IntVar::attach(Propagator *p, int pos, int eflags) {
135 if (isFixed()) p->wakeup(pos, eflags);
136 else pinfo.push(PropInfo(p, pos, eflags));
137 }
138
wakePropagators()139 void IntVar::wakePropagators() {
140 for (int i = pinfo.size(); i--; ) {
141 PropInfo& pi = pinfo[i];
142 if ((pi.eflags & changes) == 0) continue;
143 if (pi.p->satisfied) continue;
144 if (pi.p == engine.last_prop) continue;
145 pi.p->wakeup(pi.pos, changes);
146 }
147 clearPropState();
148 }
149
simplifyWatches()150 int IntVar::simplifyWatches() {
151 int i, j;
152 for (i = j = 0; i < pinfo.size(); i++) {
153 if (!pinfo[i].p->satisfied) pinfo[j++] = pinfo[i];
154 }
155 pinfo.resize(j);
156 return j;
157 }
158
159 //-----
160 // Branching stuff
161
getScore(VarBranch vb)162 double IntVar::getScore(VarBranch vb) {
163 switch(vb) {
164 case VAR_MIN_MIN : return -min;
165 case VAR_MIN_MAX : return min;
166 case VAR_MAX_MIN : return -max;
167 case VAR_MAX_MAX : return max;
168 #if INT_BRANCH_HOLES
169 // note slight inconsistency, if INT_BRANCH_HOLES=0 then we
170 // use the domain size-1, same behaviour but more efficient?
171 case VAR_SIZE_MIN : return vals ? -size() : min - (max + 1);
172 case VAR_SIZE_MAX : return vals ? size() : max + 1 - min;
173 #else
174 case VAR_SIZE_MIN : return min-max;
175 case VAR_SIZE_MAX : return max-min;
176 #endif
177 case VAR_DEGREE_MIN : return -pinfo.size();
178 case VAR_DEGREE_MAX : return pinfo.size();
179 case VAR_REDUCED_COST : return mip->getRC(this);
180 case VAR_ACTIVITY : return activity;
181 case VAR_REGRET_MIN_MAX: return isFixed() ? 0 : (vals ? *++begin() - *begin() : 1);
182 default: NOT_SUPPORTED;
183 }
184 }
185
branch()186 DecInfo* IntVar::branch() {
187 // vec<int> possible;
188 // for (int i = min; i <= max; i++) if (indomain(i)) possible.push(i);
189 // return new DecInfo(this, possible[rand()%possible.size()], 1);
190
191
192 switch (preferred_val) {
193 case PV_MIN : return new DecInfo(this, min, 1);
194 case PV_MAX : return new DecInfo(this, max, 1);
195 #if INT_BRANCH_HOLES
196 // note slight inconsistency, if INT_BRANCH_HOLES=0 then we
197 // round down rather than up (vice versa for PV_SPLIT_MAX),
198 // should probably revisit this and make them consistent
199 case PV_SPLIT_MIN : {
200 if (!vals)
201 return new DecInfo(this, min + (max - min) / 2, 3);
202 int values = (size()- 1) / 2;
203 iterator j = begin();
204 for (int i = 0; i < values; ++i)
205 ++j;
206 return new DecInfo(this, *j, 3);
207 }
208 case PV_SPLIT_MAX : {
209 if (!vals)
210 return new DecInfo(this, min + (max - min - 1) / 2, 2);
211 int values = size() / 2;
212 iterator j = begin();
213 for (int i = 0; i < values; ++i)
214 ++j;
215 return new DecInfo(this, *j, 2);
216 }
217 case PV_MEDIAN: {
218 if (!vals)
219 return new DecInfo(this, min + (max - min) / 2, 1);
220 int values = (size() - 1) / 2;
221 iterator j = begin();
222 for (int i = 0; i < values; ++i)
223 ++j;
224 return new DecInfo(this, *j, 1);
225 }
226 #else
227 case PV_SPLIT_MIN:
228 return new DecInfo(this, min+(max-min-1)/2, 3);
229 case PV_SPLIT_MAX:
230 return new DecInfo(this, min+(max-min)/2, 2);
231 case PV_MEDIAN:
232 if (!vals) {
233 CHUFFED_ERROR("Median value selection is not supported this variable.\n");
234 }
235 else {
236 int values = (size() - 1) / 2;
237 iterator j = begin();
238 for (int i = 0; i < values; ++i)
239 ++j;
240 return new DecInfo(this, *j, 1);
241 }
242 #endif
243 default: NEVER;
244 }
245 }
246
247 //-----
248 // Domain change stuff
249
250 #if !INT_DOMAIN_LIST
updateMin()251 inline void IntVar::updateMin() {
252 int v = min;
253 if (!vals[v]) {
254 while (!vals[v]) v++;
255 min = v;
256 changes |= EVENT_C | EVENT_L;
257 }
258 }
259
updateMax()260 inline void IntVar::updateMax() {
261 int v = max;
262 if (!vals[v]) {
263 while (!vals[v]) v--;
264 max = v;
265 changes |= EVENT_C | EVENT_U;
266 }
267 }
268 #endif
269
updateFixed()270 inline void IntVar::updateFixed() {
271 if (isFixed()) changes |= EVENT_F;
272 }
273
setMin(int64_t v,Reason r,bool channel)274 bool IntVar::setMin(int64_t v, Reason r, bool channel) {
275 assert(setMinNotR(v));
276 if (v > max) return false;
277 #if INT_DOMAIN_LIST
278 if (vals) {
279 int i;
280 int j = vals_count;
281 for (i = min; i < v; i = vals_list[2*i+1])
282 --j;
283 min = i;
284 vals_count = j;
285 }
286 else
287 min = v;
288 changes |= EVENT_C | EVENT_L;
289 #else
290 min = v; changes |= EVENT_C | EVENT_L;
291 if (vals) updateMin();
292 #endif
293 updateFixed();
294 pushInQueue();
295 return true;
296 }
297
setMax(int64_t v,Reason r,bool channel)298 bool IntVar::setMax(int64_t v, Reason r, bool channel) {
299 assert(setMaxNotR(v));
300 if (v < min) return false;
301 #if INT_DOMAIN_LIST
302 if (vals) {
303 int i;
304 int j = vals_count;
305 for (i = max; i > v; i = vals_list[2*i])
306 --j;
307 max = i;
308 vals_count = j;
309 }
310 else
311 max = v;
312 changes |= EVENT_C | EVENT_U;
313 #else
314 max = v; changes |= EVENT_C | EVENT_U;
315 if (vals) updateMax();
316 #endif
317 updateFixed();
318 pushInQueue();
319 return true;
320 }
321
setVal(int64_t v,Reason r,bool channel)322 bool IntVar::setVal(int64_t v, Reason r, bool channel) {
323 assert(setValNotR(v));
324 if (!indomain(v)) return false;
325 if (min < v) { min = v; changes |= EVENT_C | EVENT_L | EVENT_F; }
326 if (max > v) { max = v; changes |= EVENT_C | EVENT_U | EVENT_F; }
327 #if INT_DOMAIN_LIST
328 if (vals)
329 vals_count = 1;
330 #endif
331 pushInQueue();
332 return true;
333 }
334
remVal(int64_t v,Reason r,bool channel)335 bool IntVar::remVal(int64_t v, Reason r, bool channel) {
336 assert(remValNotR(v));
337 if (isFixed()) return false;
338 if (!vals) {
339 if (!engine.finished_init) NEVER;
340 return true;
341 }
342 #if INT_DOMAIN_LIST
343 if (v == min) {
344 min = vals_list[2*min+1];
345 changes |= EVENT_C | EVENT_L;
346 }
347 else if (v == max) {
348 max = vals_list[2*max];
349 changes |= EVENT_C | EVENT_U;
350 }
351 else {
352 vals[v] = 0;
353 vals_list[vals_list[2*v]*2+1] = vals_list[2*v+1];
354 vals_list[vals_list[2*v+1]*2] = vals_list[2*v];
355 changes |= EVENT_C;
356 }
357 --vals_count;
358 #else
359 vals[v] = 0; changes |= EVENT_C;
360 updateMin();
361 updateMax();
362 #endif
363 updateFixed();
364 pushInQueue();
365 return true;
366 }
367
368 // Assumes v is sorted
allowSet(vec<int> & v,Reason r,bool channel)369 bool IntVar::allowSet(vec<int>& v, Reason r, bool channel) {
370 initVals();
371 if (!vals && !engine.finished_init) NOT_SUPPORTED;
372 int i = 0;
373 int m = min;
374 while (i < v.size() && v[i] < m) i++;
375 for ( ; i < v.size(); i++) {
376 for ( ; m < v[i]; m++) {
377 if (m > max) return true;
378 if (remValNotR(m)) if (!remVal(m, r, channel)) return false;
379 }
380 m = v[i]+1;
381 }
382 for ( ; m <= max; m++) {
383 if (remValNotR(m)) if (!remVal(m, r, channel)) return false;
384 }
385 return true;
386 }
387