1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file implics.c
17 * @ingroup OTHER_CFILES
18 * @brief methods for implications, variable bounds, and clique tables
19 * @author Tobias Achterberg
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "scip/event.h"
25 #include "scip/implics.h"
26 #include "scip/misc.h"
27 #include "scip/pub_implics.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_misc_sort.h"
31 #include "scip/pub_var.h"
32 #include "scip/set.h"
33 #include "scip/struct_implics.h"
34 #include "scip/struct_set.h"
35 #include "scip/struct_stat.h"
36 #include "scip/var.h"
37
38
39
40 /*
41 * methods for variable bounds
42 */
43
44 /** creates a variable bounds data structure */
45 static
46 SCIP_RETCODE vboundsCreate(
47 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
48 BMS_BLKMEM* blkmem /**< block memory */
49 )
50 {
51 assert(vbounds != NULL);
52
53 SCIP_ALLOC( BMSallocBlockMemory(blkmem, vbounds) );
54 (*vbounds)->vars = NULL;
55 (*vbounds)->coefs = NULL;
56 (*vbounds)->constants = NULL;
57 (*vbounds)->len = 0;
58 (*vbounds)->size = 0;
59
60 return SCIP_OKAY;
61 }
62
63 /** frees a variable bounds data structure */
64 void SCIPvboundsFree(
65 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
66 BMS_BLKMEM* blkmem /**< block memory */
67 )
68 {
69 assert(vbounds != NULL);
70
71 if( *vbounds != NULL )
72 {
73 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->vars, (*vbounds)->size);
74 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->coefs, (*vbounds)->size);
75 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->constants, (*vbounds)->size);
76 BMSfreeBlockMemory(blkmem, vbounds);
77 }
78 }
79
80 /** ensures, that variable bounds arrays can store at least num entries */
81 static
82 SCIP_RETCODE vboundsEnsureSize(
83 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
84 BMS_BLKMEM* blkmem, /**< block memory */
85 SCIP_SET* set, /**< global SCIP settings */
86 int num /**< minimum number of entries to store */
87 )
88 {
89 assert(vbounds != NULL);
90
91 /* create variable bounds data structure, if not yet existing */
92 if( *vbounds == NULL )
93 {
94 SCIP_CALL( vboundsCreate(vbounds, blkmem) );
95 }
96 assert(*vbounds != NULL);
97 assert((*vbounds)->len <= (*vbounds)->size);
98
99 if( num > (*vbounds)->size )
100 {
101 int newsize;
102
103 newsize = SCIPsetCalcMemGrowSize(set, num);
104 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->vars, (*vbounds)->size, newsize) );
105 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->coefs, (*vbounds)->size, newsize) );
106 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->constants, (*vbounds)->size, newsize) );
107 (*vbounds)->size = newsize;
108 }
109 assert(num <= (*vbounds)->size);
110
111 return SCIP_OKAY;
112 }
113
114 /** binary searches the insertion position of the given variable in the vbounds data structure */
115 static
116 SCIP_RETCODE vboundsSearchPos(
117 SCIP_VBOUNDS* vbounds, /**< variable bounds data structure, or NULL */
118 SCIP_VAR* var, /**< variable to search in vbounds data structure */
119 SCIP_Bool negativecoef, /**< is coefficient b negative? */
120 int* insertpos, /**< pointer to store position where to insert new entry */
121 SCIP_Bool* found /**< pointer to store whether the same variable was found at the returned pos */
122 )
123 {
124 SCIP_Bool exists;
125 int pos;
126
127 assert(insertpos != NULL);
128 assert(found != NULL);
129
130 /* check for empty vbounds data */
131 if( vbounds == NULL )
132 {
133 *insertpos = 0;
134 *found = FALSE;
135 return SCIP_OKAY;
136 }
137 assert(vbounds->len >= 0);
138
139 /* binary search for the given variable */
140 exists = SCIPsortedvecFindPtr((void**)vbounds->vars, SCIPvarComp, var, vbounds->len, &pos);
141
142 if( exists )
143 {
144 /* we found the variable: check if the sign of the coefficient matches */
145 assert(var == vbounds->vars[pos]);
146 if( (vbounds->coefs[pos] < 0.0) == negativecoef )
147 {
148 /* the variable exists with the same sign at the current position */
149 *insertpos = pos;
150 *found = TRUE;
151 }
152 else if( negativecoef )
153 {
154 assert(vbounds->coefs[pos] > 0.0);
155 if( pos+1 < vbounds->len && vbounds->vars[pos+1] == var )
156 {
157 /* the variable exists with the desired sign at the next position */
158 assert(vbounds->coefs[pos+1] < 0.0);
159 *insertpos = pos+1;
160 *found = TRUE;
161 }
162 else
163 {
164 /* the negative coefficient should be inserted to the right of the positive one */
165 *insertpos = pos+1;
166 *found = FALSE;
167 }
168 }
169 else
170 {
171 assert(vbounds->coefs[pos] < 0.0);
172 if( pos-1 >= 0 && vbounds->vars[pos-1] == var )
173 {
174 /* the variable exists with the desired sign at the previous position */
175 assert(vbounds->coefs[pos-1] > 0.0);
176 *insertpos = pos-1;
177 *found = TRUE;
178 }
179 else
180 {
181 /* the positive coefficient should be inserted to the left of the negative one */
182 *insertpos = pos;
183 *found = FALSE;
184 }
185 }
186 }
187 else
188 {
189 *insertpos = pos;
190 *found = FALSE;
191 }
192
193 return SCIP_OKAY;
194 }
195
196 /** adds a variable bound to the variable bounds data structure */
197 SCIP_RETCODE SCIPvboundsAdd(
198 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
199 BMS_BLKMEM* blkmem, /**< block memory */
200 SCIP_SET* set, /**< global SCIP settings */
201 SCIP_BOUNDTYPE vboundtype, /**< type of variable bound (LOWER or UPPER) */
202 SCIP_VAR* var, /**< variable z in x <= b*z + d or x >= b*z + d */
203 SCIP_Real coef, /**< coefficient b in x <= b*z + d or x >= b*z + d */
204 SCIP_Real constant, /**< constant d in x <= b*z + d or x >= b*z + d */
205 SCIP_Bool* added /**< pointer to store whether the variable bound was added */
206 )
207 {
208 int insertpos;
209 SCIP_Bool found;
210
211 assert(vbounds != NULL);
212 assert(var != NULL);
213 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
214 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
215 assert(added != NULL);
216 assert(!SCIPsetIsZero(set, coef));
217
218 *added = FALSE;
219
220 /* identify insertion position of variable */
221 SCIP_CALL( vboundsSearchPos(*vbounds, var, (coef < 0.0), &insertpos, &found) );
222 if( found )
223 {
224 /* the same variable already exists in the vbounds data structure: use the better vbound */
225 assert(*vbounds != NULL);
226 assert(0 <= insertpos && insertpos < (*vbounds)->len);
227 assert((*vbounds)->vars[insertpos] == var);
228 assert(((*vbounds)->coefs[insertpos] < 0.0) == (coef < 0.0));
229
230 if( vboundtype == SCIP_BOUNDTYPE_UPPER )
231 {
232 if( constant + MIN(coef, 0.0) < (*vbounds)->constants[insertpos] + MIN((*vbounds)->coefs[insertpos], 0.0) )
233 {
234 (*vbounds)->coefs[insertpos] = coef;
235 (*vbounds)->constants[insertpos] = constant;
236 *added = TRUE;
237 }
238 }
239 else
240 {
241 if( constant + MAX(coef, 0.0) > (*vbounds)->constants[insertpos] + MAX((*vbounds)->coefs[insertpos], 0.0) )
242 {
243 (*vbounds)->coefs[insertpos] = coef;
244 (*vbounds)->constants[insertpos] = constant;
245 *added = TRUE;
246 }
247 }
248 }
249 else
250 {
251 int i;
252
253 /* the given variable does not yet exist in the vbounds */
254 SCIP_CALL( vboundsEnsureSize(vbounds, blkmem, set, *vbounds != NULL ? (*vbounds)->len+1 : 1) );
255 assert(*vbounds != NULL);
256 assert(0 <= insertpos && insertpos <= (*vbounds)->len);
257 assert(0 <= insertpos && insertpos < (*vbounds)->size);
258
259 /* insert variable at the correct position */
260 for( i = (*vbounds)->len; i > insertpos; --i )
261 {
262 assert(!SCIPsetIsZero(set, (*vbounds)->coefs[i-1]));
263 (*vbounds)->vars[i] = (*vbounds)->vars[i-1];
264 (*vbounds)->coefs[i] = (*vbounds)->coefs[i-1];
265 (*vbounds)->constants[i] = (*vbounds)->constants[i-1];
266 }
267 assert(!SCIPsetIsZero(set, coef));
268 (*vbounds)->vars[insertpos] = var;
269 (*vbounds)->coefs[insertpos] = coef;
270 (*vbounds)->constants[insertpos] = constant;
271 (*vbounds)->len++;
272 *added = TRUE;
273 }
274
275 return SCIP_OKAY;
276 }
277
278 /** removes from variable x a variable bound x >=/<= b*z + d with binary or integer z */
279 SCIP_RETCODE SCIPvboundsDel(
280 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
281 BMS_BLKMEM* blkmem, /**< block memory */
282 SCIP_VAR* vbdvar, /**< variable z in x >=/<= b*z + d */
283 SCIP_Bool negativecoef /**< is coefficient b negative? */
284 )
285 {
286 SCIP_Bool found;
287 int pos;
288 int i;
289
290 assert(vbounds != NULL);
291 assert(*vbounds != NULL);
292
293 /* searches for variable z in variable bounds of x */
294 SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) );
295 if( !found )
296 return SCIP_OKAY;
297
298 assert(0 <= pos && pos < (*vbounds)->len);
299 assert((*vbounds)->vars[pos] == vbdvar);
300 assert(((*vbounds)->coefs[pos] < 0.0) == negativecoef);
301
302 /* removes z from variable bounds of x */
303 for( i = pos; i < (*vbounds)->len - 1; i++ )
304 {
305 (*vbounds)->vars[i] = (*vbounds)->vars[i+1];
306 (*vbounds)->coefs[i] = (*vbounds)->coefs[i+1];
307 (*vbounds)->constants[i] = (*vbounds)->constants[i+1];
308 }
309 (*vbounds)->len--;
310
311 #ifndef NDEBUG
312 SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) );
313 assert(!found);
314 #endif
315
316 /* free vbounds data structure, if it is empty */
317 if( (*vbounds)->len == 0 )
318 SCIPvboundsFree(vbounds, blkmem);
319
320 return SCIP_OKAY; /*lint !e438*/
321 }
322
323 /** reduces the number of variable bounds stored in the given variable bounds data structure */
324 void SCIPvboundsShrink(
325 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
326 BMS_BLKMEM* blkmem, /**< block memory */
327 int newnvbds /**< new number of variable bounds */
328 )
329 {
330 assert(vbounds != NULL);
331 assert(*vbounds != NULL);
332 assert(newnvbds <= (*vbounds)->len);
333
334 if( newnvbds == 0 )
335 SCIPvboundsFree(vbounds, blkmem);
336 else
337 (*vbounds)->len = newnvbds;
338 }
339
340
341
342
343 /*
344 * methods for implications
345 */
346
347 #ifndef NDEBUG
348 /** comparator function for implication variables in the implication data structure */
349 static
350 SCIP_DECL_SORTPTRCOMP(compVars)
351 { /*lint --e{715}*/
352 SCIP_VAR* var1;
353 SCIP_VAR* var2;
354 int var1idx;
355 int var2idx;
356
357 var1 = (SCIP_VAR*)elem1;
358 var2 = (SCIP_VAR*)elem2;
359 assert(var1 != NULL);
360 assert(var2 != NULL);
361 var1idx = SCIPvarGetIndex(var1);
362 var2idx = SCIPvarGetIndex(var2);
363
364 if( var1idx < var2idx )
365 return -1;
366 else if( var1idx > var2idx )
367 return +1;
368 else
369 return 0;
370 }
371
372 /** performs integrity check on implications data structure */
373 static
374 void checkImplics(
375 SCIP_IMPLICS* implics /**< implications data structure */
376 )
377 {
378 SCIP_Bool varfixing;
379
380 if( implics == NULL )
381 return;
382
383 varfixing = FALSE;
384 do
385 {
386 SCIP_VAR** vars;
387 SCIP_BOUNDTYPE* types;
388 int nimpls;
389 int i;
390
391 vars = implics->vars[varfixing];
392 types = implics->types[varfixing];
393 nimpls = implics->nimpls[varfixing];
394
395 assert(0 <= nimpls && nimpls <= implics->size[varfixing]);
396 for( i = 1; i < nimpls; ++i )
397 {
398 int cmp;
399
400 cmp = compVars(vars[i-1], vars[i]);
401 assert(cmp <= 0);
402 assert((cmp == 0) == (vars[i-1] == vars[i]));
403 assert(cmp < 0 || (types[i-1] == SCIP_BOUNDTYPE_LOWER && types[i] == SCIP_BOUNDTYPE_UPPER));
404 }
405
406 varfixing = !varfixing;
407 }
408 while( varfixing == TRUE );
409 }
410 #else
411 #define checkImplics(implics) /**/
412 #endif
413
414 /** creates an implications data structure */
415 static
416 SCIP_RETCODE implicsCreate(
417 SCIP_IMPLICS** implics, /**< pointer to store implications data structure */
418 BMS_BLKMEM* blkmem /**< block memory */
419 )
420 {
421 assert(implics != NULL);
422
423 SCIP_ALLOC( BMSallocBlockMemory(blkmem, implics) );
424
425 (*implics)->vars[0] = NULL;
426 (*implics)->types[0] = NULL;
427 (*implics)->bounds[0] = NULL;
428 (*implics)->ids[0] = NULL;
429 (*implics)->size[0] = 0;
430 (*implics)->nimpls[0] = 0;
431 (*implics)->vars[1] = NULL;
432 (*implics)->types[1] = NULL;
433 (*implics)->bounds[1] = NULL;
434 (*implics)->ids[1] = NULL;
435 (*implics)->size[1] = 0;
436 (*implics)->nimpls[1] = 0;
437
438 return SCIP_OKAY;
439 }
440
441 /** frees an implications data structure */
442 void SCIPimplicsFree(
443 SCIP_IMPLICS** implics, /**< pointer of implications data structure to free */
444 BMS_BLKMEM* blkmem /**< block memory */
445 )
446 {
447 assert(implics != NULL);
448
449 if( *implics != NULL )
450 {
451 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[0], (*implics)->size[0]);
452 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[0], (*implics)->size[0]);
453 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[0], (*implics)->size[0]);
454 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[0], (*implics)->size[0]);
455 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[1], (*implics)->size[1]);
456 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[1], (*implics)->size[1]);
457 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[1], (*implics)->size[1]);
458 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[1], (*implics)->size[1]);
459 BMSfreeBlockMemory(blkmem, implics);
460 }
461 }
462
463 /** ensures, that arrays for x == 0 or x == 1 in implications data structure can store at least num entries */
464 static
465 SCIP_RETCODE implicsEnsureSize(
466 SCIP_IMPLICS** implics, /**< pointer to implications data structure */
467 BMS_BLKMEM* blkmem, /**< block memory */
468 SCIP_SET* set, /**< global SCIP settings */
469 SCIP_Bool varfixing, /**< FALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1 */
470 int num /**< minimum number of entries to store */
471 )
472 {
473 assert(implics != NULL);
474
475 /* create implications data structure, if not yet existing */
476 if( *implics == NULL )
477 {
478 SCIP_CALL( implicsCreate(implics, blkmem) );
479 }
480 assert(*implics != NULL);
481 assert((*implics)->nimpls[varfixing] <= (*implics)->size[varfixing]);
482
483 if( num > (*implics)->size[varfixing] )
484 {
485 int newsize;
486
487 newsize = SCIPsetCalcMemGrowSize(set, num);
488 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->vars[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
489 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->types[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
490 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->bounds[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
491 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->ids[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
492 (*implics)->size[varfixing] = newsize;
493 }
494 assert(num <= (*implics)->size[varfixing]);
495
496 return SCIP_OKAY;
497 }
498
499 /** gets the positions of the implications y >= l and y <= u in the implications data structure;
500 * if no lower or upper bound implication for y was found, -1 is returned
501 */
502 static
503 void implicsSearchVar(
504 SCIP_IMPLICS* implics, /**< implications data structure */
505 SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */
506 SCIP_VAR* implvar, /**< variable y to search for */
507 int* poslower, /**< pointer to store position of y_lower (-1 if not found) */
508 int* posupper, /**< pointer to store position of y_upper (-1 if not found) */
509 int* posadd /**< pointer to store position of first y entry, or where a new y entry
510 * should be placed */
511 )
512 {
513 SCIP_Bool found;
514 int right;
515 int pos;
516
517 assert(implics != NULL);
518 assert(poslower != NULL);
519 assert(posupper != NULL);
520 assert(posadd != NULL);
521
522 if( implics->nimpls[varfixing] == 0 )
523 {
524 /* there are no implications with non-binary variable y */
525 *posadd = 0;
526 *poslower = -1;
527 *posupper = -1;
528 return;
529 }
530 right = implics->nimpls[varfixing] - 1;
531 assert(0 <= right);
532
533 /* search for the position in the sorted array (via binary search) */
534 found = SCIPsortedvecFindPtr((void**)(&(implics->vars[varfixing][0])), SCIPvarComp, (void*)implvar, right + 1, &pos);
535
536 if( !found )
537 {
538 /* y was not found */
539 assert(pos >= right || compVars((void*)implics->vars[varfixing][pos], (void*)implvar) > 0);
540 assert(pos == 0 || compVars((void*)implics->vars[varfixing][pos-1], (void*)implvar) < 0);
541 *poslower = -1;
542 *posupper = -1;
543 *posadd = pos;
544 }
545 else
546 {
547 /* y was found */
548 assert(implvar == implics->vars[varfixing][pos]);
549
550 /* set poslower and posupper */
551 if( implics->types[varfixing][pos] == SCIP_BOUNDTYPE_LOWER )
552 {
553 /* y was found as y_lower (on position middle) */
554 *poslower = pos;
555 if( pos + 1 < implics->nimpls[varfixing] && implics->vars[varfixing][pos+1] == implvar )
556 {
557 assert(implics->types[varfixing][pos+1] == SCIP_BOUNDTYPE_UPPER);
558 *posupper = pos + 1;
559 }
560 else
561 *posupper = -1;
562 *posadd = pos;
563 }
564 else
565 {
566 /* y was found as y_upper (on position pos) */
567 *posupper = pos;
568 if( pos - 1 >= 0 && implics->vars[varfixing][pos-1] == implvar )
569 {
570 assert(implics->types[varfixing][pos-1] == SCIP_BOUNDTYPE_LOWER);
571 *poslower = pos - 1;
572 *posadd = pos - 1;
573 }
574 else
575 {
576 *poslower = -1;
577 *posadd = pos;
578 }
579 }
580 }
581 }
582
583 /** returns whether variable y is already contained in implications for x == 0 or x == 1 with the given impltype
584 * y can be contained in structure with y >= b (y_lower) and y <= b (y_upper)
585 */
586 static
587 SCIP_Bool implicsSearchImplic(
588 SCIP_IMPLICS* implics, /**< implications data structure */
589 SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */
590 SCIP_VAR* implvar, /**< variable y to search for */
591 SCIP_BOUNDTYPE impltype, /**< type of implication y <=/>= b to search for */
592 int* poslower, /**< pointer to store position of y_lower (inf if not found) */
593 int* posupper, /**< pointer to store position of y_upper (inf if not found) */
594 int* posadd /**< pointer to store correct position (with respect to impltype) to add y */
595 )
596 {
597 assert(implics != NULL);
598 assert(poslower != NULL);
599 assert(posupper != NULL);
600 assert(posadd != NULL);
601
602 implicsSearchVar(implics, varfixing, implvar, poslower, posupper, posadd);
603 assert(*poslower == -1 || *posupper == -1 || *posupper == (*poslower)+1);
604 assert(*poslower == -1 || *posadd == *poslower);
605 assert(*poslower >= 0 || *posupper == -1 || *posadd == *posupper);
606 assert(0 <= *posadd && *posadd <= implics->nimpls[varfixing]);
607
608 if( impltype == SCIP_BOUNDTYPE_LOWER )
609 return (*poslower >= 0);
610 else
611 {
612 if( *poslower >= 0 )
613 {
614 assert(*posadd == *poslower);
615 (*posadd)++;
616 }
617 return (*posupper >= 0);
618 }
619 }
620
621 /** adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure;
622 * the implication must be non-redundant
623 */
624 SCIP_RETCODE SCIPimplicsAdd(
625 SCIP_IMPLICS** implics, /**< pointer to implications data structure */
626 BMS_BLKMEM* blkmem, /**< block memory */
627 SCIP_SET* set, /**< global SCIP settings */
628 SCIP_STAT* stat, /**< problem statistics */
629 SCIP_Bool varfixing, /**< FALSE if implication for x == 0 has to be added, TRUE for x == 1 */
630 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
631 SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
632 SCIP_Real implbound, /**< bound b in implication y <= b or y >= b */
633 SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */
634 SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */
635 SCIP_Bool* added /**< pointer to store whether the implication was added */
636 )
637 {
638 int poslower;
639 int posupper;
640 int posadd;
641 SCIP_Bool found;
642 #ifndef NDEBUG
643 int k;
644 #endif
645
646 assert(implics != NULL);
647 assert(*implics == NULL || 0 <= (*implics)->nimpls[varfixing]);
648 assert(stat != NULL);
649 assert(SCIPvarIsActive(implvar));
650 assert(SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_LOOSE);
651 assert((impltype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, implbound, SCIPvarGetLbGlobal(implvar)))
652 || (impltype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, implbound, SCIPvarGetUbGlobal(implvar))));
653 assert(conflict != NULL);
654 assert(added != NULL);
655
656 SCIPsetDebugMsg(set, "adding implication to implics %p [%u]: <%s> %s %g\n",
657 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbound);
658
659 checkImplics(*implics);
660
661 *conflict = FALSE;
662 *added = FALSE;
663
664 /* check if variable is already contained in implications data structure */
665 if( *implics != NULL )
666 {
667 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
668 assert(-1 <= poslower && poslower < (*implics)->nimpls[varfixing]);
669 assert(-1 <= posupper && posupper < (*implics)->nimpls[varfixing]);
670 assert(0 <= posadd && posadd <= (*implics)->nimpls[varfixing]);
671 assert(poslower == -1 || (*implics)->types[varfixing][poslower] == SCIP_BOUNDTYPE_LOWER);
672 assert(posupper == -1 || (*implics)->types[varfixing][posupper] == SCIP_BOUNDTYPE_UPPER);
673 }
674 else
675 {
676 found = FALSE;
677 poslower = -1;
678 posupper = -1;
679 posadd = 0;
680 }
681
682 if( impltype == SCIP_BOUNDTYPE_LOWER )
683 {
684 assert(found == (poslower >= 0));
685
686 /* check if y >= b is redundant */
687 if( poslower >= 0 && SCIPsetIsFeasLE(set, implbound, (*implics)->bounds[varfixing][poslower]) )
688 {
689 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
690 return SCIP_OKAY;
691 }
692
693 /* check if y >= b causes conflict for x (i.e. y <= a (with a < b) is also valid) */
694 if( posupper >= 0 && SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][posupper]) )
695 {
696 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
697 *conflict = TRUE;
698 return SCIP_OKAY;
699 }
700
701 *added = TRUE;
702
703 /* check if entry of the same type already exists */
704 if( found )
705 {
706 assert(poslower >= 0);
707 assert(posadd == poslower);
708
709 /* add y >= b by changing old entry on poslower */
710 assert((*implics)->vars[varfixing][poslower] == implvar);
711 assert(SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][poslower]));
712 (*implics)->bounds[varfixing][poslower] = implbound;
713 }
714 else
715 {
716 assert(poslower == -1);
717
718 /* add y >= b by creating a new entry on posadd */
719 SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing,
720 *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) );
721 assert(*implics != NULL);
722
723 if( (*implics)->nimpls[varfixing] - posadd > 0 )
724 {
725 int amount = ((*implics)->nimpls[varfixing] - posadd);
726
727 #ifndef NDEBUG
728 for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- )
729 {
730 assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0);
731 }
732 #endif
733 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
734 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
735 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
736 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
737 }
738
739 (*implics)->vars[varfixing][posadd] = implvar;
740 (*implics)->types[varfixing][posadd] = impltype;
741 (*implics)->bounds[varfixing][posadd] = implbound;
742 (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications);
743 (*implics)->nimpls[varfixing]++;
744 #ifndef NDEBUG
745 for( k = posadd-1; k >= 0; k-- )
746 assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0);
747 #endif
748 stat->nimplications++;
749 }
750 }
751 else
752 {
753 assert(found == (posupper >= 0));
754
755 /* check if y <= b is redundant */
756 if( posupper >= 0 && SCIPsetIsFeasGE(set, implbound, (*implics)->bounds[varfixing][posupper]) )
757 {
758 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
759 return SCIP_OKAY;
760 }
761
762 /* check if y <= b causes conflict for x (i.e. y >= a (with a > b) is also valid) */
763 if( poslower >= 0 && SCIPsetIsFeasLT(set, implbound, (*implics)->bounds[varfixing][poslower]) )
764 {
765 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
766 *conflict = TRUE;
767 return SCIP_OKAY;
768 }
769
770 *added = TRUE;
771
772 /* check if entry of the same type already exists */
773 if( found )
774 {
775 assert(posupper >= 0);
776 assert(posadd == posupper);
777
778 /* add y <= b by changing old entry on posupper */
779 assert((*implics)->vars[varfixing][posupper] == implvar);
780 assert(SCIPsetIsFeasLT(set, implbound,(*implics)->bounds[varfixing][posupper]));
781 (*implics)->bounds[varfixing][posupper] = implbound;
782 }
783 else
784 {
785 /* add y <= b by creating a new entry on posadd */
786 assert(posupper == -1);
787
788 SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing,
789 *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) );
790 assert(*implics != NULL);
791
792 if( (*implics)->nimpls[varfixing] - posadd > 0 )
793 {
794 int amount = ((*implics)->nimpls[varfixing] - posadd);
795
796 #ifndef NDEBUG
797 for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- )
798 {
799 assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0);
800 }
801 #endif
802 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
803 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
804 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
805 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
806 }
807
808 (*implics)->vars[varfixing][posadd] = implvar;
809 (*implics)->types[varfixing][posadd] = impltype;
810 (*implics)->bounds[varfixing][posadd] = implbound;
811 (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications);
812 (*implics)->nimpls[varfixing]++;
813 #ifndef NDEBUG
814 for( k = posadd-1; k >= 0; k-- )
815 assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0);
816 #endif
817 stat->nimplications++;
818 }
819 }
820
821 checkImplics(*implics);
822
823 return SCIP_OKAY;
824 }
825
826 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */
827 SCIP_RETCODE SCIPimplicsDel(
828 SCIP_IMPLICS** implics, /**< pointer to implications data structure */
829 BMS_BLKMEM* blkmem, /**< block memory */
830 SCIP_SET* set, /**< global SCIP settings */
831 SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */
832 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
833 SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
834 )
835 { /*lint --e{715}*/
836 int poslower;
837 int posupper;
838 int posadd;
839 SCIP_Bool found;
840
841 assert(implics != NULL);
842 assert(*implics != NULL);
843 assert(implvar != NULL);
844
845 SCIPsetDebugMsg(set, "deleting implication from implics %p [%u]: <%s> %s x\n",
846 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=");
847
848 checkImplics(*implics);
849
850 /* searches for y in implications of x */
851 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
852 if( !found )
853 {
854 SCIPsetDebugMsg(set, " -> implication was not found\n");
855 return SCIP_OKAY;
856 }
857
858 assert((impltype == SCIP_BOUNDTYPE_LOWER && poslower >= 0 && posadd == poslower)
859 || (impltype == SCIP_BOUNDTYPE_UPPER && posupper >= 0 && posadd == posupper));
860 assert(0 <= posadd && posadd < (*implics)->nimpls[varfixing]);
861 assert((*implics)->vars[varfixing][posadd] == implvar);
862 assert((*implics)->types[varfixing][posadd] == impltype);
863
864 /* removes y from implications of x */
865 if( (*implics)->nimpls[varfixing] - posadd > 1 )
866 {
867 int amount = ((*implics)->nimpls[varfixing] - posadd - 1);
868
869 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd]), &((*implics)->types[varfixing][posadd+1]), amount); /*lint !e866*/
870 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd]), &((*implics)->vars[varfixing][posadd+1]), amount); /*lint !e866*/
871 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd]), &((*implics)->bounds[varfixing][posadd+1]), amount); /*lint !e866*/
872 }
873 (*implics)->nimpls[varfixing]--;
874
875 /* free implics data structure, if it is empty */
876 if( (*implics)->nimpls[0] == 0 && (*implics)->nimpls[1] == 0 )
877 SCIPimplicsFree(implics, blkmem);
878
879 checkImplics(*implics);
880
881 return SCIP_OKAY;
882 }
883
884 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
885 void SCIPimplicsGetVarImplics(
886 SCIP_IMPLICS* implics, /**< implications data structure */
887 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
888 SCIP_VAR* implvar, /**< variable y to search for */
889 SCIP_Bool* haslowerimplic, /**< pointer to store whether there exists an implication y >= l */
890 SCIP_Bool* hasupperimplic /**< pointer to store whether there exists an implication y <= u */
891 )
892 {
893 int poslower;
894 int posupper;
895 int posadd;
896
897 assert(haslowerimplic != NULL);
898 assert(hasupperimplic != NULL);
899
900 implicsSearchVar(implics, varfixing, implvar, &poslower, &posupper, &posadd);
901
902 *haslowerimplic = (poslower >= 0);
903 *hasupperimplic = (posupper >= 0);
904 } /*lint !e438*/
905
906 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
907 void SCIPimplicsGetVarImplicPoss(
908 SCIP_IMPLICS* implics, /**< implications data structure */
909 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
910 SCIP_VAR* implvar, /**< variable y to search for */
911 int* lowerimplicpos, /**< pointer to store the position of an implication y >= l */
912 int* upperimplicpos /**< pointer to store the position of an implication y <= u */
913 )
914 {
915 int posadd;
916
917 assert(lowerimplicpos != NULL);
918 assert(upperimplicpos != NULL);
919
920 implicsSearchVar(implics, varfixing, implvar, lowerimplicpos, upperimplicpos, &posadd);
921 }
922
923 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */
924 SCIP_Bool SCIPimplicsContainsImpl(
925 SCIP_IMPLICS* implics, /**< implications data structure */
926 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
927 SCIP_VAR* implvar, /**< variable y to search for */
928 SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */
929 )
930 {
931 int poslower;
932 int posupper;
933 int posadd;
934
935 return implicsSearchImplic(implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); /*lint !e438*/
936 } /*lint !e638*/
937
938
939
940
941 /*
942 * methods for cliques
943 */
944
945 /* swaps cliques at positions first and second in cliques array of clique table */
946 static
947 void cliquetableSwapCliques(
948 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
949 int first, /**< first index */
950 int second /**< second index */
951 )
952 {
953 /* nothing to do if clique happens to be at the pole position of clean cliques */
954 if( first != second )
955 {
956 SCIP_CLIQUE* tmp;
957
958 tmp = cliquetable->cliques[first];
959 assert(tmp->index == first);
960 assert(cliquetable->cliques[second]->index == second);
961
962 cliquetable->cliques[first] = cliquetable->cliques[second];
963 cliquetable->cliques[second] = tmp;
964
965 /* change the indices accordingly */
966 tmp->index = second;
967 cliquetable->cliques[first]->index = first;
968 }
969 }
970
971 /* moves clique to the last position of currently dirty cliques */
972 static
973 void cliquetableMarkCliqueForCleanup(
974 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
975 SCIP_CLIQUE* clique /**< clique data structure */
976 )
977 {
978 assert(cliquetable->ndirtycliques <= clique->index);
979 assert(cliquetable->cliques[clique->index] == clique);
980 assert(cliquetable->ndirtycliques < cliquetable->ncliques);
981 assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ndirtycliques]));
982
983 /* nothing to do if clique happens to be at the pole position of clean cliques */
984 if( clique->index > cliquetable->ndirtycliques )
985 {
986 cliquetableSwapCliques(cliquetable, clique->index, cliquetable->ndirtycliques);
987 }
988
989 ++cliquetable->ndirtycliques;
990 }
991
992
993 /** creates a clique data structure with already created variables and values arrays in the size of 'size' */
994 static
995 SCIP_RETCODE cliqueCreateWithData(
996 SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
997 BMS_BLKMEM* blkmem, /**< block memory */
998 int size, /**< initial size of clique */
999 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given
1000 * value */
1001 SCIP_Bool* values, /**< values of the variables in the clique */
1002 int nvars, /**< number of variables in the clique */
1003 int id, /**< unique identifier of the clique */
1004 SCIP_Bool isequation /**< is the clique an equation or an inequality? */
1005 )
1006 {
1007 assert(clique != NULL);
1008 assert(blkmem != NULL);
1009 assert(size >= nvars && nvars > 0);
1010 assert(vars != NULL);
1011 assert(values != NULL);
1012
1013 SCIP_ALLOC( BMSallocBlockMemory(blkmem, clique) );
1014 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->vars, vars, size) );
1015 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->values, values, size) );
1016 (*clique)->nvars = nvars;
1017 (*clique)->size = size;
1018 (*clique)->startcleanup = -1;
1019 (*clique)->id = (unsigned int)id;
1020 (*clique)->eventsissued = FALSE;
1021 (*clique)->equation = isequation;
1022 (*clique)->index = -1;
1023
1024 return SCIP_OKAY;
1025 }
1026
1027 /** frees a clique data structure */
1028 static
1029 void cliqueFree(
1030 SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
1031 BMS_BLKMEM* blkmem /**< block memory */
1032 )
1033 {
1034 assert(clique != NULL);
1035
1036 if( *clique != NULL )
1037 {
1038 BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->vars, (*clique)->size);
1039 BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->values, (*clique)->size);
1040 BMSfreeBlockMemory(blkmem, clique);
1041 }
1042 }
1043
1044 /** ensures, that clique arrays can store at least num entries */
1045 static
1046 SCIP_RETCODE cliqueEnsureSize(
1047 SCIP_CLIQUE* clique, /**< clique data structure */
1048 BMS_BLKMEM* blkmem, /**< block memory */
1049 SCIP_SET* set, /**< global SCIP settings */
1050 int num /**< minimum number of entries to store */
1051 )
1052 {
1053 assert(clique != NULL);
1054
1055 if( num > clique->size )
1056 {
1057 int newsize;
1058
1059 newsize = SCIPsetCalcMemGrowSize(set, num);
1060 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->vars, clique->size, newsize) );
1061 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->values, clique->size, newsize) );
1062 clique->size = newsize;
1063 }
1064 assert(num <= clique->size);
1065
1066 return SCIP_OKAY;
1067 }
1068
1069 /** returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member
1070 * of the clique
1071 */
1072 int SCIPcliqueSearchVar(
1073 SCIP_CLIQUE* clique, /**< clique data structure */
1074 SCIP_VAR* var, /**< variable to search for */
1075 SCIP_Bool value /**< value of the variable in the clique */
1076 )
1077 {
1078 int varidx;
1079 int left;
1080 int right;
1081
1082 assert(clique != NULL);
1083
1084 varidx = SCIPvarGetIndex(var);
1085 left = -1;
1086 right = clique->nvars;
1087 while( left < right-1 )
1088 {
1089 int middle;
1090 int idx;
1091
1092 middle = (left+right)/2;
1093 idx = SCIPvarGetIndex(clique->vars[middle]);
1094 assert(idx >= 0);
1095 if( varidx < idx )
1096 right = middle;
1097 else if( varidx > idx )
1098 left = middle;
1099 else
1100 {
1101 assert(var == clique->vars[middle]);
1102
1103 /* now watch out for the correct value */
1104 if( clique->values[middle] < value )
1105 {
1106 int i;
1107 for( i = middle+1; i < clique->nvars && clique->vars[i] == var; ++i )
1108 {
1109 if( clique->values[i] == value )
1110 return i;
1111 }
1112 return -1;
1113 }
1114 if( clique->values[middle] > value )
1115 {
1116 int i;
1117 for( i = middle-1; i >= 0 && clique->vars[i] == var; --i )
1118 {
1119 if( clique->values[i] == value )
1120 return i;
1121 }
1122 return -1;
1123 }
1124 return middle;
1125 }
1126 }
1127
1128 return -1;
1129 }
1130
1131 /** returns whether the given variable/value pair is member of the given clique */
1132 SCIP_Bool SCIPcliqueHasVar(
1133 SCIP_CLIQUE* clique, /**< clique data structure */
1134 SCIP_VAR* var, /**< variable to remove from the clique */
1135 SCIP_Bool value /**< value of the variable in the clique */
1136 )
1137 {
1138 return (SCIPcliqueSearchVar(clique, var, value) >= 0);
1139 }
1140
1141 /** adds a single variable to the given clique */
1142 SCIP_RETCODE SCIPcliqueAddVar(
1143 SCIP_CLIQUE* clique, /**< clique data structure */
1144 BMS_BLKMEM* blkmem, /**< block memory */
1145 SCIP_SET* set, /**< global SCIP settings */
1146 SCIP_VAR* var, /**< variable to add to the clique */
1147 SCIP_Bool value, /**< value of the variable in the clique */
1148 SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */
1149 SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */
1150 )
1151 {
1152 int pos;
1153 int i;
1154
1155 assert(clique != NULL);
1156 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
1157 assert(SCIPvarIsBinary(var));
1158 assert(doubleentry != NULL);
1159 assert(oppositeentry != NULL);
1160
1161 SCIPsetDebugMsg(set, "adding variable <%s> == %u to clique %u\n", SCIPvarGetName(var), value, clique->id);
1162
1163 *doubleentry = FALSE;
1164 *oppositeentry = FALSE;
1165
1166 /* allocate memory */
1167 SCIP_CALL( cliqueEnsureSize(clique, blkmem, set, clique->nvars+1) );
1168
1169 /* search for insertion position by binary variable, note that first the entries are order after variable index and
1170 * second after the bool value of the corresponding variable
1171 */
1172 (void) SCIPsortedvecFindPtr((void**) clique->vars, SCIPvarComp, var, clique->nvars, &pos);
1173
1174 assert(pos >= 0 && pos <= clique->nvars);
1175 /* remember insertion position for later, pos might change */
1176 i = pos;
1177
1178 if( pos < clique->nvars )
1179 {
1180 const int amount = clique->nvars - pos;
1181
1182 /* moving elements to correct position */
1183 BMSmoveMemoryArray(&(clique->vars[pos+1]), &(clique->vars[pos]), amount); /*lint !e866*/
1184 BMSmoveMemoryArray(&(clique->values[pos+1]), &(clique->values[pos]), amount); /*lint !e866*/
1185 clique->nvars++;
1186
1187 /* insertion for a variable with cliquevalue FALSE */
1188 if( !value )
1189 {
1190 /* find last entry with the same variable and value behind the insertion position */
1191 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] == value; ++pos ); /*lint !e722*/
1192
1193 /* check if the same variable with other value also exists */
1194 if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1195 {
1196 assert(clique->values[pos + 1] != value);
1197 *oppositeentry = TRUE;
1198 }
1199
1200 /* check if we found the same variable with the same value more than once */
1201 if( pos != i )
1202 *doubleentry = TRUE;
1203 else
1204 {
1205 /* find last entry with the same variable and different value before the insertion position */
1206 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value; --pos ); /*lint !e722*/
1207
1208 /* check if we found the same variable with the same value more than once */
1209 if( pos > 0 && clique->vars[pos - 1] == var )
1210 {
1211 assert(clique->values[pos - 1] == value);
1212
1213 *doubleentry = TRUE;
1214 }
1215 /* if we found the same variable with different value, we need to order them correctly */
1216 if( pos != i )
1217 {
1218 assert(clique->vars[pos] == var);
1219 assert(clique->values[pos] != value);
1220
1221 clique->values[pos] = value;
1222 value = !value;
1223 }
1224 }
1225 }
1226 /* insertion for a variable with cliquevalue TRUE */
1227 else
1228 {
1229 /* find last entry with the same variable and different value behind the insertion position */
1230 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] != value; ++pos ); /*lint !e722*/
1231
1232 /* check if the same variable with other value also exists */
1233 if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1234 {
1235 assert(clique->values[pos + 1] == value);
1236 *doubleentry = TRUE;
1237 }
1238
1239 /* check if we found the same variable with different value */
1240 if( pos != i )
1241 {
1242 *oppositeentry = TRUE;
1243
1244 /* if we found the same variable with different value, we need to order them correctly */
1245 assert(clique->vars[pos] == var);
1246 assert(clique->values[pos] != value);
1247
1248 clique->values[pos] = value;
1249 value = !value;
1250 }
1251 else
1252 {
1253 /* find last entry with the same variable and value before the insertion position */
1254 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] == value; --pos ); /*lint !e722*/
1255
1256 if( pos != i )
1257 *doubleentry = TRUE;
1258
1259 /* check if we found the same variable with different value up front */
1260 if( pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value )
1261 *oppositeentry = TRUE;
1262 }
1263 }
1264 }
1265 else
1266 clique->nvars++;
1267
1268 clique->vars[i] = var;
1269 clique->values[i] = value;
1270 clique->eventsissued = FALSE;
1271
1272 return SCIP_OKAY;
1273 }
1274
1275 /** removes a single variable from the given clique */
1276 void SCIPcliqueDelVar(
1277 SCIP_CLIQUE* clique, /**< clique data structure */
1278 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1279 SCIP_VAR* var, /**< variable to remove from the clique */
1280 SCIP_Bool value /**< value of the variable in the clique */
1281 )
1282 {
1283 int pos;
1284
1285 assert(clique != NULL);
1286 assert(SCIPvarIsBinary(var));
1287 assert(cliquetable != NULL);
1288
1289 /* if the clique is the leading clique during the cleanup step, we do not need to insert it again */
1290 if( cliquetable->incleanup && clique->index == 0 )
1291 return;
1292
1293 SCIPdebugMessage("marking variable <%s> == %u from clique %u for deletion\n", SCIPvarGetName(var), value, clique->id);
1294
1295 /* find variable in clique */
1296 pos = SCIPcliqueSearchVar(clique, var, value);
1297
1298 assert(0 <= pos && pos < clique->nvars);
1299 assert(clique->vars[pos] == var);
1300 assert(clique->values[pos] == value);
1301
1302 /* inform the clique table that this clique should be cleaned up */
1303 if( clique->startcleanup == -1 )
1304 cliquetableMarkCliqueForCleanup(cliquetable, clique);
1305
1306 if( clique->startcleanup == -1 || pos < clique->startcleanup )
1307 clique->startcleanup = pos;
1308
1309 #ifdef SCIP_MORE_DEBUG
1310 {
1311 int v;
1312 /* all variables prior to the one marked for startcleanup should be unfixed */
1313 for( v = clique->startcleanup - 1; v >= 0; --v )
1314 {
1315 assert(SCIPvarGetUbGlobal(clique->vars[v]) > 0.5);
1316 assert(SCIPvarGetLbGlobal(clique->vars[v]) < 0.5);
1317 }
1318 }
1319 #endif
1320 }
1321
1322 /** gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array */
1323 static
1324 int cliquesSearchClique(
1325 SCIP_CLIQUE** cliques, /**< array of cliques */
1326 int ncliques, /**< number of cliques in the cliques array */
1327 SCIP_CLIQUE* clique /**< clique to search for */
1328 )
1329 {
1330 unsigned int cliqueid;
1331 int left;
1332 int right;
1333
1334 assert(cliques != NULL || ncliques == 0);
1335 assert(clique != NULL);
1336
1337 cliqueid = clique->id; /*lint !e732*/
1338 left = -1;
1339 right = ncliques;
1340 while( left < right-1 )
1341 {
1342 unsigned int id;
1343 int middle;
1344
1345 assert(cliques != NULL);
1346 middle = (left+right)/2;
1347 id = cliques[middle]->id; /*lint !e732*/
1348 if( cliqueid < id )
1349 right = middle;
1350 else if( cliqueid > id )
1351 left = middle;
1352 else
1353 {
1354 assert(clique == cliques[middle]);
1355 return middle;
1356 }
1357 }
1358
1359 return -1;
1360 }
1361
1362 #ifdef SCIP_MORE_DEBUG
1363 /** checks whether clique appears in all clique lists of the involved variables */
1364 static
1365 void cliqueCheck(
1366 SCIP_CLIQUE* clique /**< clique data structure */
1367 )
1368 {
1369 int i;
1370
1371 assert(clique != NULL);
1372
1373 for( i = 0; i < clique->nvars; ++i )
1374 {
1375 SCIP_CLIQUE** cliques;
1376 int ncliques;
1377 int pos;
1378 SCIP_VAR* var;
1379
1380 var = clique->vars[i];
1381 assert(i == 0 || SCIPvarGetIndex(clique->vars[i-1]) <= SCIPvarGetIndex(var));
1382 assert(i == 0 || clique->vars[i-1] != var || clique->values[i-1] <= clique->values[i]);
1383 ncliques = SCIPvarGetNCliques(var, clique->values[i]);
1384
1385 assert(SCIPvarIsActive(var) || ncliques == 0);
1386
1387 /* cliquelist of inactive variables are already destroyed */
1388 if( ncliques == 0 )
1389 continue;
1390
1391 cliques = SCIPvarGetCliques(var, clique->values[i]);
1392 pos = cliquesSearchClique(cliques, ncliques, clique);
1393
1394 /* assert that the clique is correctly listed in all clique lists of unfixed variables. For fixed variables,
1395 * we require that a clean up has been correctly scheduled, but not yet been processed
1396 */
1397 if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) > 0.5 )
1398 {
1399 assert(0 <= pos && pos < ncliques);
1400 assert(cliques[pos] == clique);
1401 }
1402 else
1403 assert(0 <= clique->startcleanup && clique->startcleanup <= i);
1404 }
1405 assert(clique->index >= 0);
1406 }
1407 #else
1408 #define cliqueCheck(clique) /**/
1409 #endif
1410
1411 /** creates a clique list data structure */
1412 static
1413 SCIP_RETCODE cliquelistCreate(
1414 SCIP_CLIQUELIST** cliquelist, /**< pointer to store clique list data structure */
1415 BMS_BLKMEM* blkmem /**< block memory */
1416 )
1417 {
1418 assert(cliquelist != NULL);
1419
1420 SCIP_ALLOC( BMSallocBlockMemory(blkmem, cliquelist) );
1421 (*cliquelist)->cliques[0] = NULL;
1422 (*cliquelist)->cliques[1] = NULL;
1423 (*cliquelist)->ncliques[0] = 0;
1424 (*cliquelist)->ncliques[1] = 0;
1425 (*cliquelist)->size[0] = 0;
1426 (*cliquelist)->size[1] = 0;
1427
1428 return SCIP_OKAY;
1429 }
1430
1431 /** frees a clique list data structure */
1432 void SCIPcliquelistFree(
1433 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1434 BMS_BLKMEM* blkmem /**< block memory */
1435 )
1436 {
1437 assert(cliquelist != NULL);
1438
1439 if( *cliquelist != NULL )
1440 {
1441 BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[0], (*cliquelist)->size[0]);
1442 BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[1], (*cliquelist)->size[1]);
1443 BMSfreeBlockMemory(blkmem, cliquelist);
1444 }
1445 }
1446
1447 /** ensures, that clique list arrays can store at least num entries */
1448 static
1449 SCIP_RETCODE cliquelistEnsureSize(
1450 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1451 BMS_BLKMEM* blkmem, /**< block memory */
1452 SCIP_SET* set, /**< global SCIP settings */
1453 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1454 int num /**< minimum number of entries to store */
1455 )
1456 {
1457 assert(cliquelist != NULL);
1458
1459 if( num > cliquelist->size[value] )
1460 {
1461 int newsize;
1462
1463 newsize = SCIPsetCalcMemGrowSize(set, num);
1464 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &cliquelist->cliques[value], cliquelist->size[value], newsize) ); /*lint !e866*/
1465 cliquelist->size[value] = newsize;
1466 }
1467 assert(num <= cliquelist->size[value]);
1468
1469 return SCIP_OKAY;
1470 }
1471
1472 /** adds a clique to the clique list */
1473 SCIP_RETCODE SCIPcliquelistAdd(
1474 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1475 BMS_BLKMEM* blkmem, /**< block memory */
1476 SCIP_SET* set, /**< global SCIP settings */
1477 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1478 SCIP_CLIQUE* clique /**< clique that should be added to the clique list */
1479 )
1480 {
1481 unsigned int id;
1482 int i = 0;
1483
1484 assert(cliquelist != NULL);
1485
1486 /* insert clique into list, sorted by clique id */
1487 id = clique->id; /*lint !e732*/
1488
1489 /* allocate memory */
1490 if( *cliquelist == NULL )
1491 {
1492 SCIP_CALL( cliquelistCreate(cliquelist, blkmem) );
1493 }
1494 else
1495 {
1496 if( (*cliquelist)->cliques[value] != NULL )
1497 {
1498 for( i = (*cliquelist)->ncliques[value]; i > 0 && (*cliquelist)->cliques[value][i - 1]->id > id; --i ); /*lint !e574 !e722*/
1499 /* do not put the same clique twice in the cliquelist */
1500 if( i > 0 && (*cliquelist)->cliques[value][i - 1]->id == id )
1501 return SCIP_OKAY;
1502 }
1503 }
1504 SCIP_CALL( cliquelistEnsureSize(*cliquelist, blkmem, set, value, (*cliquelist)->ncliques[value] + 1) );
1505
1506 SCIPsetDebugMsg(set, "adding clique %u to cliquelist %p value %u (length: %d)\n",
1507 clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1508
1509 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][i+1]), &((*cliquelist)->cliques[value][i]), (*cliquelist)->ncliques[value] - i); /*lint !e866*/
1510
1511 (*cliquelist)->cliques[value][i] = clique;
1512 (*cliquelist)->ncliques[value]++;
1513
1514 return SCIP_OKAY;
1515 }
1516
1517 /** removes a clique from the clique list */
1518 SCIP_RETCODE SCIPcliquelistDel(
1519 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1520 BMS_BLKMEM* blkmem, /**< block memory */
1521 SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */
1522 SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */
1523 )
1524 {
1525 int pos;
1526
1527 assert(cliquelist != NULL);
1528
1529 /* if a variable appeared twice in its last clique and is now removed both times, the cliquelist is already cleaned
1530 up after the first removal call of this "doubleton" */
1531 if( *cliquelist == NULL )
1532 return SCIP_OKAY;
1533
1534 SCIPdebugMessage("deleting clique %u from cliquelist %p value %u (length: %d)\n",
1535 clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1536
1537 pos = cliquesSearchClique((*cliquelist)->cliques[value], (*cliquelist)->ncliques[value], clique);
1538
1539 /* clique does not exist in cliquelist, the clique should contain multiple entries of the same variable */
1540 if( pos < 0 )
1541 {
1542 #ifdef SCIP_MORE_DEBUG
1543 SCIP_VAR** clqvars;
1544 SCIP_Bool* clqvalues;
1545 int nclqvars = SCIPcliqueGetNVars(clique);
1546 int v;
1547
1548 assert(nclqvars >= 2);
1549 assert(SCIPcliqueGetVars(clique) != NULL);
1550 assert(SCIPcliqueGetValues(clique) != NULL);
1551
1552 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvars, SCIPcliqueGetVars(clique), nclqvars) );
1553 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvalues, SCIPcliqueGetValues(clique), nclqvars) );
1554
1555 /* sort variables and corresponding clique values after variables indices */
1556 SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, nclqvars);
1557
1558 for( v = nclqvars - 1; v > 0; --v )
1559 {
1560 if( clqvars[v] == clqvars[v - 1] )
1561 {
1562 if( clqvalues[v] == clqvalues[v - 1] || (v > 1 && clqvars[v] == clqvars[v - 2]) )
1563 break;
1564 }
1565 }
1566 assert(v > 0);
1567
1568 BMSfreeBlockMemoryArray(blkmem, &clqvalues, nclqvars);
1569 BMSfreeBlockMemoryArray(blkmem, &clqvars, nclqvars);
1570 #endif
1571 return SCIP_OKAY;
1572 }
1573
1574 assert(0 <= pos && pos < (*cliquelist)->ncliques[value]);
1575 assert((*cliquelist)->cliques[value][pos] == clique);
1576
1577 /* remove clique from list */
1578 /* @todo maybe buffered deletion */
1579 (*cliquelist)->ncliques[value]--;
1580 if( pos < (*cliquelist)->ncliques[value] )
1581 {
1582 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][pos]), &((*cliquelist)->cliques[value][pos+1]),
1583 (*cliquelist)->ncliques[value] - pos); /*lint !e866*/
1584 }
1585
1586 /* free cliquelist if it is empty */
1587 if( (*cliquelist)->ncliques[0] == 0 && (*cliquelist)->ncliques[1] == 0 )
1588 SCIPcliquelistFree(cliquelist, blkmem);
1589
1590 return SCIP_OKAY;
1591 }
1592
1593 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears
1594 * in both lists
1595 */
1596 SCIP_Bool SCIPcliquelistsHaveCommonClique(
1597 SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */
1598 SCIP_Bool value1, /**< value of first variable */
1599 SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */
1600 SCIP_Bool value2 /**< value of second variable */
1601 )
1602 {
1603 SCIP_CLIQUE** cliques1;
1604 SCIP_CLIQUE** cliques2;
1605 int ncliques1;
1606 int ncliques2;
1607 int i1;
1608 int i2;
1609
1610 if( cliquelist1 == NULL || cliquelist2 == NULL )
1611 return FALSE;
1612
1613 ncliques1 = cliquelist1->ncliques[value1];
1614 cliques1 = cliquelist1->cliques[value1];
1615 ncliques2 = cliquelist2->ncliques[value2];
1616 cliques2 = cliquelist2->cliques[value2];
1617
1618 i1 = 0;
1619 i2 = 0;
1620
1621 if( i1 < ncliques1 && i2 < ncliques2 )
1622 {
1623 unsigned int cliqueid;
1624
1625 /* make the bigger clique the first one */
1626 if( ncliques2 > ncliques1 )
1627 {
1628 SCIP_CLIQUE** tmpc;
1629 int tmpi;
1630
1631 tmpc = cliques1;
1632 tmpi = ncliques1;
1633 cliques1 = cliques2;
1634 ncliques1 = ncliques2;
1635 cliques2 = tmpc;
1636 ncliques2 = tmpi;
1637 }
1638
1639 /* check whether both clique lists have a same clique */
1640 while( TRUE ) /*lint !e716*/
1641 {
1642 cliqueid = SCIPcliqueGetId(cliques2[i2]);
1643
1644 /* if last item in clique1 has a smaller index than the actual clique in clique2, than cause of increasing order
1645 * there will be no same item and we can stop */
1646 if( SCIPcliqueGetId(cliques1[ncliques1 - 1]) < cliqueid )
1647 break;
1648
1649 while( SCIPcliqueGetId(cliques1[i1]) < cliqueid )
1650 {
1651 ++i1;
1652 assert(i1 < ncliques1);
1653 }
1654 cliqueid = SCIPcliqueGetId(cliques1[i1]);
1655
1656 /* if last item in clique2 has a smaller index than the actual clique in clique1, than cause of increasing order
1657 * there will be no same item and we can stop */
1658 if( SCIPcliqueGetId(cliques2[ncliques2 - 1]) < cliqueid )
1659 break;
1660
1661 while( SCIPcliqueGetId(cliques2[i2]) < cliqueid )
1662 {
1663 ++i2;
1664 assert(i2 < ncliques2);
1665 }
1666 if( SCIPcliqueGetId(cliques2[i2]) == cliqueid )
1667 return TRUE;
1668 }
1669 }
1670 return FALSE;
1671 }
1672
1673 /** removes all listed entries from the cliques */
1674 void SCIPcliquelistRemoveFromCliques(
1675 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1676 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1677 SCIP_VAR* var, /**< active problem variable the clique list belongs to */
1678 SCIP_Bool irrelevantvar /**< has the variable become irrelevant, meaning that equality
1679 * cliques need to be relaxed? */
1680 )
1681 {
1682 assert(SCIPvarIsBinary(var));
1683
1684 if( cliquelist != NULL )
1685 {
1686 int value;
1687
1688 SCIPdebugMessage("removing variable <%s> from cliques (%d with value 0, %d with value 1)\n",
1689 SCIPvarGetName(var), cliquelist->ncliques[0], cliquelist->ncliques[1]);
1690
1691 for( value = 0; value < 2; ++value )
1692 {
1693 int i;
1694
1695 assert(SCIPvarGetCliques(var, (SCIP_Bool)value) == cliquelist->cliques[value]);
1696 assert(SCIPvarGetNCliques(var, (SCIP_Bool)value) == cliquelist->ncliques[value]);
1697
1698 /* it is important to iterate from the end of the array because otherwise, each removal causes
1699 * a memory move of the entire array
1700 */
1701 for( i = cliquelist->ncliques[value] - 1; i >= 0; --i )
1702 {
1703 SCIP_CLIQUE* clique;
1704
1705 clique = cliquelist->cliques[value][i];
1706 assert(clique != NULL);
1707
1708 SCIPdebugMessage(" -> removing variable <%s> == %d from clique %u (size %d)\n",
1709 SCIPvarGetName(var), value, clique->id, clique->nvars);
1710
1711 SCIPcliqueDelVar(clique, cliquetable, var, (SCIP_Bool)value);
1712
1713 if( irrelevantvar )
1714 clique->equation = FALSE;
1715
1716 #ifdef SCIP_MORE_DEBUG
1717 /* during the cleanup step, we skip the consistency check because clique may be temporarily inconsistent */
1718 if( ! cliquetable->incleanup || clique->index > 0 )
1719 {
1720 cliqueCheck(clique);
1721 }
1722 #endif
1723 }
1724 }
1725 }
1726 }
1727
1728 /** gets the key of the given element */
1729 static
1730 SCIP_DECL_HASHGETKEY(hashgetkeyClique)
1731 { /*lint --e{715}*/
1732 return elem;
1733 }
1734
1735 /** returns TRUE iff both keys are equal */
1736 static
1737 SCIP_DECL_HASHKEYEQ(hashkeyeqClique)
1738 { /*lint --e{715}*/
1739 SCIP_CLIQUE* clique1;
1740 SCIP_CLIQUE* clique2;
1741 int i;
1742
1743 clique1 = (SCIP_CLIQUE*)key1;
1744 clique2 = (SCIP_CLIQUE*)key2;
1745 assert(clique1 != NULL);
1746 assert(clique2 != NULL);
1747
1748 if( clique1->nvars != clique2->nvars )
1749 return FALSE;
1750
1751 /* the variables are sorted: we can simply check the equality of each pair of variable/values */
1752 for( i = 0; i < clique1->nvars; ++i )
1753 {
1754 if( clique1->vars[i] != clique2->vars[i] || clique1->values[i] != clique2->values[i] )
1755 return FALSE;
1756 }
1757
1758 return TRUE;
1759 }
1760
1761 /** returns the hash value of the key */
1762 static
1763 SCIP_DECL_HASHKEYVAL(hashkeyvalClique)
1764 { /*lint --e{715}*/
1765 SCIP_CLIQUE* clique;
1766
1767 clique = (SCIP_CLIQUE*)key;
1768
1769 return clique->nvars == 0 ? 0 : SCIPhashFour(SCIPvarGetIndex(clique->vars[0]), \
1770 SCIPvarGetIndex(clique->vars[clique->nvars-1]), \
1771 clique->nvars, 2*clique->values[0] + clique->values[clique->nvars-1]);
1772 }
1773
1774 #define HASHTABLE_CLIQUETABLE_SIZE 100
1775
1776 /** creates a clique table data structure */
1777 SCIP_RETCODE SCIPcliquetableCreate(
1778 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1779 SCIP_SET* set, /**< global SCIP settings */
1780 BMS_BLKMEM* blkmem /**< block memory */
1781 )
1782 {
1783 int hashtablesize;
1784
1785 assert(cliquetable != NULL);
1786
1787 SCIP_ALLOC( BMSallocMemory(cliquetable) );
1788
1789 /* create hash table to test for multiple cliques */
1790 hashtablesize = HASHTABLE_CLIQUETABLE_SIZE;
1791 hashtablesize = MAX(hashtablesize, (set->misc_usesmalltables ? SCIP_HASHSIZE_CLIQUES_SMALL : SCIP_HASHSIZE_CLIQUES));
1792 SCIP_CALL( SCIPhashtableCreate(&((*cliquetable)->hashtable), blkmem, hashtablesize,
1793 hashgetkeyClique, hashkeyeqClique, hashkeyvalClique, NULL) );
1794
1795 (*cliquetable)->varidxtable = NULL;
1796 (*cliquetable)->djset = NULL;
1797 (*cliquetable)->cliques = NULL;
1798 (*cliquetable)->ncliques = 0;
1799 (*cliquetable)->size = 0;
1800 (*cliquetable)->ncreatedcliques = 0;
1801 (*cliquetable)->ncleanupfixedvars = 0;
1802 (*cliquetable)->ncleanupaggrvars = 0;
1803 (*cliquetable)->ndirtycliques = 0;
1804 (*cliquetable)->nentries = 0;
1805 (*cliquetable)->incleanup = FALSE;
1806 (*cliquetable)->compsfromscratch = FALSE;
1807 (*cliquetable)->ncliquecomponents = -1;
1808
1809 return SCIP_OKAY;
1810 }
1811
1812 /** frees a clique table data structure */
1813 SCIP_RETCODE SCIPcliquetableFree(
1814 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1815 BMS_BLKMEM* blkmem /**< block memory */
1816 )
1817 {
1818 int i;
1819
1820 assert(cliquetable != NULL);
1821 assert(*cliquetable != NULL);
1822
1823 /* free all cliques */
1824 for( i = (*cliquetable)->ncliques - 1; i >= 0; --i )
1825 {
1826 cliqueFree(&(*cliquetable)->cliques[i], blkmem);
1827 }
1828
1829 /* free disjoint set (union find) data structure */
1830 if( (*cliquetable)->djset != NULL )
1831 SCIPdisjointsetFree(&(*cliquetable)->djset, blkmem);
1832
1833 /* free hash table for variable indices */
1834 if( (*cliquetable)->varidxtable != NULL )
1835 SCIPhashmapFree(&(*cliquetable)->varidxtable);
1836
1837 /* free clique table data */
1838 BMSfreeMemoryArrayNull(&(*cliquetable)->cliques);
1839
1840 /* free hash table */
1841 SCIPhashtableFree(&((*cliquetable)->hashtable));
1842
1843 BMSfreeMemory(cliquetable);
1844
1845 return SCIP_OKAY;
1846 }
1847
1848 /** ensures, that clique table arrays can store at least num entries */
1849 static
1850 SCIP_RETCODE cliquetableEnsureSize(
1851 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1852 SCIP_SET* set, /**< global SCIP settings */
1853 int num /**< minimum number of entries to store */
1854 )
1855 {
1856 assert(cliquetable != NULL);
1857
1858 if( num > cliquetable->size )
1859 {
1860 int newsize;
1861
1862 newsize = SCIPsetCalcMemGrowSize(set, num);
1863 SCIP_ALLOC( BMSreallocMemoryArray(&cliquetable->cliques, newsize) );
1864 cliquetable->size = newsize;
1865 }
1866 assert(num <= cliquetable->size);
1867
1868 return SCIP_OKAY;
1869 }
1870
1871 /** sort variables regarding their index and remove multiple entries of the same variable */
1872 static
1873 SCIP_RETCODE sortAndMergeClique(
1874 SCIP_VAR** clqvars, /**< variables of a clique */
1875 SCIP_Bool* clqvalues, /**< clique values, active or negated, for the variables in a clique */
1876 int* nclqvars, /**< number of clique variables */
1877 SCIP_Bool* isequation, /**< do we have an equation clique at hand? */
1878 SCIP_CLIQUE* clique, /**< clique data structure or NULL */
1879 BMS_BLKMEM* blkmem, /**< block memory */
1880 SCIP_SET* set, /**< global SCIP settings */
1881 SCIP_STAT* stat, /**< problem statistics */
1882 SCIP_PROB* transprob, /**< transformed problem */
1883 SCIP_PROB* origprob, /**< original problem */
1884 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
1885 SCIP_REOPT* reopt, /**< reoptimization data structure */
1886 SCIP_LP* lp, /**< current LP data */
1887 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1888 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1889 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1890 int* nbdchgs, /**< pointer to store number of fixed variables */
1891 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1892 )
1893 {
1894 int noldbdchgs;
1895 int startidx;
1896
1897 assert(nclqvars != NULL);
1898
1899 SCIPsetDebugMsg(set, "starting merging %d variables in clique %d\n", *nclqvars, (clique == NULL) ? -1 : (int) clique->id);
1900
1901 if( *nclqvars <= 1 )
1902 return SCIP_OKAY;
1903
1904 assert(clqvars != NULL);
1905 assert(clqvalues != NULL);
1906 assert(blkmem != NULL);
1907 assert(set != NULL);
1908 assert(stat != NULL);
1909 assert(transprob != NULL);
1910 assert(origprob != NULL);
1911 assert(tree != NULL);
1912 assert(eventqueue != NULL);
1913 assert(nbdchgs != NULL);
1914 assert(infeasible != NULL);
1915
1916 /* sort variables and corresponding clique values regarding variables indices before merging multiples */
1917 SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, *nclqvars);
1918
1919 noldbdchgs = *nbdchgs;
1920 /* check for multiple occurences or pairs of negations in the variable array, this should be very rare when creating a
1921 * new clique */
1922 startidx = *nclqvars - 1;
1923 while( startidx >= 0 )
1924 {
1925 SCIP_VAR* var;
1926 int nones;
1927 int nzeros;
1928 int curr;
1929
1930 var = clqvars[startidx];
1931 /* only column and loose variables can exist now */
1932 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
1933 assert(SCIPvarIsBinary(var));
1934
1935 /* the counters denote the occurrences of the variable var with value TRUE and FALSE as clqvalues, respectively */
1936 if( clqvalues[startidx] )
1937 {
1938 nones = 1;
1939 nzeros = 0;
1940 }
1941 else
1942 {
1943 nzeros = 1;
1944 nones = 0;
1945 }
1946 curr = startidx - 1;
1947
1948 /* loop and increase the counter based on the clique value */
1949 while( curr >= 0 )
1950 {
1951 if( clqvars[curr] == var )
1952 {
1953 if( clqvalues[curr] )
1954 nones++;
1955 else
1956 nzeros++;
1957 }
1958 else
1959 /* var is different from variable at index curr */
1960 break;
1961
1962 --curr;
1963 }
1964 assert(nzeros + nones <= *nclqvars);
1965
1966 /* single occurrence of the variable */
1967 if( nones + nzeros == 1 )
1968 {
1969 startidx = curr;
1970 continue;
1971 }
1972 /* at least two occurrences of both the variable and its negation; infeasible */
1973 if( nones >= 2 && nzeros >= 2 )
1974 {
1975 *infeasible = TRUE;
1976 break;
1977 }
1978
1979 /* do we have the same variable with the same clique value twice? */
1980 if( nones >= 2 || nzeros >= 2 )
1981 {
1982 SCIP_Bool fixvalue;
1983
1984 /* other cases should be handled as infeasible */
1985 assert(nones <= 1 || nzeros <= 1);
1986
1987 /* ensure that the variable is removed from both clique lists before fixing it */
1988 if( clique != NULL )
1989 {
1990 if( nones >= 1 )
1991 {
1992 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) );
1993 }
1994 if( nzeros >= 1 )
1995 {
1996 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) );
1997 }
1998 }
1999
2000 /* we fix the variable into the direction of fewer occurrences */
2001 fixvalue = nones >= 2 ? FALSE : TRUE;
2002
2003 /* a variable multiple times in one clique forces this variable to be zero */
2004 SCIP_CALL( SCIPvarFixBinary(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2005 cliquetable, fixvalue, infeasible, nbdchgs) );
2006
2007 SCIPsetDebugMsg(set, "same var %s twice in a clique with value %d fixed to %d (was %s)\n", SCIPvarGetName(var), fixvalue ? 0 : 1,
2008 fixvalue ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2009
2010 if( *infeasible )
2011 break;
2012 }
2013
2014 /* do we have a pair of negated variables? */
2015 if( nones >= 1 && nzeros >= 1 )
2016 {
2017 SCIPsetDebugMsg(set, "var %s is paired with its negation in one clique -> fix all other variables\n", SCIPvarGetName(var));
2018
2019 /* a pair of negated variables in one clique forces all other variables in the clique to be zero */
2020 if( nzeros + nones < *nclqvars )
2021 {
2022 int w;
2023
2024 w = *nclqvars - 1;
2025 while( w >= 0 )
2026 {
2027 /* skip all occurrences of variable var itself, these are between curr and startidx */
2028 if( w == startidx )
2029 {
2030 if( curr == -1 )
2031 break;
2032
2033 w = curr;
2034 }
2035 assert(clqvars[w] != var);
2036
2037 /* if one of the other variables occurs multiple times, we can
2038 * 1) deduce infeasibility if it occurs with different values
2039 * 2) wait for the last occurence to fix it
2040 */
2041 while( w > 0 && clqvars[w-1] == clqvars[w] )
2042 {
2043 if( clqvalues[w-1] != clqvalues[w] )
2044 {
2045 *infeasible = TRUE;
2046 break;
2047 }
2048 --w;
2049 }
2050
2051 if( *infeasible )
2052 break;
2053
2054 if( clique != NULL )
2055 {
2056 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[w], blkmem, clqvalues[w], clique) );
2057 }
2058 SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2059 branchcand, eventqueue, cliquetable, !clqvalues[w], infeasible, nbdchgs) );
2060
2061 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[w]), clqvalues[w],
2062 clqvalues[w] ? 0 : 1, *infeasible ? "infeasible" : "feasible");
2063
2064 if( *infeasible )
2065 break;
2066
2067 --w;
2068 }
2069 }
2070 /* all variables except for var were fixed */
2071 if( clique != NULL )
2072 {
2073 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) );
2074 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) );
2075 }
2076 *nclqvars = 0;
2077 *isequation = FALSE;
2078
2079 /* break main loop */
2080 break;
2081 }
2082
2083 /* otherwise, we would have an endless loop */
2084 assert(curr < startidx);
2085 startidx = curr;
2086 }
2087
2088 /* we might have found an infeasibility or reduced the clique to size 0 */
2089 if( *infeasible || *nclqvars == 0 )
2090 return SCIP_OKAY;
2091
2092 /* we fixed a variable because it appears at least twice, now we need to remove the fixings
2093 *
2094 * @note that if we are in probing or solving stage, the fixation on the variable might not be carried out yet,
2095 * because it was contradicting a local bound
2096 */
2097 if( *nbdchgs > noldbdchgs )
2098 {
2099 SCIP_VAR* onefixedvar;
2100 SCIP_Bool onefixedvalue;
2101 int w;
2102
2103 /* we initialize the former value only to please gcc */
2104 onefixedvalue = TRUE;
2105 onefixedvar = NULL;
2106
2107 /* remove all inactive variables, thereby checking for a variable that is fixed to one */
2108 startidx = 0;
2109 w = 0;
2110 while( startidx < *nclqvars )
2111 {
2112 SCIP_VAR* var;
2113
2114 var = clqvars[startidx];
2115
2116 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
2117 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
2118
2119 /* check if we have a variable fixed to one for this clique */
2120 if( (clqvalues[startidx] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[startidx] && SCIPvarGetUbGlobal(var) < 0.5) )
2121 {
2122 if( onefixedvar != NULL )
2123 {
2124 *infeasible = TRUE;
2125
2126 SCIPsetDebugMsg(set, "two variables in clique %d fixed to one %s%s and %s%s\n", (clique != NULL) ? (int) clique->id : -1,
2127 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clqvalues[startidx] ? "" : "~", SCIPvarGetName(clqvars[startidx]));
2128 return SCIP_OKAY;
2129 }
2130 onefixedvar = var;
2131 onefixedvalue = clqvalues[startidx];
2132 }
2133 /* only keep active variables */
2134 else if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
2135 {
2136 /* we remove all fixed variables */
2137 if( startidx > w )
2138 {
2139 clqvars[w] = clqvars[startidx];
2140 clqvalues[w] = clqvalues[startidx];
2141 }
2142 ++w;
2143 }
2144 else
2145 {
2146 /* can we have some variable fixed to one? */
2147 assert((SCIPvarGetUbGlobal(var) < 0.5 && clqvalues[startidx]) || (SCIPvarGetLbGlobal(var) > 0.5 && !clqvalues[startidx]));
2148
2149 if( clique != NULL )
2150 {
2151 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, clqvalues[startidx], clique) );
2152 }
2153 }
2154 ++startidx;
2155 }
2156
2157 /* the clique has been reduced to w active (unfixed) variables */
2158 *nclqvars = w;
2159
2160 /* in rare cases, a variable fixed to one is only detected in the merging step */
2161 if( onefixedvar != NULL )
2162 {
2163 SCIPsetDebugMsg(set, "variable %s%s in clique %d fixed to one, fixing all other variables to zero\n",
2164 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), (clique != NULL) ? (int) clique->id : -1);
2165
2166 /* handle all active variables by fixing them */
2167 for( startidx = *nclqvars; startidx >= 0; --startidx )
2168 {
2169 assert(SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_COLUMN
2170 || SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_LOOSE);
2171
2172 /* delete the variable from its clique lists and fix it */
2173 if( onefixedvalue != clqvalues[startidx] || clqvars[startidx] != onefixedvar )
2174 {
2175 if( clique != NULL )
2176 {
2177 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[startidx], blkmem, clqvalues[startidx], clique) );
2178 }
2179
2180 /* if one of the other variables occurs multiple times, we can
2181 * 1) deduce infeasibility if it occurs with different values
2182 * 2) wait for the last occurence to fix it
2183 */
2184 while( startidx > 0 && clqvars[startidx - 1] == clqvars[startidx] )
2185 {
2186 if( clqvalues[startidx - 1] != clqvalues[startidx] )
2187 {
2188 *infeasible = TRUE;
2189 return SCIP_OKAY;
2190 }
2191 --startidx; /*lint !e850*/
2192 }
2193
2194 SCIPsetDebugMsg(set, "fixing variable %s in clique %d to %d\n", SCIPvarGetName(clqvars[startidx]), (clique != NULL) ? (int) clique->id : -1,
2195 clqvalues[startidx] ? 0 : 1);
2196
2197 /* note that the variable status will remain unchanged */
2198 SCIP_CALL( SCIPvarFixBinary(clqvars[startidx], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2199 branchcand, eventqueue, cliquetable, !clqvalues[startidx], infeasible, nbdchgs) );
2200
2201 if( *infeasible )
2202 return SCIP_OKAY;
2203 }
2204 }
2205
2206 /* delete clique from onefixedvars clique list */
2207 if( clique != NULL ) /*lint !e850*/
2208 {
2209 SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2210 }
2211
2212 *nclqvars = 0;
2213 *isequation = FALSE;
2214 }
2215 }
2216
2217 assert(!(*infeasible));
2218
2219 if( *isequation )
2220 {
2221 if( *nclqvars == 0 )
2222 {
2223 SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n");
2224
2225 *infeasible = TRUE;
2226 }
2227 else if( *nclqvars == 1 )
2228 {
2229 assert(SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_COLUMN
2230 || SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_LOOSE);
2231 /* clearing data and removing variable from its clique list */
2232 if( clique != NULL )
2233 {
2234 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[0], blkmem, clqvalues[0], clique) );
2235 }
2236 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2237 eventqueue, cliquetable, clqvalues[0], infeasible, nbdchgs) );
2238
2239 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2240 clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2241
2242 *nclqvars = 0;
2243 *isequation = FALSE;
2244 }
2245 }
2246
2247 return SCIP_OKAY;
2248 }
2249
2250 /** helper function that returns the graph node index for a variable during connected component detection */
2251 static
2252 int cliquetableGetNodeIndexBinvar(
2253 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2254 SCIP_VAR* binvar /**< binary (or binary integer or implicit binary) variable */
2255 )
2256 {
2257 SCIP_VAR* activevar;
2258 int nodeindex;
2259
2260 assert(binvar != NULL);
2261 assert(SCIPvarIsBinary(binvar));
2262
2263 if( cliquetable->varidxtable == NULL )
2264 return -1;
2265
2266 /* get active representative of variable */
2267 if( !SCIPvarIsActive(binvar) )
2268 {
2269 activevar = SCIPvarGetProbvar(binvar);
2270 if( !SCIPvarIsActive(activevar) )
2271 return -1;
2272 }
2273 else
2274 activevar = binvar;
2275
2276 assert(SCIPvarIsBinary(activevar));
2277
2278 /* if the map does not contain an index for this variable, return -1 and mark that the components must be
2279 * recomputed from scratch
2280 */
2281 if( SCIPhashmapExists(cliquetable->varidxtable, (void*)activevar) )
2282 nodeindex = SCIPhashmapGetImageInt(cliquetable->varidxtable, (void *)activevar);
2283 else
2284 {
2285 nodeindex = -1;
2286 cliquetable->compsfromscratch = TRUE;
2287 }
2288
2289 return nodeindex;
2290 }
2291
2292
2293 /** updates connectedness information for the \p clique */
2294 static
2295 void cliquetableUpdateConnectednessClique(
2296 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2297 SCIP_CLIQUE* clique /**< clique that should be added */
2298 )
2299 {
2300 int i;
2301 int lastnode;
2302 SCIP_VAR** clqvars;
2303 int nclqvars;
2304
2305 assert(cliquetable != NULL);
2306 assert(clique != NULL);
2307
2308 /* check if disjoint set (union find) data structure has not been allocated yet */
2309 if( cliquetable->djset == NULL )
2310 cliquetable->compsfromscratch = TRUE;
2311
2312 /* return immediately if a component update is already pending */
2313 if( cliquetable->compsfromscratch )
2314 return;
2315
2316 lastnode = -1;
2317 clqvars = clique->vars;
2318 nclqvars = clique->nvars;
2319
2320 /* loop over variables in the clique and connect the corresponding components */
2321 for( i = 0; i < nclqvars && !cliquetable->compsfromscratch; ++i )
2322 {
2323 /* this method may also detect that the clique table must entirely recompute connectedness */
2324 int currnode = cliquetableGetNodeIndexBinvar(cliquetable, clqvars[i]);
2325
2326 /* skip inactive variables */
2327 if( currnode == - 1 )
2328 continue;
2329
2330 /* connect this and the last active variable */
2331 if( lastnode != -1 )
2332 SCIPdisjointsetUnion(cliquetable->djset, lastnode, currnode, FALSE);
2333
2334 lastnode = currnode;
2335 }
2336 }
2337
2338 /** returns the index of the connected component of the clique graph that the variable belongs to, or -1 */
2339 int SCIPcliquetableGetVarComponentIdx(
2340 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2341 SCIP_VAR* var /**< problem variable */
2342 )
2343 {
2344 int cmpidx = -1;
2345 assert(var != NULL);
2346 assert(cliquetable->djset != NULL);
2347
2348 /* only binary variables can have a component index
2349 *(both integer and implicit integer variables can be binary)
2350 */
2351 if( SCIPvarIsBinary(var) )
2352 {
2353 int nodeindex = cliquetableGetNodeIndexBinvar(cliquetable, var);
2354 assert(nodeindex < SCIPdisjointsetGetSize(cliquetable->djset));
2355
2356 if( nodeindex >= 0 )
2357 cmpidx = SCIPdisjointsetFind(cliquetable->djset, nodeindex);
2358 }
2359
2360 return cmpidx;
2361 }
2362
2363
2364 /** adds a clique to the clique table, using the given values for the given variables;
2365 * performs implications if the clique contains the same variable twice
2366 */
2367 SCIP_RETCODE SCIPcliquetableAdd(
2368 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2369 BMS_BLKMEM* blkmem, /**< block memory */
2370 SCIP_SET* set, /**< global SCIP settings */
2371 SCIP_STAT* stat, /**< problem statistics */
2372 SCIP_PROB* transprob, /**< transformed problem */
2373 SCIP_PROB* origprob, /**< original problem */
2374 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2375 SCIP_REOPT* reopt, /**< reoptimization data structure */
2376 SCIP_LP* lp, /**< current LP data */
2377 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2378 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2379 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
2380 SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
2381 int nvars, /**< number of variables in the clique */
2382 SCIP_Bool isequation, /**< is the clique an equation or an inequality? */
2383 SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
2384 int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */
2385 )
2386 {
2387 SCIP_VAR** clqvars;
2388 SCIP_Bool* clqvalues;
2389 SCIP_CLIQUE* clique;
2390 SCIP_VAR* var;
2391 int size;
2392 int nlocalbdchgs = 0;
2393 int v;
2394 int w;
2395
2396 assert(cliquetable != NULL);
2397 assert(vars != NULL);
2398
2399 SCIPsetDebugMsg(set, "trying to add clique %d with %d vars to clique table\n", cliquetable->ncliques, nvars);
2400
2401 /* check clique on debugging solution */
2402 SCIP_CALL( SCIPdebugCheckClique(set, vars, values, nvars) ); /*lint !e506 !e774*/
2403
2404 *infeasible = FALSE;
2405 size = nvars;
2406
2407 /* copy clique data */
2408 if( values == NULL )
2409 {
2410 SCIP_CALL( SCIPsetAllocBufferArray(set, &clqvalues, size) );
2411
2412 /* initialize clique values data */
2413 for( v = nvars - 1; v >= 0; --v )
2414 clqvalues[v] = TRUE;
2415 }
2416 else
2417 {
2418 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvalues, values, size) );
2419 }
2420 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvars, vars, size) );
2421
2422 /* get active variables */
2423 SCIP_CALL( SCIPvarsGetProbvarBinary(&clqvars, &clqvalues, nvars) );
2424
2425 /* remove all inactive vars */
2426 for( v = nvars - 1; v >= 0; --v )
2427 {
2428 var = clqvars[v];
2429
2430 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
2431 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
2432 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
2433 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
2434 assert(SCIPvarIsBinary(var));
2435
2436 /* if we have a variables already fixed to one in the clique, fix all other to zero */
2437 if( ! SCIPvarIsMarkedDeleteGlobalStructures(var) &&
2438 ((clqvalues[v] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[v] && SCIPvarGetUbGlobal(var) < 0.5)) )
2439 {
2440 SCIPsetDebugMsg(set, "in a clique var %s with value %u is fixed to %d -> fix the rest\n", SCIPvarGetName(var), clqvalues[v], clqvalues[v] ? 1 : 0);
2441
2442 for( w = nvars - 1; w >= 0; --w )
2443 {
2444 SCIP_VAR* clqvar = clqvars[w];
2445
2446 /* the rare case where the same variable appears several times is handled later during sort and merge */
2447 if( clqvar != var )
2448 {
2449 SCIP_Bool clqval = clqvalues[w];
2450
2451 /* check if variable is fixed already and terminate with infeasible if this fixing contradicts the clique info */
2452 if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2453 {
2454 /* check if fixing contradicts clique constraint */
2455 if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2456 || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2457 {
2458 *infeasible = TRUE;
2459
2460 goto FREEMEM;
2461 }
2462
2463 continue;
2464 }
2465
2466 /* the following piece of code is disabled because it assumes the clqvars to be sorted which they aren't until the method
2467 * sortAndMergeClique() is called
2468 */
2469 #ifdef SCIP_DISABLED_CODE
2470 /* if one of the other variables occurs multiple times, we can
2471 * 1) deduce infeasibility if it occurs with different values
2472 * 2) wait for the last occurence to fix it
2473 */
2474 while( w > 0 && clqvars[w - 1] == clqvars[w] )
2475 {
2476 if( clqvalues[w - 1] != clqvalues[w] )
2477 {
2478 *infeasible = TRUE;
2479 return SCIP_OKAY;
2480 }
2481 --w;
2482 }
2483 #endif
2484
2485 /* fix the variable */
2486 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2487 branchcand, eventqueue, cliquetable, !clqval, infeasible, &nlocalbdchgs) );
2488
2489 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvar), clqval,
2490 clqval ? 0 : 1, *infeasible ? "infeasible" : "feasible");
2491
2492 if( *infeasible )
2493 break;
2494 }
2495 }
2496
2497 /* all variables are fixed so we can stop */
2498 break; /*lint !e850*/
2499 }
2500
2501 /* only unfixed column and loose variables may be member of a clique */
2502 if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) < 0.5 ||
2503 (SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN && SCIPvarGetStatus(var) != SCIP_VARSTATUS_LOOSE) ||
2504 SCIPvarIsMarkedDeleteGlobalStructures(var) )
2505 {
2506 --nvars;
2507 clqvars[v] = clqvars[nvars];
2508 clqvalues[v] = clqvalues[nvars];
2509 isequation = isequation && !(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR) && ! SCIPvarIsMarkedDeleteGlobalStructures(var);
2510 }
2511 }
2512
2513 if( nbdchgs != NULL )
2514 *nbdchgs += nlocalbdchgs;
2515
2516 /* did we fix all variables or are we infeasible? */
2517 if( v >= 0 )
2518 goto FREEMEM;
2519
2520 assert(!*infeasible);
2521
2522 /* check if only one or less variables are left */
2523 if( v < 0 && nvars <= 1)
2524 {
2525 if( isequation )
2526 {
2527 if( nvars == 1 )
2528 {
2529 nlocalbdchgs = 0;
2530
2531 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2532 branchcand, eventqueue, cliquetable, clqvalues[0], infeasible, &nlocalbdchgs) );
2533
2534 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2535 clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2536
2537 if( nbdchgs != NULL )
2538 *nbdchgs += nlocalbdchgs;
2539 }
2540 else if( nvars == 0 )
2541 {
2542 SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n");
2543
2544 *infeasible = TRUE;
2545 }
2546 }
2547
2548 goto FREEMEM;
2549 }
2550
2551 nlocalbdchgs = 0;
2552
2553 /* sort the variables and values and remove multiple entries of the same variable */
2554 SCIP_CALL( sortAndMergeClique(clqvars, clqvalues, &nvars, &isequation, NULL, blkmem, set, stat, transprob, origprob, tree,
2555 reopt, lp, branchcand, eventqueue, cliquetable, &nlocalbdchgs, infeasible) );
2556
2557 if( nbdchgs != NULL )
2558 *nbdchgs += nlocalbdchgs;
2559
2560 /* did we stop early due to a pair of negated variables? */
2561 if( nvars == 0 || *infeasible )
2562 goto FREEMEM;
2563
2564 if( !SCIPsetIsInfinity(set, set->presol_clqtablefac) && SCIPcliquetableGetNEntries(cliquetable) + nvars > set->presol_clqtablefac * stat->nnz )
2565 {
2566 SCIPsetDebugMsg(set, "reject %d-variable clique to keep clique table entries below threshold of %g entries\n",
2567 nvars, set->presol_clqtablefac * stat->nnz);
2568
2569 goto FREEMEM;
2570 }
2571
2572 /* if less than two variables are left over, the clique is redundant */
2573 if( nvars > 1 )
2574 {
2575 SCIP_CLIQUE* sameclique;
2576
2577 /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2578
2579 /* create the clique data structure */
2580 SCIP_CALL( cliqueCreateWithData(&clique, blkmem, nvars, clqvars, clqvalues, nvars, cliquetable->ncreatedcliques, isequation) );
2581
2582 sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
2583
2584 if( sameclique == NULL )
2585 {
2586 SCIPsetDebugMsg(set, "adding clique %u with %d vars to clique table\n", clique->id, nvars);
2587
2588 cliquetable->ncreatedcliques++;
2589
2590 /* add clique to clique table */
2591 SCIP_CALL( cliquetableEnsureSize(cliquetable, set, cliquetable->ncliques+1) );
2592 cliquetable->cliques[cliquetable->ncliques] = clique;
2593 clique->index = cliquetable->ncliques;
2594 cliquetable->ncliques++;
2595 cliquetable->nentries += nvars;
2596 cliquetableUpdateConnectednessClique(cliquetable, clique);
2597
2598 SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
2599
2600 /* add filled clique to the cliquelists of all corresponding variables */
2601 SCIP_CALL( SCIPvarsAddClique(clqvars, clqvalues, nvars, blkmem, set, clique) );
2602 }
2603 else
2604 {
2605 SCIPsetDebugMsg(set, "same clique %p (id: %d) already found in cliquetable -> discard new one\n", (void*) sameclique, sameclique->id);
2606
2607 /* update equation status of clique */
2608 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
2609 * the sameclique from the hashmap while adding the new clique
2610 */
2611 if( !sameclique->equation && clique->equation )
2612 sameclique->equation = TRUE;
2613
2614 cliqueFree(&clique, blkmem);
2615
2616 goto FREEMEM;
2617 }
2618 }
2619 else
2620 {
2621 assert(!isequation);
2622 assert(nvars == 1);
2623
2624 goto FREEMEM;
2625 }
2626 cliqueCheck(clique);
2627
2628 FREEMEM:
2629 SCIPsetFreeBufferArray(set, &clqvars);
2630 SCIPsetFreeBufferArray(set, &clqvalues);
2631
2632 return SCIP_OKAY;
2633 }
2634
2635 /** clean up given clique by removing fixed variables */
2636 static
2637 SCIP_RETCODE cliqueCleanup(
2638 SCIP_CLIQUE* clique, /**< clique data structure */
2639 BMS_BLKMEM* blkmem, /**< block memory */
2640 SCIP_SET* set, /**< global SCIP settings */
2641 SCIP_STAT* stat, /**< problem statistics */
2642 SCIP_PROB* transprob, /**< transformed problem */
2643 SCIP_PROB* origprob, /**< original problem */
2644 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2645 SCIP_REOPT* reopt, /**< reoptimization data structure */
2646 SCIP_LP* lp, /**< current LP data */
2647 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2648 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2649 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2650 int* nchgbds, /**< pointer to store number of fixed variables */
2651 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2652 )
2653 {
2654 assert(clique != NULL);
2655 assert(blkmem != NULL);
2656 assert(set != NULL);
2657 assert(nchgbds != NULL);
2658 assert(infeasible != NULL);
2659
2660 /* do we need to clean up fixed variables? */
2661 if( !SCIPcliqueIsCleanedUp(clique) )
2662 {
2663 SCIP_VAR* onefixedvar = NULL;
2664 SCIP_Bool onefixedvalue;
2665 SCIP_Bool needsorting = FALSE;
2666 int v;
2667 int w;
2668
2669 w = clique->startcleanup;
2670
2671 SCIPsetDebugMsg(set, "Starting clean up of clique %u (size %d) from position %d\n", clique->id, clique->nvars, w);
2672
2673 /* exchange inactive by active variables */
2674 for( v = w; v < clique->nvars; ++v )
2675 {
2676 SCIP_Bool addvartoclique; /* has the variable status changed such that it needs to be replaced by an active representative? */
2677
2678 addvartoclique = FALSE;
2679 if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_AGGREGATED
2680 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED
2681 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2682 {
2683 needsorting = TRUE;
2684
2685 SCIP_CALL( SCIPvarGetProbvarBinary(&(clique->vars[v]), &(clique->values[v])) );
2686 if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED )
2687 {
2688 clique->vars[v] = SCIPvarGetNegationVar(clique->vars[v]);
2689 clique->values[v] = !clique->values[v];
2690 }
2691 else if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2692 {
2693 clique->equation = FALSE;
2694 continue;
2695 }
2696
2697 addvartoclique = TRUE;
2698 }
2699
2700 assert(SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_COLUMN
2701 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_LOOSE
2702 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_FIXED);
2703
2704 /* check for variables that are either fixed to zero or marked for deletion from global structures */
2705 if( (clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) ||
2706 (!clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5) ||
2707 SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2708 {
2709 if( clique->equation && SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2710 clique->equation = FALSE;
2711
2712 /* the variable will be overwritten by subsequent active variables */
2713 continue;
2714 }
2715
2716 /* check for a variable fixed to one in the clique */
2717 else if( (clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5)
2718 || (!clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) )
2719 {
2720 if( onefixedvar != NULL )
2721 {
2722 *infeasible = TRUE;
2723
2724 SCIPsetDebugMsg(set, "two variables in clique %u fixed to one %s%s and %s%s\n", clique->id,
2725 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->values[v] ? "" : "~",
2726 SCIPvarGetName(clique->vars[v])); /*lint !e530*/
2727 return SCIP_OKAY;
2728 }
2729 onefixedvar = clique->vars[v];
2730 onefixedvalue = clique->values[v];
2731 }
2732 else
2733 {
2734 assert(SCIPvarGetStatus(clique->vars[v]) != SCIP_VARSTATUS_FIXED);
2735 assert(w <= v);
2736
2737 if( w < v )
2738 {
2739 clique->vars[w] = clique->vars[v];
2740 clique->values[w] = clique->values[v];
2741 }
2742
2743 /* add clique to active variable if it replaced a aggregated or negated var */
2744 if( addvartoclique )
2745 {
2746 SCIP_CALL( SCIPvarAddCliqueToList(clique->vars[w], blkmem, set, clique->values[w], clique) );
2747 }
2748 /* increase indexer of last active, i.e. unfixed, variable in clique */
2749 ++w;
2750 }
2751 }
2752 clique->nvars = w;
2753
2754 if( onefixedvar != NULL )
2755 {
2756 SCIPsetDebugMsg(set, "variable %s%s in clique %u fixed to one, fixing all other variables to zero\n",
2757 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->id);
2758
2759 for( v = 0; v < clique->nvars ; ++v )
2760 {
2761 SCIP_VAR* clqvar = clique->vars[v];
2762 SCIP_Bool clqval = clique->values[v];
2763
2764 assert(SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_COLUMN
2765 || SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_LOOSE);
2766
2767 if( onefixedvalue != clqval || clqvar != onefixedvar )
2768 {
2769 /* the variable could have been fixed already because it appears more than once in the clique */
2770 if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2771 {
2772 /* the fixing must have occurred previously inside this loop. It may happen that
2773 * the variable occurs together with its negation in that clique, which is usually
2774 * handled during the merge step, but leads to a direct infeasibility because it
2775 * contradicts any other variable fixed to one in this clique
2776 */
2777 if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2778 || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2779 {
2780 /* impossible because we would have detected this in the previous cleanup loop */
2781 assert(clqvar != onefixedvar);
2782 *infeasible = TRUE;
2783
2784 return SCIP_OKAY;
2785 }
2786 continue;
2787 }
2788
2789 SCIP_CALL( SCIPvarDelCliqueFromList(clqvar, blkmem, clqval, clique) );
2790
2791 /* the following piece of code is wrong at this point because it assumes sorted variables. can be enabled if sorting
2792 * of variables is performed earlier than it is now
2793 */
2794 #ifdef SCIP_DISABLED_CODE
2795 /* if one of the other variables occurs multiple times, we can
2796 * 1) deduce infeasibility if it occurs with different values
2797 * 2) wait for the last occurence to fix it
2798 */
2799 while( v < clique->nvars - 1 && clique->vars[v + 1] == clqvar )
2800 {
2801 if( clique->values[v + 1] != clique->values[v] )
2802 {
2803 *infeasible = TRUE;
2804 return SCIP_OKAY;
2805 }
2806 ++v;
2807 }
2808 #endif
2809 SCIPsetDebugMsg(set, "fixing variable %s in clique %u to %d\n", SCIPvarGetName(clqvar), clique->id, clqval ? 0 : 1);
2810
2811 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2812 eventqueue, cliquetable, !clqval, infeasible, nchgbds) );
2813
2814 if( *infeasible )
2815 return SCIP_OKAY;
2816 }
2817 }
2818
2819 if( SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_COLUMN /*lint !e850*/
2820 || SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_LOOSE )
2821 {
2822 SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2823 }
2824
2825 clique->nvars = 0;
2826 clique->equation = FALSE;
2827 clique->startcleanup = -1;
2828
2829 return SCIP_OKAY;
2830 }
2831
2832 if( clique->equation )
2833 {
2834 if( clique->nvars == 0 )
2835 {
2836 *infeasible = TRUE;
2837 return SCIP_OKAY;
2838 }
2839 else if( clique->nvars == 1 )
2840 {
2841 assert(SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_COLUMN
2842 || SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_LOOSE);
2843
2844 /* clearing data and removing variable from its clique list */
2845 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[0], blkmem, clique->values[0], clique) );
2846
2847 SCIPsetDebugMsg(set, "fixing last variable %s in clique %u to %d\n", SCIPvarGetName(clique->vars[0]), clique->id,
2848 clique->values[0] ? 1 : 0);
2849
2850 SCIP_CALL( SCIPvarFixBinary(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2851 branchcand, eventqueue, cliquetable, clique->values[0], infeasible, nchgbds) );
2852
2853 clique->nvars = 0;
2854 clique->equation = FALSE;
2855 clique->startcleanup = -1;
2856
2857 return SCIP_OKAY;
2858 }
2859 }
2860
2861 if( needsorting )
2862 {
2863 SCIP_Bool isequation = clique->equation;
2864
2865 /* remove multiple entries of the same variable */
2866 SCIP_CALL( sortAndMergeClique(clique->vars, clique->values, &(clique->nvars), &isequation, clique, blkmem, set, stat,
2867 transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, nchgbds, infeasible) );
2868
2869 clique->equation = isequation;
2870 }
2871
2872 /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2873
2874 clique->startcleanup = -1;
2875 }
2876 assert(SCIPcliqueIsCleanedUp(clique));
2877
2878 return SCIP_OKAY;
2879 }
2880
2881 #ifdef SCIP_MORE_DEBUG
2882 /** checks whether clique appears in all clique lists of the involved variables */
2883 static
2884 SCIP_Bool checkNEntries(
2885 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2886 )
2887 {
2888 SCIP_Longint nentries = 0;
2889 int c;
2890
2891 assert(cliquetable != NULL);
2892
2893 for( c = cliquetable->ncliques - 1; c >= 0; --c )
2894 nentries += cliquetable->cliques[c]->nvars;
2895
2896 return (nentries == cliquetable->nentries);
2897 }
2898 #else
2899 #define checkNEntries(cliquetable) TRUE
2900 #endif
2901
2902 /** removes all empty and single variable cliques from the clique table; removes double entries from the clique table
2903 *
2904 * @note cliques can be processed several times by this method
2905 *
2906 * @todo try to detect infeasible implications, e.g., x = 1 => (y = 0 && y = 1)
2907 */
2908 SCIP_RETCODE SCIPcliquetableCleanup(
2909 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2910 BMS_BLKMEM* blkmem, /**< block memory */
2911 SCIP_SET* set, /**< global SCIP settings */
2912 SCIP_STAT* stat, /**< problem statistics */
2913 SCIP_PROB* transprob, /**< transformed problem */
2914 SCIP_PROB* origprob, /**< original problem */
2915 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2916 SCIP_REOPT* reopt, /**< reoptimization data structure */
2917 SCIP_LP* lp, /**< current LP data */
2918 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2919 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2920 int* nchgbds, /**< pointer to store number of fixed variables */
2921 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2922 )
2923 {
2924 assert(cliquetable != NULL);
2925 assert(stat != NULL);
2926 assert(infeasible != NULL);
2927
2928 *infeasible = FALSE;
2929
2930 /* check if we have anything to do */
2931 if( stat->npresolfixedvars == cliquetable->ncleanupfixedvars
2932 && stat->npresolaggrvars == cliquetable->ncleanupaggrvars
2933 && cliquetable->ndirtycliques == 0 )
2934 return SCIP_OKAY;
2935
2936 SCIPsetDebugMsg(set, "cleaning up clique table with %d cliques (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
2937
2938 /* delay events */
2939 SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
2940
2941 cliquetable->incleanup = TRUE;
2942 while( cliquetable->ndirtycliques > 0 && !(*infeasible) )
2943 {
2944 SCIP_CLIQUE* clique;
2945 SCIP_CLIQUE* sameclique;
2946
2947 clique = cliquetable->cliques[0];
2948
2949 assert(!SCIPcliqueIsCleanedUp(clique));
2950
2951 /* remove not clean up clique from hastable */
2952 SCIP_CALL( SCIPhashtableRemove(cliquetable->hashtable, (void*)clique) );
2953 cliquetable->nentries -= clique->nvars;
2954 assert(cliquetable->nentries >= 0);
2955
2956 SCIP_CALL( cliqueCleanup(clique, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2957 cliquetable, nchgbds, infeasible) );
2958
2959 if( *infeasible )
2960 break;
2961
2962 assert(SCIPcliqueIsCleanedUp(clique));
2963
2964 /* swap freshly cleaned clique with last dirty clique */
2965 cliquetable->ndirtycliques--;
2966 cliquetableSwapCliques(cliquetable, 0, cliquetable->ndirtycliques);
2967 cliqueCheck(clique);
2968
2969 /* @todo check if we can/want to aggregate variables with the following code */
2970 #ifdef SCIP_DISABLED_CODE
2971 if( clique->nvars == 2 && clique->equation && SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING )
2972 {
2973 SCIP_VAR* var0;
2974 SCIP_VAR* var1;
2975 SCIP_Real scalarx;
2976 SCIP_Real scalary;
2977 SCIP_Real rhs = 1.0;
2978 SCIP_Bool aggregated;
2979
2980 printf("aggr vars, clique %u\n", clique->id);
2981
2982 if( SCIPvarGetType(clique->vars[0]) >= SCIPvarGetType(clique->vars[1]) )
2983 {
2984 var0 = clique->vars[0];
2985 var1 = clique->vars[1];
2986
2987 if( !clique->values[0] )
2988 {
2989 scalarx = -1.0;
2990 rhs -= 1.0;
2991 }
2992 else
2993 scalarx = 1.0;
2994
2995 if( !clique->values[1] )
2996 {
2997 scalary = -1.0;
2998 rhs -= 1.0;
2999 }
3000 else
3001 scalary = 1.0;
3002 }
3003 else
3004 {
3005 var0 = clique->vars[1];
3006 var1 = clique->vars[0];
3007
3008 if( !clique->values[0] )
3009 {
3010 scalary = -1.0;
3011 rhs -= 1.0;
3012 }
3013 else
3014 scalary = 1.0;
3015
3016 if( !clique->values[1] )
3017 {
3018 scalarx = -1.0;
3019 rhs -= 1.0;
3020 }
3021 else
3022 scalarx = 1.0;
3023 }
3024
3025 assert((SCIPvarGetStatus(var0) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var0) == SCIP_VARSTATUS_COLUMN)
3026 && (SCIPvarGetStatus(var1) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_COLUMN));
3027
3028 /* aggregate the variable */
3029 SCIP_CALL( SCIPvarTryAggregateVars(set, blkmem, stat, transprob, origprob, primal,
3030 tree, lp, cliquetable, branchcand, eventfilter, eventqueue,
3031 var0, var1, scalarx, scalary, rhs, infeasible, &aggregated) );
3032
3033 assert(aggregated || *infeasible);
3034 }
3035 #endif
3036
3037 sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
3038
3039 /* check if the clique is already contained in the clique table, or if it is redundant (too small) */
3040 if( clique->nvars <= 1 || sameclique != NULL )
3041 {
3042 int j;
3043
3044 /* infeasible or fixing should be performed already on trivial clique */
3045 assert(clique->nvars > 1 || !clique->equation);
3046
3047 /* if the clique which is already in the hashtable is an inequality and the current clique is an equation, we
3048 * update the equation status of the old one
3049 */
3050 if( clique->nvars > 1 && clique->equation && !sameclique->equation )
3051 {
3052 assert(sameclique->nvars >= 2);
3053
3054 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
3055 * the sameclique from the hashmap while adding the new clique
3056 */
3057 sameclique->equation = TRUE;
3058 }
3059
3060 /* delete the clique from the variables' clique lists */
3061 for( j = 0; j < clique->nvars; ++j )
3062 {
3063 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[j], blkmem, clique->values[j], clique) );
3064 }
3065
3066 /* free clique and remove it from clique table */
3067 cliqueFree(&clique, blkmem);
3068 cliquetable->ncliques--;
3069 /* insert a clean clique from the end of the array */
3070 if( cliquetable->ndirtycliques < cliquetable->ncliques )
3071 {
3072 assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ncliques]));
3073 cliquetable->cliques[cliquetable->ndirtycliques] = cliquetable->cliques[cliquetable->ncliques];
3074 cliquetable->cliques[cliquetable->ndirtycliques]->index = cliquetable->ndirtycliques;
3075 }
3076 }
3077 else
3078 {
3079 cliquetable->nentries += clique->nvars;
3080
3081 SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
3082 if( !clique->eventsissued )
3083 {
3084 int j;
3085
3086 /* issue IMPLADDED event on each variable in the clique */
3087 for( j = 0; j < clique->nvars; ++j )
3088 {
3089 SCIP_EVENT* event;
3090
3091 SCIP_CALL( SCIPeventCreateImplAdded(&event, blkmem, clique->vars[j]) );
3092 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3093 }
3094 clique->eventsissued = TRUE;
3095 }
3096 }
3097 }
3098 cliquetable->incleanup = FALSE;
3099
3100 /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */
3101 cliquetable->ncleanupfixedvars = stat->npresolfixedvars;
3102 cliquetable->ncleanupaggrvars = stat->npresolaggrvars;
3103 assert(*infeasible || cliquetable->ndirtycliques == 0);
3104
3105 assert(*infeasible || checkNEntries(cliquetable)); /*lint !e506*/
3106
3107 SCIPsetDebugMsg(set, "cleaned up clique table has %d cliques left (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
3108
3109 /* process events */
3110 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, NULL, lp, branchcand, NULL) );
3111
3112 return SCIP_OKAY;
3113 }
3114
3115 /** computes connected components of the clique table
3116 *
3117 * an update becomes necessary if a clique gets added with variables from different components
3118 */
3119 SCIP_RETCODE SCIPcliquetableComputeCliqueComponents(
3120 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3121 SCIP_SET* set, /**< global SCIP settings */
3122 BMS_BLKMEM* blkmem, /**< block memory */
3123 SCIP_VAR** vars, /**< array of problem variables, sorted by variable type */
3124 int nbinvars, /**< number of binary variables */
3125 int nintvars, /**< number of integer variables */
3126 int nimplvars /**< number of implicit integer variables */
3127 )
3128 {
3129 SCIP_DISJOINTSET* djset;
3130 int nimplbinvars;
3131 int v;
3132 int c;
3133 int nbinvarstotal;
3134 int ndiscvars;
3135 int nnonbinvars;
3136
3137 SCIP_CLIQUE** cliques;
3138
3139 assert(cliquetable != NULL);
3140 assert(vars != NULL);
3141
3142 nimplbinvars = 0;
3143 cliquetable->compsfromscratch = FALSE;
3144 ndiscvars = nbinvars + nintvars + nimplvars;
3145
3146 /* detect integer and implicit integer variables with bounds {0,1} because they might appear in cliques, as well */
3147 for( v = nbinvars; v < ndiscvars; ++v )
3148 {
3149 if( SCIPvarIsBinary(vars[v]) )
3150 ++nimplbinvars;
3151 }
3152
3153 /* count binary and implicit binary variables */
3154 nbinvarstotal = nbinvars + nimplbinvars;
3155
3156 /* if there are no binary variables, return */
3157 if( nbinvarstotal == 0 )
3158 {
3159 SCIPsetDebugMsg(set, "0 binary variables in total --> 0 connected components in the clique table");
3160 cliquetable->ncliquecomponents = 0;
3161 return SCIP_OKAY;
3162 }
3163
3164 /* no cliques are present */
3165 if( cliquetable->ncliques == 0 )
3166 {
3167 SCIPsetDebugMsg(set, "0 cliques --> Clique table has %d isolated nodes", nbinvarstotal);
3168 cliquetable->ncliquecomponents = nbinvarstotal;
3169 return SCIP_OKAY;
3170 }
3171
3172 /* create or clear the variable index mapping */
3173 if( cliquetable->varidxtable == NULL )
3174 {
3175 SCIP_CALL( SCIPhashmapCreate(&(cliquetable)->varidxtable, blkmem, ndiscvars) );
3176 }
3177 else
3178 {
3179 SCIP_CALL( SCIPhashmapRemoveAll(cliquetable->varidxtable) );
3180 }
3181
3182 /* loop through variables and store their respective positions in the hash map if they are binary */
3183 for( v = 0; v < ndiscvars; ++v )
3184 {
3185 SCIP_VAR* var = vars[v];
3186 if( SCIPvarIsBinary(var) )
3187 {
3188 /* consider only active representatives */
3189 if( SCIPvarIsActive(var) )
3190 {
3191 SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3192 }
3193 else
3194 {
3195 var = SCIPvarGetProbvar(var);
3196 if( SCIPvarIsActive(var) )
3197 {
3198 SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3199 }
3200 }
3201 }
3202 }
3203
3204 /* free previous disjoint set (union find) data structure which has become outdated if new variables are present */
3205 if( cliquetable->djset != NULL )
3206 SCIPdisjointsetFree(&cliquetable->djset, blkmem);
3207
3208 /* we need to consider integer and implicit integer variables for which SCIPvarIsBinary() returns TRUE.
3209 * These may be scattered across the ninteger + nimplvars implicit integer variables.
3210 * For simplicity, we add all integer and implicit integer variables as nodes to the graph, and subtract
3211 * the amount of nonbinary integer and implicit integer variables afterwards.
3212 */
3213 SCIP_CALL( SCIPdisjointsetCreate(&cliquetable->djset, blkmem, ndiscvars) );
3214 djset = cliquetable->djset;
3215
3216 /* subtract all (implicit) integer for which SCIPvarIsBinary() returns FALSE */
3217 nnonbinvars = (nintvars + nimplvars) - nimplbinvars;
3218
3219 cliques = cliquetable->cliques;
3220
3221 /* for every clique, we connect clique variable components, treating a clique as a path
3222 *
3223 * if the graph turns out to be completely connected (except for the nonbinary variables), we terminate */
3224 for( c = 0; c < cliquetable->ncliques && SCIPdisjointsetGetComponentCount(djset) > 1 + nnonbinvars; ++c )
3225 {
3226 SCIP_CLIQUE* clique;
3227
3228 clique = cliques[c];
3229 cliquetableUpdateConnectednessClique(cliquetable, clique);
3230 }
3231
3232 /* subtract superfluous integer and implicit integer variables added to the auxiliary graph */
3233 cliquetable->ncliquecomponents = SCIPdisjointsetGetComponentCount(djset) - nnonbinvars;
3234 assert(cliquetable->ncliquecomponents >= 0);
3235 assert(cliquetable->ncliquecomponents <= nbinvarstotal);
3236
3237 SCIPsetDebugMsg(set, "connected components detection: %d comps (%d clqs, %d vars)", cliquetable->ncliquecomponents, cliquetable->ncliques, nbinvarstotal);
3238
3239 return SCIP_OKAY;
3240 }
3241
3242 /*
3243 * simple functions implemented as defines
3244 */
3245
3246 /* In debug mode, the following methods are implemented as function calls to ensure
3247 * type validity.
3248 * In optimized mode, the methods are implemented as defines to improve performance.
3249 * However, we want to have them in the library anyways, so we have to undef the defines.
3250 */
3251
3252 #undef SCIPvboundsGetNVbds
3253 #undef SCIPvboundsGetVars
3254 #undef SCIPvboundsGetCoefs
3255 #undef SCIPvboundsGetConstants
3256 #undef SCIPimplicsGetNImpls
3257 #undef SCIPimplicsGetVars
3258 #undef SCIPimplicsGetTypes
3259 #undef SCIPimplicsGetBounds
3260 #undef SCIPimplicsGetIds
3261 #undef SCIPcliqueGetNVars
3262 #undef SCIPcliqueGetVars
3263 #undef SCIPcliqueGetValues
3264 #undef SCIPcliqueGetId
3265 #undef SCIPcliqueGetIndex
3266 #undef SCIPcliqueIsCleanedUp
3267 #undef SCIPcliqueIsEquation
3268 #undef SCIPcliquelistGetNCliques
3269 #undef SCIPcliquelistGetCliques
3270 #undef SCIPcliquelistCheck
3271 #undef SCIPcliquetableGetNCliques
3272 #undef SCIPcliquetableGetCliques
3273 #undef SCIPcliquetableGetNEntries
3274 #undef SCIPcliquetableGetNCliqueComponents
3275 #undef SCIPcliquetableNeedsComponentUpdate
3276
3277 /** gets number of variable bounds contained in given variable bounds data structure */
3278 int SCIPvboundsGetNVbds(
3279 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3280 )
3281 {
3282 return vbounds != NULL ? vbounds->len : 0;
3283 }
3284
3285 /** gets array of variables contained in given variable bounds data structure */
3286 SCIP_VAR** SCIPvboundsGetVars(
3287 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3288 )
3289 {
3290 return vbounds != NULL ? vbounds->vars : NULL;
3291 }
3292
3293 /** gets array of coefficients contained in given variable bounds data structure */
3294 SCIP_Real* SCIPvboundsGetCoefs(
3295 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3296 )
3297 {
3298 return vbounds != NULL ? vbounds->coefs : NULL;
3299 }
3300
3301 /** gets array of constants contained in given variable bounds data structure */
3302 SCIP_Real* SCIPvboundsGetConstants(
3303 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3304 )
3305 {
3306 return vbounds != NULL ? vbounds->constants : NULL;
3307 }
3308
3309 /** gets number of implications for a given binary variable fixing */
3310 int SCIPimplicsGetNImpls(
3311 SCIP_IMPLICS* implics, /**< implication data */
3312 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3313 )
3314 {
3315 return implics != NULL ? implics->nimpls[varfixing] : 0;
3316 }
3317
3318 /** gets array with implied variables for a given binary variable fixing */
3319 SCIP_VAR** SCIPimplicsGetVars(
3320 SCIP_IMPLICS* implics, /**< implication data */
3321 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3322 )
3323 {
3324 return implics != NULL ? implics->vars[varfixing] : NULL;
3325 }
3326
3327 /** gets array with implication types for a given binary variable fixing */
3328 SCIP_BOUNDTYPE* SCIPimplicsGetTypes(
3329 SCIP_IMPLICS* implics, /**< implication data */
3330 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3331 )
3332 {
3333 return implics != NULL ? implics->types[varfixing] : NULL;
3334 }
3335
3336 /** gets array with implication bounds for a given binary variable fixing */
3337 SCIP_Real* SCIPimplicsGetBounds(
3338 SCIP_IMPLICS* implics, /**< implication data */
3339 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3340 )
3341 {
3342 return implics != NULL ? implics->bounds[varfixing] : NULL;
3343 }
3344
3345 /** Gets array with unique implication identifiers for a given binary variable fixing.
3346 * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
3347 * its id is negative, otherwise it is nonnegative.
3348 */
3349 int* SCIPimplicsGetIds(
3350 SCIP_IMPLICS* implics, /**< implication data */
3351 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3352 )
3353 {
3354 return implics != NULL ? implics->ids[varfixing] : NULL;
3355 }
3356
3357 /** gets number of variables in the cliques */
3358 int SCIPcliqueGetNVars(
3359 SCIP_CLIQUE* clique /**< clique data structure */
3360 )
3361 {
3362 assert(clique != NULL);
3363
3364 return clique->nvars;
3365 }
3366
3367 /** gets array of active problem variables in the cliques */
3368 SCIP_VAR** SCIPcliqueGetVars(
3369 SCIP_CLIQUE* clique /**< clique data structure */
3370 )
3371 {
3372 assert(clique != NULL);
3373
3374 return clique->vars;
3375 }
3376
3377 /** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or
3378 * to TRUE in the clique
3379 */
3380 SCIP_Bool* SCIPcliqueGetValues(
3381 SCIP_CLIQUE* clique /**< clique data structure */
3382 )
3383 {
3384 assert(clique != NULL);
3385
3386 return clique->values;
3387 }
3388
3389 /** gets unique identifier of the clique */
3390 unsigned int SCIPcliqueGetId(
3391 SCIP_CLIQUE* clique /**< clique data structure */
3392 )
3393 {
3394 unsigned int id;
3395
3396 assert(clique != NULL);
3397
3398 id = clique->id; /*lint !e732*/
3399
3400 return id;
3401 }
3402
3403 /** gets index of the clique in the clique table */
3404 int SCIPcliqueGetIndex(
3405 SCIP_CLIQUE* clique /**< clique data structure */
3406 )
3407 {
3408 assert(clique != NULL);
3409
3410 return clique->index;
3411 }
3412
3413 /** gets unique identifier of the clique */
3414 SCIP_Bool SCIPcliqueIsCleanedUp(
3415 SCIP_CLIQUE* clique /**< clique data structure */
3416 )
3417 {
3418 assert(clique != NULL);
3419
3420 return (clique->startcleanup == -1);
3421 }
3422
3423 /** return whether the given clique is an equation */
3424 SCIP_Bool SCIPcliqueIsEquation(
3425 SCIP_CLIQUE* clique /**< clique data structure */
3426 )
3427 {
3428 assert(clique != NULL);
3429
3430 return (SCIP_Bool)(clique->equation); /*lint !e571*/
3431 }
3432
3433 /** returns the number of cliques stored in the clique list */
3434 int SCIPcliquelistGetNCliques(
3435 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3436 SCIP_Bool value /**< value of the variable for which the cliques should be returned */
3437 )
3438 {
3439 return cliquelist != NULL ? cliquelist->ncliques[value] : 0;
3440 }
3441
3442 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */
3443 SCIP_CLIQUE** SCIPcliquelistGetCliques(
3444 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3445 SCIP_Bool value /**< value of the variable for which the cliques should be returned */
3446 )
3447 {
3448 return cliquelist != NULL ? cliquelist->cliques[value] : NULL;
3449 }
3450
3451 /** checks whether variable is contained in all cliques of the cliquelist */
3452 void SCIPcliquelistCheck(
3453 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3454 SCIP_VAR* var /**< variable, the clique list belongs to */
3455 )
3456 {
3457 /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MORE_DEBUG because it can take at lot of time to check for
3458 * correctness
3459 */
3460 #ifndef NDEBUG
3461 int value;
3462
3463 assert(SCIPvarGetNCliques(var, FALSE) == SCIPcliquelistGetNCliques(cliquelist, FALSE));
3464 assert(SCIPvarGetCliques(var, FALSE) == SCIPcliquelistGetCliques(cliquelist, FALSE));
3465 assert(SCIPvarGetNCliques(var, TRUE) == SCIPcliquelistGetNCliques(cliquelist, TRUE));
3466 assert(SCIPvarGetCliques(var, TRUE) == SCIPcliquelistGetCliques(cliquelist, TRUE));
3467
3468 for( value = 0; value < 2; ++value )
3469 {
3470 SCIP_CLIQUE** cliques;
3471 int ncliques;
3472 int i;
3473
3474 ncliques = SCIPcliquelistGetNCliques(cliquelist, (SCIP_Bool)value);
3475 cliques = SCIPcliquelistGetCliques(cliquelist, (SCIP_Bool)value);
3476 for( i = 0; i < ncliques; ++i )
3477 {
3478 SCIP_CLIQUE* clique;
3479 int pos;
3480
3481 clique = cliques[i];
3482 assert(clique != NULL);
3483
3484 pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value);
3485 assert(0 <= pos && pos < clique->nvars);
3486 assert(clique->vars[pos] == var);
3487 assert(clique->values[pos] == (SCIP_Bool)value);
3488 }
3489 }
3490 #endif
3491 }
3492
3493 /** gets the number of cliques stored in the clique table */
3494 int SCIPcliquetableGetNCliques(
3495 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3496 )
3497 {
3498 assert(cliquetable != NULL);
3499
3500 return cliquetable->ncliques;
3501 }
3502
3503 /** gets the number of cliques created so far by the clique table */
3504 int SCIPcliquetableGetNCliquesCreated(
3505 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3506 )
3507 {
3508 assert(cliquetable != NULL);
3509
3510 return cliquetable->ncreatedcliques;
3511 }
3512
3513 /** gets the array of cliques stored in the clique table */
3514 SCIP_CLIQUE** SCIPcliquetableGetCliques(
3515 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3516 )
3517 {
3518 assert(cliquetable != NULL);
3519
3520 return cliquetable->cliques;
3521 }
3522
3523 /** gets the number of entries in the whole clique table */
3524 SCIP_Longint SCIPcliquetableGetNEntries(
3525 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3526 )
3527 {
3528 assert(cliquetable != NULL);
3529
3530 return cliquetable->nentries;
3531 }
3532
3533 /** returns the number of clique components, or -1 if update is necessary first */
3534 int SCIPcliquetableGetNCliqueComponents(
3535 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3536 )
3537 {
3538 return cliquetable->compsfromscratch ? -1 : cliquetable->ncliquecomponents;
3539 }
3540
3541 /** returns TRUE iff the connected clique components need an update (because new cliques were added) */
3542 SCIP_Bool SCIPcliquetableNeedsComponentUpdate(
3543 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3544 )
3545 {
3546 return cliquetable->compsfromscratch || cliquetable->djset == NULL;
3547 }
3548