Scippy

SCIP

Solving Constraint Integer Programs

implics.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 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
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 */
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
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
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 */
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);
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 */
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 */
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
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
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
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 */
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
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
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
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  */
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));
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 */
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 */
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 */
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 */
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
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
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
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
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
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  */
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 */
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 */
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);
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 */
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
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
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 */
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
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 */
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 */
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  */
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 */
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 */
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 */
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
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
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 */
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 
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
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
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 */
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  */
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 
2434  assert(SCIPvarIsBinary(var));
2435 
2436  /* if we have a variables already fixed to one in the clique, fix all other to zero */
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 ||
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
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;
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) ||
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
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  */
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 
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  */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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  */
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 */
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 */
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  */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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) */
3543  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3544  )
3545 {
3546  return cliquetable->compsfromscratch || cliquetable->djset == NULL;
3547 }
SCIP_CLIQUE ** cliques
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
void SCIPcliquelistRemoveFromCliques(SCIP_CLIQUELIST *cliquelist, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Bool irrelevantvar)
Definition: implics.c:1674
#define HASHTABLE_CLIQUETABLE_SIZE
Definition: implics.c:1774
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6200
static int cliquetableGetNodeIndexBinvar(SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *binvar)
Definition: implics.c:2252
SCIP_HASHMAP * varidxtable
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:461
internal methods for managing events
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3368
int SCIPcliquetableGetVarComponentIdx(SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var)
Definition: implics.c:2339
static SCIP_Bool implicsSearchImplic(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, int *poslower, int *posupper, int *posadd)
Definition: implics.c:587
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:141
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11175
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
void SCIPimplicsGetVarImplics(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_Bool *haslowerimplic, SCIP_Bool *hasupperimplic)
Definition: implics.c:885
SCIP_RETCODE SCIPeventqueueProcess(SCIP_EVENTQUEUE *eventqueue, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter)
Definition: event.c:2487
SCIP_HASHTABLE * hashtable
SCIP_Longint SCIPcliquetableGetNEntries(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3524
SCIP_RETCODE SCIPcliqueAddVar(SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_VAR *var, SCIP_Bool value, SCIP_Bool *doubleentry, SCIP_Bool *oppositeentry)
Definition: implics.c:1142
#define SCIPsetDuplicateBufferArray(set, ptr, source, num)
Definition: set.h:1727
public methods for implications, variable bounds, and cliques
methods for implications, variable bounds, and cliques
SCIP_RETCODE SCIPeventqueueAdd(SCIP_EVENTQUEUE *eventqueue, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENT **event)
Definition: event.c:2231
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:12309
SCIP_Real * constants
#define SCIP_HASHSIZE_CLIQUES_SMALL
Definition: def.h:308
SCIP_RETCODE SCIPeventCreateImplAdded(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_VAR *var)
Definition: event.c:805
SCIP_VAR ** SCIPimplicsGetVars(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3319
int npresolaggrvars
Definition: struct_stat.h:238
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18273
static SCIP_RETCODE cliquetableEnsureSize(SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, int num)
Definition: implics.c:1850
int npresolfixedvars
Definition: struct_stat.h:237
int SCIPcliquelistGetNCliques(SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)
Definition: implics.c:3434
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
SCIP_VAR ** SCIPvboundsGetVars(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3286
#define SCIPdebugCheckClique(set, vars, values, nvars)
Definition: debug.h:276
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1132
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3404
static SCIP_RETCODE cliqueCleanup(SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, int *nchgbds, SCIP_Bool *infeasible)
Definition: implics.c:2637
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
static SCIP_RETCODE implicsEnsureSize(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool varfixing, int num)
Definition: implics.c:465
static SCIP_DECL_HASHKEYVAL(hashkeyvalClique)
Definition: implics.c:1763
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6312
SCIP_RETCODE SCIPeventqueueDelay(SCIP_EVENTQUEUE *eventqueue)
Definition: event.c:2472
SCIP_RETCODE SCIPvboundsDel(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, SCIP_VAR *vbdvar, SCIP_Bool negativecoef)
Definition: implics.c:279
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3424
SCIP_RETCODE SCIPcliquetableCreate(SCIP_CLIQUETABLE **cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem)
Definition: implics.c:1777
void SCIPimplicsGetVarImplicPoss(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, int *lowerimplicpos, int *upperimplicpos)
Definition: implics.c:907
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition: set.h:1725
#define checkNEntries(cliquetable)
Definition: implics.c:2899
static SCIP_RETCODE cliquelistCreate(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
Definition: implics.c:1413
SCIP_RETCODE SCIPcliquetableCleanup(SCIP_CLIQUETABLE *cliquetable, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, int *nchgbds, SCIP_Bool *infeasible)
Definition: implics.c:2908
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5779
public methods for problem variables
unsigned int eventsissued
SCIP_RETCODE SCIPimplicsDel(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: implics.c:827
SCIP_RETCODE SCIPcliquetableFree(SCIP_CLIQUETABLE **cliquetable, BMS_BLKMEM *blkmem)
Definition: implics.c:1813
#define SCIPdebugMessage
Definition: pub_message.h:87
int SCIPdisjointsetGetSize(SCIP_DISJOINTSET *djset)
Definition: misc.c:11255
SCIP_CLIQUE ** SCIPcliquelistGetCliques(SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)
Definition: implics.c:3443
SCIP_VAR ** vars[2]
SCIP_RETCODE SCIPcliquelistAdd(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: implics.c:1473
#define SCIPsetFreeBufferArray(set, ptr)
Definition: set.h:1732
#define BMSfreeMemory(ptr)
Definition: memory.h:138
SCIP_Real * coefs
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17736
static void implicsSearchVar(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, int *poslower, int *posupper, int *posadd)
Definition: implics.c:503
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18262
Definition: heur_padm.c:123
static void cliquetableSwapCliques(SCIP_CLIQUETABLE *cliquetable, int first, int second)
Definition: implics.c:947
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2236
static void cliquetableMarkCliqueForCleanup(SCIP_CLIQUETABLE *cliquetable, SCIP_CLIQUE *clique)
Definition: implics.c:973
SCIP_RETCODE SCIPvboundsAdd(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_BOUNDTYPE vboundtype, SCIP_VAR *var, SCIP_Real coef, SCIP_Real constant, SCIP_Bool *added)
Definition: implics.c:197
int SCIPcliquetableGetNCliquesCreated(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3504
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
static SCIP_RETCODE cliqueCreateWithData(SCIP_CLIQUE **clique, BMS_BLKMEM *blkmem, int size, SCIP_VAR **vars, SCIP_Bool *values, int nvars, int id, SCIP_Bool isequation)
Definition: implics.c:995
int * ids[2]
#define SCIP_HASHSIZE_CLIQUES
Definition: def.h:305
void SCIPcliquelistFree(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
Definition: implics.c:1432
int SCIPcliqueSearchVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1072
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12217
int SCIPcliquetableGetNCliques(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3494
SCIP_VAR * w
Definition: circlepacking.c:58
SCIP_Bool compsfromscratch
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:455
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:515
SCIP_BOUNDTYPE * SCIPimplicsGetTypes(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3328
void SCIPcliqueDelVar(SCIP_CLIQUE *clique, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1276
SCIP_Bool SCIPimplicsContainsImpl(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: implics.c:924
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11226
SCIP_RETCODE SCIPimplicsAdd(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool isshortcut, SCIP_Bool *conflict, SCIP_Bool *added)
Definition: implics.c:624
void SCIPsortPtrBool(void **ptrarray, SCIP_Bool *boolarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
static SCIP_DECL_HASHGETKEY(hashgetkeyClique)
Definition: implics.c:1730
#define BMSmoveMemoryArray(ptr, source, num)
Definition: memory.h:131
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
static int cliquesSearchClique(SCIP_CLIQUE **cliques, int ncliques, SCIP_CLIQUE *clique)
Definition: implics.c:1324
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real * SCIPvboundsGetCoefs(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3294
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11148
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
static void checkImplics(SCIP_IMPLICS *implics)
Definition: implics.c:374
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6686
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2617
SCIP_VAR ** vars
SCIP_Real * SCIPvboundsGetConstants(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3302
Definition: graph_load.c:93
static void cliquetableUpdateConnectednessClique(SCIP_CLIQUETABLE *cliquetable, SCIP_CLIQUE *clique)
Definition: implics.c:2295
unsigned int equation
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11245
SCIP_Bool SCIPcliquelistsHaveCommonClique(SCIP_CLIQUELIST *cliquelist1, SCIP_Bool value1, SCIP_CLIQUELIST *cliquelist2, SCIP_Bool value2)
Definition: implics.c:1596
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6642
int SCIPcliquetableGetNCliqueComponents(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3534
void SCIPvboundsShrink(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, int newnvbds)
Definition: implics.c:324
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:458
SCIP_Bool * values
internal methods for problem variables
SCIP_Real * bounds[2]
SCIP_RETCODE SCIPvarTryAggregateVars(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_CLIQUETABLE *cliquetable, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition: var.c:5275
datastructures for implications, variable bounds, and cliques
public data structures and miscellaneous methods
SCIP_Bool SCIPcliquetableNeedsComponentUpdate(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3542
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3573
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:460
int * SCIPimplicsGetIds(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3349
SCIP_RETCODE SCIPcliquetableComputeCliqueComponents(SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_VAR **vars, int nbinvars, int nintvars, int nimplvars)
Definition: implics.c:3119
#define MAX(x, y)
Definition: tclique_def.h:83
int SCIPimplicsGetNImpls(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3310
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3380
#define SCIPsetDebugMsg
Definition: set.h:1761
SCIP_RETCODE SCIPvarAddCliqueToList(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: var.c:11392
static SCIP_DECL_HASHKEYEQ(hashkeyeqClique)
Definition: implics.c:1737
SCIP_BOUNDTYPE * types[2]
#define cliqueCheck(clique)
Definition: implics.c:1408
SCIP_VAR ** vars
SCIP_RETCODE SCIPvarFixBinary(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool value, SCIP_Bool *infeasible, int *nbdchgs)
Definition: var.c:11178
datastructures for problem statistics
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6620
SCIP_RETCODE SCIPcliquetableAdd(SCIP_CLIQUETABLE *cliquetable, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
Definition: implics.c:2367
static SCIP_RETCODE vboundsCreate(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem)
Definition: implics.c:46
SCIP_Longint nnz
Definition: struct_stat.h:180
int SCIPvboundsGetNVbds(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3278
static void cliqueFree(SCIP_CLIQUE **clique, BMS_BLKMEM *blkmem)
Definition: implics.c:1029
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2286
static SCIP_RETCODE cliqueEnsureSize(SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
Definition: implics.c:1046
SCIP_DISJOINTSET * djset
methods for sorting joint arrays of various types
static SCIP_RETCODE vboundsSearchPos(SCIP_VBOUNDS *vbounds, SCIP_VAR *var, SCIP_Bool negativecoef, int *insertpos, SCIP_Bool *found)
Definition: implics.c:116
static SCIP_RETCODE sortAndMergeClique(SCIP_VAR **clqvars, SCIP_Bool *clqvalues, int *nclqvars, SCIP_Bool *isequation, SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, int *nbdchgs, SCIP_Bool *infeasible)
Definition: implics.c:1873
static SCIP_DECL_SORTPTRCOMP(compVars)
Definition: implics.c:350
static SCIP_RETCODE vboundsEnsureSize(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
Definition: implics.c:82
unsigned int id
public methods for message output
void SCIPcliquelistCheck(SCIP_CLIQUELIST *cliquelist, SCIP_VAR *var)
Definition: implics.c:3452
SCIP_CLIQUE ** cliques[2]
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
#define SCIP_Real
Definition: def.h:177
SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
Definition: var.c:12277
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:120
#define SCIP_Longint
Definition: def.h:162
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
Definition: implics.c:3390
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:11108
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6664
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
static SCIP_RETCODE cliquelistEnsureSize(SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, int num)
Definition: implics.c:1449
SCIP_STAGE SCIPsetGetStage(SCIP_SET *set)
Definition: set.c:2982
SCIP_Bool SCIPvarIsMarkedDeleteGlobalStructures(SCIP_VAR *var)
Definition: var.c:17518
SCIP_Bool SCIPcliqueIsCleanedUp(SCIP_CLIQUE *clique)
Definition: implics.c:3414
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3358
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:444
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIP_Real * SCIPimplicsGetBounds(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3337
#define SCIP_ALLOC(x)
Definition: def.h:395
static SCIP_RETCODE implicsCreate(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem)
Definition: implics.c:416
void SCIPvboundsFree(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem)
Definition: implics.c:64
SCIP_RETCODE SCIPvarsAddClique(SCIP_VAR **vars, SCIP_Bool *values, int nvars, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_CLIQUE *clique)
Definition: var.c:11354
datastructures for global SCIP settings
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:451
SCIP_CLIQUE ** SCIPcliquetableGetCliques(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3514
void SCIPimplicsFree(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem)
Definition: implics.c:442
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
SCIP_RETCODE SCIPcliquelistDel(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: implics.c:1518
SCIP_Longint nentries
int nimplications
Definition: struct_stat.h:232
SCIP_RETCODE SCIPvarDelCliqueFromList(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: var.c:11414