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-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file implics.c
17  * @ingroup OTHER_CFILES
18  * @brief methods for implications, variable bounds, and clique tables
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "scip/event.h"
25 #include "scip/implics.h"
26 #include "scip/misc.h"
27 #include "scip/pub_implics.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_misc_sort.h"
31 #include "scip/pub_var.h"
32 #include "scip/set.h"
33 #include "scip/struct_implics.h"
34 #include "scip/struct_set.h"
35 #include "scip/struct_stat.h"
36 #include "scip/var.h"
37 
38 
39 
40 /*
41  * methods for variable bounds
42  */
43 
44 /** creates a variable bounds data structure */
45 static
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 whether an implication y <= b or y >= b is 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  SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */
912  )
913 {
914  int poslower;
915  int posupper;
916  int posadd;
917 
918  return implicsSearchImplic(implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); /*lint !e438*/
919 } /*lint !e638*/
920 
921 
922 
923 
924 /*
925  * methods for cliques
926  */
927 
928 /* swaps cliques at positions first and second in cliques array of clique table */
929 static
931  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
932  int first, /**< first index */
933  int second /**< second index */
934  )
935 {
936  /* nothing to do if clique happens to be at the pole position of clean cliques */
937  if( first != second )
938  {
939  SCIP_CLIQUE* tmp;
940 
941  tmp = cliquetable->cliques[first];
942  assert(tmp->index == first);
943  assert(cliquetable->cliques[second]->index == second);
944 
945  cliquetable->cliques[first] = cliquetable->cliques[second];
946  cliquetable->cliques[second] = tmp;
947 
948  /* change the indices accordingly */
949  tmp->index = second;
950  cliquetable->cliques[first]->index = first;
951  }
952 }
953 
954 /* moves clique to the last position of currently dirty cliques */
955 static
957  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
958  SCIP_CLIQUE* clique /**< clique data structure */
959  )
960 {
961  assert(cliquetable->ndirtycliques <= clique->index);
962  assert(cliquetable->cliques[clique->index] == clique);
963  assert(cliquetable->ndirtycliques < cliquetable->ncliques);
964  assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ndirtycliques]));
965 
966  /* nothing to do if clique happens to be at the pole position of clean cliques */
967  if( clique->index > cliquetable->ndirtycliques )
968  {
969  cliquetableSwapCliques(cliquetable, clique->index, cliquetable->ndirtycliques);
970  }
971 
972  ++cliquetable->ndirtycliques;
973 }
974 
975 
976 /** creates a clique data structure with already created variables and values arrays in the size of 'size' */
977 static
979  SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
980  BMS_BLKMEM* blkmem, /**< block memory */
981  int size, /**< initial size of clique */
982  SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given
983  * value */
984  SCIP_Bool* values, /**< values of the variables in the clique */
985  int nvars, /**< number of variables in the clique */
986  int id, /**< unique identifier of the clique */
987  SCIP_Bool isequation /**< is the clique an equation or an inequality? */
988  )
989 {
990  assert(clique != NULL);
991  assert(blkmem != NULL);
992  assert(size >= nvars && nvars > 0);
993  assert(vars != NULL);
994  assert(values != NULL);
995 
996  SCIP_ALLOC( BMSallocBlockMemory(blkmem, clique) );
997  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->vars, vars, size) );
998  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->values, values, size) );
999  (*clique)->nvars = nvars;
1000  (*clique)->size = size;
1001  (*clique)->startcleanup = -1;
1002  (*clique)->id = (unsigned int)id;
1003  (*clique)->eventsissued = FALSE;
1004  (*clique)->equation = isequation;
1005  (*clique)->index = -1;
1006 
1007  return SCIP_OKAY;
1008 }
1009 
1010 /** frees a clique data structure */
1011 static
1013  SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
1014  BMS_BLKMEM* blkmem /**< block memory */
1015  )
1016 {
1017  assert(clique != NULL);
1018 
1019  if( *clique != NULL )
1020  {
1021  BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->vars, (*clique)->size);
1022  BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->values, (*clique)->size);
1023  BMSfreeBlockMemory(blkmem, clique);
1024  }
1025 }
1026 
1027 /** ensures, that clique arrays can store at least num entries */
1028 static
1030  SCIP_CLIQUE* clique, /**< clique data structure */
1031  BMS_BLKMEM* blkmem, /**< block memory */
1032  SCIP_SET* set, /**< global SCIP settings */
1033  int num /**< minimum number of entries to store */
1034  )
1035 {
1036  assert(clique != NULL);
1037 
1038  if( num > clique->size )
1039  {
1040  int newsize;
1041 
1042  newsize = SCIPsetCalcMemGrowSize(set, num);
1043  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->vars, clique->size, newsize) );
1044  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->values, clique->size, newsize) );
1045  clique->size = newsize;
1046  }
1047  assert(num <= clique->size);
1048 
1049  return SCIP_OKAY;
1050 }
1051 
1052 /** returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member
1053  * of the clique
1054  */
1056  SCIP_CLIQUE* clique, /**< clique data structure */
1057  SCIP_VAR* var, /**< variable to search for */
1058  SCIP_Bool value /**< value of the variable in the clique */
1059  )
1060 {
1061  int varidx;
1062  int left;
1063  int right;
1064 
1065  assert(clique != NULL);
1066 
1067  varidx = SCIPvarGetIndex(var);
1068  left = -1;
1069  right = clique->nvars;
1070  while( left < right-1 )
1071  {
1072  int middle;
1073  int idx;
1074 
1075  middle = (left+right)/2;
1076  idx = SCIPvarGetIndex(clique->vars[middle]);
1077  assert(idx >= 0);
1078  if( varidx < idx )
1079  right = middle;
1080  else if( varidx > idx )
1081  left = middle;
1082  else
1083  {
1084  assert(var == clique->vars[middle]);
1085 
1086  /* now watch out for the correct value */
1087  if( clique->values[middle] < value )
1088  {
1089  int i;
1090  for( i = middle+1; i < clique->nvars && clique->vars[i] == var; ++i )
1091  {
1092  if( clique->values[i] == value )
1093  return i;
1094  }
1095  return -1;
1096  }
1097  if( clique->values[middle] > value )
1098  {
1099  int i;
1100  for( i = middle-1; i >= 0 && clique->vars[i] == var; --i )
1101  {
1102  if( clique->values[i] == value )
1103  return i;
1104  }
1105  return -1;
1106  }
1107  return middle;
1108  }
1109  }
1110 
1111  return -1;
1112 }
1113 
1114 /** returns whether the given variable/value pair is member of the given clique */
1116  SCIP_CLIQUE* clique, /**< clique data structure */
1117  SCIP_VAR* var, /**< variable to remove from the clique */
1118  SCIP_Bool value /**< value of the variable in the clique */
1119  )
1120 {
1121  return (SCIPcliqueSearchVar(clique, var, value) >= 0);
1122 }
1123 
1124 /** adds a single variable to the given clique */
1126  SCIP_CLIQUE* clique, /**< clique data structure */
1127  BMS_BLKMEM* blkmem, /**< block memory */
1128  SCIP_SET* set, /**< global SCIP settings */
1129  SCIP_VAR* var, /**< variable to add to the clique */
1130  SCIP_Bool value, /**< value of the variable in the clique */
1131  SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */
1132  SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */
1133  )
1134 {
1135  int pos;
1136  int i;
1137 
1138  assert(clique != NULL);
1140  assert(SCIPvarIsBinary(var));
1141  assert(doubleentry != NULL);
1142  assert(oppositeentry != NULL);
1143 
1144  SCIPsetDebugMsg(set, "adding variable <%s> == %u to clique %u\n", SCIPvarGetName(var), value, clique->id);
1145 
1146  *doubleentry = FALSE;
1147  *oppositeentry = FALSE;
1148 
1149  /* allocate memory */
1150  SCIP_CALL( cliqueEnsureSize(clique, blkmem, set, clique->nvars+1) );
1151 
1152  /* search for insertion position by binary variable, note that first the entries are order after variable index and
1153  * second after the bool value of the corresponding variable
1154  */
1155  (void) SCIPsortedvecFindPtr((void**) clique->vars, SCIPvarComp, var, clique->nvars, &pos);
1156 
1157  assert(pos >= 0 && pos <= clique->nvars);
1158  /* remember insertion position for later, pos might change */
1159  i = pos;
1160 
1161  if( pos < clique->nvars )
1162  {
1163  const int amount = clique->nvars - pos;
1164 
1165  /* moving elements to correct position */
1166  BMSmoveMemoryArray(&(clique->vars[pos+1]), &(clique->vars[pos]), amount); /*lint !e866*/
1167  BMSmoveMemoryArray(&(clique->values[pos+1]), &(clique->values[pos]), amount); /*lint !e866*/
1168  clique->nvars++;
1169 
1170  /* insertion for a variable with cliquevalue FALSE */
1171  if( !value )
1172  {
1173  /* find last entry with the same variable and value behind the insertion position */
1174  for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] == value; ++pos ); /*lint !e722*/
1175 
1176  /* check if the same variable with other value also exists */
1177  if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1178  {
1179  assert(clique->values[pos + 1] != value);
1180  *oppositeentry = TRUE;
1181  }
1182 
1183  /* check if we found the same variable with the same value more than once */
1184  if( pos != i )
1185  *doubleentry = TRUE;
1186  else
1187  {
1188  /* find last entry with the same variable and different value before the insertion position */
1189  for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value; --pos ); /*lint !e722*/
1190 
1191  /* check if we found the same variable with the same value more than once */
1192  if( pos > 0 && clique->vars[pos - 1] == var )
1193  {
1194  assert(clique->values[pos - 1] == value);
1195 
1196  *doubleentry = TRUE;
1197  }
1198  /* if we found the same variable with different value, we need to order them correctly */
1199  if( pos != i )
1200  {
1201  assert(clique->vars[pos] == var);
1202  assert(clique->values[pos] != value);
1203 
1204  clique->values[pos] = value;
1205  value = !value;
1206  }
1207  }
1208  }
1209  /* insertion for a variable with cliquevalue TRUE */
1210  else
1211  {
1212  /* find last entry with the same variable and different value behind the insertion position */
1213  for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] != value; ++pos ); /*lint !e722*/
1214 
1215  /* check if the same variable with other value also exists */
1216  if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1217  {
1218  assert(clique->values[pos + 1] == value);
1219  *doubleentry = TRUE;
1220  }
1221 
1222  /* check if we found the same variable with different value */
1223  if( pos != i )
1224  {
1225  *oppositeentry = TRUE;
1226 
1227  /* if we found the same variable with different value, we need to order them correctly */
1228  assert(clique->vars[pos] == var);
1229  assert(clique->values[pos] != value);
1230 
1231  clique->values[pos] = value;
1232  value = !value;
1233  }
1234  else
1235  {
1236  /* find last entry with the same variable and value before the insertion position */
1237  for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] == value; --pos ); /*lint !e722*/
1238 
1239  if( pos != i )
1240  *doubleentry = TRUE;
1241 
1242  /* check if we found the same variable with different value up front */
1243  if( pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value )
1244  *oppositeentry = TRUE;
1245  }
1246  }
1247  }
1248  else
1249  clique->nvars++;
1250 
1251  clique->vars[i] = var;
1252  clique->values[i] = value;
1253  clique->eventsissued = FALSE;
1254 
1255  return SCIP_OKAY;
1256 }
1257 
1258 /** removes a single variable from the given clique */
1260  SCIP_CLIQUE* clique, /**< clique data structure */
1261  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1262  SCIP_VAR* var, /**< variable to remove from the clique */
1263  SCIP_Bool value /**< value of the variable in the clique */
1264  )
1265 {
1266  int pos;
1267 
1268  assert(clique != NULL);
1269  assert(SCIPvarIsBinary(var));
1270  assert(cliquetable != NULL);
1271 
1272  /* if the clique is the leading clique during the cleanup step, we do not need to insert it again */
1273  if( cliquetable->incleanup && clique->index == 0 )
1274  return;
1275 
1276  SCIPdebugMessage("marking variable <%s> == %u from clique %u for deletion\n", SCIPvarGetName(var), value, clique->id);
1277 
1278  /* find variable in clique */
1279  pos = SCIPcliqueSearchVar(clique, var, value);
1280 
1281  assert(0 <= pos && pos < clique->nvars);
1282  assert(clique->vars[pos] == var);
1283  assert(clique->values[pos] == value);
1284 
1285  /* inform the clique table that this clique should be cleaned up */
1286  if( clique->startcleanup == -1 )
1287  cliquetableMarkCliqueForCleanup(cliquetable, clique);
1288 
1289  if( clique->startcleanup == -1 || pos < clique->startcleanup )
1290  clique->startcleanup = pos;
1291 
1292 #ifdef SCIP_MORE_DEBUG
1293  {
1294  int v;
1295  /* all variables prior to the one marked for startcleanup should be unfixed */
1296  for( v = clique->startcleanup - 1; v >= 0; --v )
1297  {
1298  assert(SCIPvarGetUbGlobal(clique->vars[v]) > 0.5);
1299  assert(SCIPvarGetLbGlobal(clique->vars[v]) < 0.5);
1300  }
1301  }
1302 #endif
1303 }
1304 
1305 /** gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array */
1306 static
1308  SCIP_CLIQUE** cliques, /**< array of cliques */
1309  int ncliques, /**< number of cliques in the cliques array */
1310  SCIP_CLIQUE* clique /**< clique to search for */
1311  )
1312 {
1313  unsigned int cliqueid;
1314  int left;
1315  int right;
1316 
1317  assert(cliques != NULL || ncliques == 0);
1318  assert(clique != NULL);
1319 
1320  cliqueid = clique->id; /*lint !e732*/
1321  left = -1;
1322  right = ncliques;
1323  while( left < right-1 )
1324  {
1325  unsigned int id;
1326  int middle;
1327 
1328  assert(cliques != NULL);
1329  middle = (left+right)/2;
1330  id = cliques[middle]->id; /*lint !e732*/
1331  if( cliqueid < id )
1332  right = middle;
1333  else if( cliqueid > id )
1334  left = middle;
1335  else
1336  {
1337  assert(clique == cliques[middle]);
1338  return middle;
1339  }
1340  }
1341 
1342  return -1;
1343 }
1344 
1345 #ifdef SCIP_MORE_DEBUG
1346 /** checks whether clique appears in all clique lists of the involved variables */
1347 static
1348 void cliqueCheck(
1349  SCIP_CLIQUE* clique /**< clique data structure */
1350  )
1351 {
1352  int i;
1353 
1354  assert(clique != NULL);
1355 
1356  for( i = 0; i < clique->nvars; ++i )
1357  {
1358  SCIP_CLIQUE** cliques;
1359  int ncliques;
1360  int pos;
1361  SCIP_VAR* var;
1362 
1363  var = clique->vars[i];
1364  assert(i == 0 || SCIPvarGetIndex(clique->vars[i-1]) <= SCIPvarGetIndex(var));
1365  assert(i == 0 || clique->vars[i-1] != var || clique->values[i-1] <= clique->values[i]);
1366  ncliques = SCIPvarGetNCliques(var, clique->values[i]);
1367 
1368  assert(SCIPvarIsActive(var) || ncliques == 0);
1369 
1370  /* cliquelist of inactive variables are already destroyed */
1371  if( ncliques == 0 )
1372  continue;
1373 
1374  cliques = SCIPvarGetCliques(var, clique->values[i]);
1375  pos = cliquesSearchClique(cliques, ncliques, clique);
1376 
1377  /* assert that the clique is correctly listed in all clique lists of unfixed variables. For fixed variables,
1378  * we require that a clean up has been correctly scheduled, but not yet been processed
1379  */
1380  if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) > 0.5 )
1381  {
1382  assert(0 <= pos && pos < ncliques);
1383  assert(cliques[pos] == clique);
1384  }
1385  else
1386  assert(0 <= clique->startcleanup && clique->startcleanup <= i);
1387  }
1388  assert(clique->index >= 0);
1389 }
1390 #else
1391 #define cliqueCheck(clique) /**/
1392 #endif
1393 
1394 /** creates a clique list data structure */
1395 static
1397  SCIP_CLIQUELIST** cliquelist, /**< pointer to store clique list data structure */
1398  BMS_BLKMEM* blkmem /**< block memory */
1399  )
1400 {
1401  assert(cliquelist != NULL);
1402 
1403  SCIP_ALLOC( BMSallocBlockMemory(blkmem, cliquelist) );
1404  (*cliquelist)->cliques[0] = NULL;
1405  (*cliquelist)->cliques[1] = NULL;
1406  (*cliquelist)->ncliques[0] = 0;
1407  (*cliquelist)->ncliques[1] = 0;
1408  (*cliquelist)->size[0] = 0;
1409  (*cliquelist)->size[1] = 0;
1410 
1411  return SCIP_OKAY;
1412 }
1413 
1414 /** frees a clique list data structure */
1416  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1417  BMS_BLKMEM* blkmem /**< block memory */
1418  )
1419 {
1420  assert(cliquelist != NULL);
1421 
1422  if( *cliquelist != NULL )
1423  {
1424  BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[0], (*cliquelist)->size[0]);
1425  BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[1], (*cliquelist)->size[1]);
1426  BMSfreeBlockMemory(blkmem, cliquelist);
1427  }
1428 }
1429 
1430 /** ensures, that clique list arrays can store at least num entries */
1431 static
1433  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1434  BMS_BLKMEM* blkmem, /**< block memory */
1435  SCIP_SET* set, /**< global SCIP settings */
1436  SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1437  int num /**< minimum number of entries to store */
1438  )
1439 {
1440  assert(cliquelist != NULL);
1441 
1442  if( num > cliquelist->size[value] )
1443  {
1444  int newsize;
1445 
1446  newsize = SCIPsetCalcMemGrowSize(set, num);
1447  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &cliquelist->cliques[value], cliquelist->size[value], newsize) ); /*lint !e866*/
1448  cliquelist->size[value] = newsize;
1449  }
1450  assert(num <= cliquelist->size[value]);
1451 
1452  return SCIP_OKAY;
1453 }
1454 
1455 /** adds a clique to the clique list */
1457  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1458  BMS_BLKMEM* blkmem, /**< block memory */
1459  SCIP_SET* set, /**< global SCIP settings */
1460  SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1461  SCIP_CLIQUE* clique /**< clique that should be added to the clique list */
1462  )
1463 {
1464  unsigned int id;
1465  int i = 0;
1466 
1467  assert(cliquelist != NULL);
1468 
1469  /* insert clique into list, sorted by clique id */
1470  id = clique->id; /*lint !e732*/
1471 
1472  /* allocate memory */
1473  if( *cliquelist == NULL )
1474  {
1475  SCIP_CALL( cliquelistCreate(cliquelist, blkmem) );
1476  }
1477  else
1478  {
1479  if( (*cliquelist)->cliques[value] != NULL )
1480  {
1481  for( i = (*cliquelist)->ncliques[value]; i > 0 && (*cliquelist)->cliques[value][i - 1]->id > id; --i ); /*lint !e574 !e722*/
1482  /* do not put the same clique twice in the cliquelist */
1483  if( i > 0 && (*cliquelist)->cliques[value][i - 1]->id == id )
1484  return SCIP_OKAY;
1485  }
1486  }
1487  SCIP_CALL( cliquelistEnsureSize(*cliquelist, blkmem, set, value, (*cliquelist)->ncliques[value] + 1) );
1488 
1489  SCIPsetDebugMsg(set, "adding clique %u to cliquelist %p value %u (length: %d)\n",
1490  clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1491 
1492  BMSmoveMemoryArray(&((*cliquelist)->cliques[value][i+1]), &((*cliquelist)->cliques[value][i]), (*cliquelist)->ncliques[value] - i); /*lint !e866*/
1493 
1494  (*cliquelist)->cliques[value][i] = clique;
1495  (*cliquelist)->ncliques[value]++;
1496 
1497  return SCIP_OKAY;
1498 }
1499 
1500 /** removes a clique from the clique list */
1502  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1503  BMS_BLKMEM* blkmem, /**< block memory */
1504  SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */
1505  SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */
1506  )
1507 {
1508  int pos;
1509 
1510  assert(cliquelist != NULL);
1511 
1512  /* if a variable appeared twice in its last clique and is now removed both times, the cliquelist is already cleaned
1513  up after the first removal call of this "doubleton" */
1514  if( *cliquelist == NULL )
1515  return SCIP_OKAY;
1516 
1517  SCIPdebugMessage("deleting clique %u from cliquelist %p value %u (length: %d)\n",
1518  clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1519 
1520  pos = cliquesSearchClique((*cliquelist)->cliques[value], (*cliquelist)->ncliques[value], clique);
1521 
1522  /* clique does not exist in cliquelist, the clique should contain multiple entries of the same variable */
1523  if( pos < 0 )
1524  {
1525 #ifdef SCIP_MORE_DEBUG
1526  SCIP_VAR** clqvars;
1527  SCIP_Bool* clqvalues;
1528  int nclqvars = SCIPcliqueGetNVars(clique);
1529  int v;
1530 
1531  assert(nclqvars >= 2);
1532  assert(SCIPcliqueGetVars(clique) != NULL);
1533  assert(SCIPcliqueGetValues(clique) != NULL);
1534 
1535  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvars, SCIPcliqueGetVars(clique), nclqvars) );
1536  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvalues, SCIPcliqueGetValues(clique), nclqvars) );
1537 
1538  /* sort variables and corresponding clique values after variables indices */
1539  SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, nclqvars);
1540 
1541  for( v = nclqvars - 1; v > 0; --v )
1542  {
1543  if( clqvars[v] == clqvars[v - 1] )
1544  {
1545  if( clqvalues[v] == clqvalues[v - 1] || (v > 1 && clqvars[v] == clqvars[v - 2]) )
1546  break;
1547  }
1548  }
1549  assert(v > 0);
1550 
1551  BMSfreeBlockMemoryArray(blkmem, &clqvalues, nclqvars);
1552  BMSfreeBlockMemoryArray(blkmem, &clqvars, nclqvars);
1553 #endif
1554  return SCIP_OKAY;
1555  }
1556 
1557  assert(0 <= pos && pos < (*cliquelist)->ncliques[value]);
1558  assert((*cliquelist)->cliques[value][pos] == clique);
1559 
1560  /* remove clique from list */
1561  /* @todo maybe buffered deletion */
1562  (*cliquelist)->ncliques[value]--;
1563  if( pos < (*cliquelist)->ncliques[value] )
1564  {
1565  BMSmoveMemoryArray(&((*cliquelist)->cliques[value][pos]), &((*cliquelist)->cliques[value][pos+1]),
1566  (*cliquelist)->ncliques[value] - pos); /*lint !e866*/
1567  }
1568 
1569  /* free cliquelist if it is empty */
1570  if( (*cliquelist)->ncliques[0] == 0 && (*cliquelist)->ncliques[1] == 0 )
1571  SCIPcliquelistFree(cliquelist, blkmem);
1572 
1573  return SCIP_OKAY;
1574 }
1575 
1576 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears
1577  * in both lists
1578  */
1580  SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */
1581  SCIP_Bool value1, /**< value of first variable */
1582  SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */
1583  SCIP_Bool value2 /**< value of second variable */
1584  )
1585 {
1586  SCIP_CLIQUE** cliques1;
1587  SCIP_CLIQUE** cliques2;
1588  int ncliques1;
1589  int ncliques2;
1590  int i1;
1591  int i2;
1592 
1593  if( cliquelist1 == NULL || cliquelist2 == NULL )
1594  return FALSE;
1595 
1596  ncliques1 = cliquelist1->ncliques[value1];
1597  cliques1 = cliquelist1->cliques[value1];
1598  ncliques2 = cliquelist2->ncliques[value2];
1599  cliques2 = cliquelist2->cliques[value2];
1600 
1601  i1 = 0;
1602  i2 = 0;
1603 
1604  if( i1 < ncliques1 && i2 < ncliques2 )
1605  {
1606  unsigned int cliqueid;
1607 
1608  /* make the bigger clique the first one */
1609  if( ncliques2 > ncliques1 )
1610  {
1611  SCIP_CLIQUE** tmpc;
1612  int tmpi;
1613 
1614  tmpc = cliques1;
1615  tmpi = ncliques1;
1616  cliques1 = cliques2;
1617  ncliques1 = ncliques2;
1618  cliques2 = tmpc;
1619  ncliques2 = tmpi;
1620  }
1621 
1622  /* check whether both clique lists have a same clique */
1623  while( TRUE ) /*lint !e716*/
1624  {
1625  cliqueid = SCIPcliqueGetId(cliques2[i2]);
1626 
1627  /* if last item in clique1 has a smaller index than the actual clique in clique2, than cause of increasing order
1628  * there will be no same item and we can stop */
1629  if( SCIPcliqueGetId(cliques1[ncliques1 - 1]) < cliqueid )
1630  break;
1631 
1632  while( SCIPcliqueGetId(cliques1[i1]) < cliqueid )
1633  {
1634  ++i1;
1635  assert(i1 < ncliques1);
1636  }
1637  cliqueid = SCIPcliqueGetId(cliques1[i1]);
1638 
1639  /* if last item in clique2 has a smaller index than the actual clique in clique1, than cause of increasing order
1640  * there will be no same item and we can stop */
1641  if( SCIPcliqueGetId(cliques2[ncliques2 - 1]) < cliqueid )
1642  break;
1643 
1644  while( SCIPcliqueGetId(cliques2[i2]) < cliqueid )
1645  {
1646  ++i2;
1647  assert(i2 < ncliques2);
1648  }
1649  if( SCIPcliqueGetId(cliques2[i2]) == cliqueid )
1650  return TRUE;
1651  }
1652  }
1653  return FALSE;
1654 }
1655 
1656 /** removes all listed entries from the cliques */
1658  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1659  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1660  SCIP_VAR* var, /**< active problem variable the clique list belongs to */
1661  SCIP_Bool irrelevantvar /**< has the variable become irrelevant, meaning that equality
1662  * cliques need to be relaxed? */
1663  )
1664 {
1665  assert(SCIPvarIsBinary(var));
1666 
1667  if( cliquelist != NULL )
1668  {
1669  int value;
1670 
1671  SCIPdebugMessage("removing variable <%s> from cliques (%d with value 0, %d with value 1)\n",
1672  SCIPvarGetName(var), cliquelist->ncliques[0], cliquelist->ncliques[1]);
1673 
1674  for( value = 0; value < 2; ++value )
1675  {
1676  int i;
1677 
1678  assert(SCIPvarGetCliques(var, (SCIP_Bool)value) == cliquelist->cliques[value]);
1679  assert(SCIPvarGetNCliques(var, (SCIP_Bool)value) == cliquelist->ncliques[value]);
1680 
1681  /* it is important to iterate from the end of the array because otherwise, each removal causes
1682  * a memory move of the entire array
1683  */
1684  for( i = cliquelist->ncliques[value] - 1; i >= 0; --i )
1685  {
1686  SCIP_CLIQUE* clique;
1687 
1688  clique = cliquelist->cliques[value][i];
1689  assert(clique != NULL);
1690 
1691  SCIPdebugMessage(" -> removing variable <%s> == %d from clique %u (size %d)\n",
1692  SCIPvarGetName(var), value, clique->id, clique->nvars);
1693 
1694  SCIPcliqueDelVar(clique, cliquetable, var, (SCIP_Bool)value);
1695 
1696  if( irrelevantvar )
1697  clique->equation = FALSE;
1698 
1699 #ifdef SCIP_MORE_DEBUG
1700  /* during the cleanup step, we skip the consistency check because clique may be temporarily inconsistent */
1701  if( ! cliquetable->incleanup || clique->index > 0 )
1702  {
1703  cliqueCheck(clique);
1704  }
1705 #endif
1706  }
1707  }
1708  }
1709 }
1710 
1711 /** gets the key of the given element */
1712 static
1713 SCIP_DECL_HASHGETKEY(hashgetkeyClique)
1714 { /*lint --e{715}*/
1715  return elem;
1716 }
1717 
1718 /** returns TRUE iff both keys are equal */
1719 static
1720 SCIP_DECL_HASHKEYEQ(hashkeyeqClique)
1721 { /*lint --e{715}*/
1722  SCIP_CLIQUE* clique1;
1723  SCIP_CLIQUE* clique2;
1724  int i;
1725 
1726  clique1 = (SCIP_CLIQUE*)key1;
1727  clique2 = (SCIP_CLIQUE*)key2;
1728  assert(clique1 != NULL);
1729  assert(clique2 != NULL);
1730 
1731  if( clique1->nvars != clique2->nvars )
1732  return FALSE;
1733 
1734  /* the variables are sorted: we can simply check the equality of each pair of variable/values */
1735  for( i = 0; i < clique1->nvars; ++i )
1736  {
1737  if( clique1->vars[i] != clique2->vars[i] || clique1->values[i] != clique2->values[i] )
1738  return FALSE;
1739  }
1740 
1741  return TRUE;
1742 }
1743 
1744 /** returns the hash value of the key */
1745 static
1746 SCIP_DECL_HASHKEYVAL(hashkeyvalClique)
1747 { /*lint --e{715}*/
1748  SCIP_CLIQUE* clique;
1749 
1750  clique = (SCIP_CLIQUE*)key;
1751 
1752  return clique->nvars == 0 ? 0 : SCIPhashFour(SCIPvarGetIndex(clique->vars[0]), \
1753  SCIPvarGetIndex(clique->vars[clique->nvars-1]), \
1754  clique->nvars, 2*clique->values[0] + clique->values[clique->nvars-1]);
1755 }
1756 
1757 #define HASHTABLE_CLIQUETABLE_SIZE 100
1758 
1759 /** creates a clique table data structure */
1761  SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1762  SCIP_SET* set, /**< global SCIP settings */
1763  BMS_BLKMEM* blkmem /**< block memory */
1764  )
1765 {
1766  int hashtablesize;
1767 
1768  assert(cliquetable != NULL);
1769 
1770  SCIP_ALLOC( BMSallocMemory(cliquetable) );
1771 
1772  /* create hash table to test for multiple cliques */
1773  hashtablesize = HASHTABLE_CLIQUETABLE_SIZE;
1774  hashtablesize = MAX(hashtablesize, (set->misc_usesmalltables ? SCIP_HASHSIZE_CLIQUES_SMALL : SCIP_HASHSIZE_CLIQUES));
1775  SCIP_CALL( SCIPhashtableCreate(&((*cliquetable)->hashtable), blkmem, hashtablesize,
1776  hashgetkeyClique, hashkeyeqClique, hashkeyvalClique, NULL) );
1777 
1778  (*cliquetable)->varidxtable = NULL;
1779  (*cliquetable)->djset = NULL;
1780  (*cliquetable)->cliques = NULL;
1781  (*cliquetable)->ncliques = 0;
1782  (*cliquetable)->size = 0;
1783  (*cliquetable)->ncreatedcliques = 0;
1784  (*cliquetable)->ncleanupfixedvars = 0;
1785  (*cliquetable)->ncleanupaggrvars = 0;
1786  (*cliquetable)->ndirtycliques = 0;
1787  (*cliquetable)->nentries = 0;
1788  (*cliquetable)->incleanup = FALSE;
1789  (*cliquetable)->compsfromscratch = FALSE;
1790  (*cliquetable)->ncliquecomponents = -1;
1791 
1792  return SCIP_OKAY;
1793 }
1794 
1795 /** frees a clique table data structure */
1797  SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1798  BMS_BLKMEM* blkmem /**< block memory */
1799  )
1800 {
1801  int i;
1802 
1803  assert(cliquetable != NULL);
1804  assert(*cliquetable != NULL);
1805 
1806  /* free all cliques */
1807  for( i = (*cliquetable)->ncliques - 1; i >= 0; --i )
1808  {
1809  cliqueFree(&(*cliquetable)->cliques[i], blkmem);
1810  }
1811 
1812  /* free disjoint set (union find) data structure */
1813  if( (*cliquetable)->djset != NULL )
1814  SCIPdisjointsetFree(&(*cliquetable)->djset, blkmem);
1815 
1816  /* free hash table for variable indices */
1817  if( (*cliquetable)->varidxtable != NULL )
1818  SCIPhashmapFree(&(*cliquetable)->varidxtable);
1819 
1820  /* free clique table data */
1821  BMSfreeMemoryArrayNull(&(*cliquetable)->cliques);
1822 
1823  /* free hash table */
1824  SCIPhashtableFree(&((*cliquetable)->hashtable));
1825 
1826  BMSfreeMemory(cliquetable);
1827 
1828  return SCIP_OKAY;
1829 }
1830 
1831 /** ensures, that clique table arrays can store at least num entries */
1832 static
1834  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1835  SCIP_SET* set, /**< global SCIP settings */
1836  int num /**< minimum number of entries to store */
1837  )
1838 {
1839  assert(cliquetable != NULL);
1840 
1841  if( num > cliquetable->size )
1842  {
1843  int newsize;
1844 
1845  newsize = SCIPsetCalcMemGrowSize(set, num);
1846  SCIP_ALLOC( BMSreallocMemoryArray(&cliquetable->cliques, newsize) );
1847  cliquetable->size = newsize;
1848  }
1849  assert(num <= cliquetable->size);
1850 
1851  return SCIP_OKAY;
1852 }
1853 
1854 /** sort variables regarding their index and remove multiple entries of the same variable */
1855 static
1857  SCIP_VAR** clqvars, /**< variables of a clique */
1858  SCIP_Bool* clqvalues, /**< clique values, active or negated, for the variables in a clique */
1859  int* nclqvars, /**< number of clique variables */
1860  SCIP_Bool* isequation, /**< do we have an equation clique at hand? */
1861  SCIP_CLIQUE* clique, /**< clique data structure or NULL */
1862  BMS_BLKMEM* blkmem, /**< block memory */
1863  SCIP_SET* set, /**< global SCIP settings */
1864  SCIP_STAT* stat, /**< problem statistics */
1865  SCIP_PROB* transprob, /**< transformed problem */
1866  SCIP_PROB* origprob, /**< original problem */
1867  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
1868  SCIP_REOPT* reopt, /**< reoptimization data structure */
1869  SCIP_LP* lp, /**< current LP data */
1870  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1871  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1872  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1873  int* nbdchgs, /**< pointer to store number of fixed variables */
1874  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1875  )
1876 {
1877  int noldbdchgs;
1878  int startidx;
1879 
1880  assert(nclqvars != NULL);
1881 
1882  SCIPsetDebugMsg(set, "starting merging %d variables in clique %d\n", *nclqvars, (clique == NULL) ? -1 : (int) clique->id);
1883 
1884  if( *nclqvars <= 1 )
1885  return SCIP_OKAY;
1886 
1887  assert(clqvars != NULL);
1888  assert(clqvalues != NULL);
1889  assert(blkmem != NULL);
1890  assert(set != NULL);
1891  assert(stat != NULL);
1892  assert(transprob != NULL);
1893  assert(origprob != NULL);
1894  assert(tree != NULL);
1895  assert(eventqueue != NULL);
1896  assert(nbdchgs != NULL);
1897  assert(infeasible != NULL);
1898 
1899  /* sort variables and corresponding clique values regarding variables indices before merging multiples */
1900  SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, *nclqvars);
1901 
1902  noldbdchgs = *nbdchgs;
1903  /* check for multiple occurences or pairs of negations in the variable array, this should be very rare when creating a
1904  * new clique */
1905  startidx = *nclqvars - 1;
1906  while( startidx >= 0 )
1907  {
1908  SCIP_VAR* var;
1909  int nones;
1910  int nzeros;
1911  int curr;
1912 
1913  var = clqvars[startidx];
1914  /* only column and loose variables can exist now */
1916  assert(SCIPvarIsBinary(var));
1917 
1918  /* the counters denote the occurrences of the variable var with value TRUE and FALSE as clqvalues, respectively */
1919  if( clqvalues[startidx] )
1920  {
1921  nones = 1;
1922  nzeros = 0;
1923  }
1924  else
1925  {
1926  nzeros = 1;
1927  nones = 0;
1928  }
1929  curr = startidx - 1;
1930 
1931  /* loop and increase the counter based on the clique value */
1932  while( curr >= 0 )
1933  {
1934  if( clqvars[curr] == var )
1935  {
1936  if( clqvalues[curr] )
1937  nones++;
1938  else
1939  nzeros++;
1940  }
1941  else
1942  /* var is different from variable at index curr */
1943  break;
1944 
1945  --curr;
1946  }
1947  assert(nzeros + nones <= *nclqvars);
1948 
1949  /* single occurrence of the variable */
1950  if( nones + nzeros == 1 )
1951  {
1952  startidx = curr;
1953  continue;
1954  }
1955  /* at least two occurrences of both the variable and its negation; infeasible */
1956  if( nones >= 2 && nzeros >= 2 )
1957  {
1958  *infeasible = TRUE;
1959  break;
1960  }
1961 
1962  /* do we have the same variable with the same clique value twice? */
1963  if( nones >= 2 || nzeros >= 2 )
1964  {
1965  SCIP_Bool fixvalue;
1966 
1967  /* other cases should be handled as infeasible */
1968  assert(nones <= 1 || nzeros <= 1);
1969 
1970  /* ensure that the variable is removed from both clique lists before fixing it */
1971  if( clique != NULL )
1972  {
1973  if( nones >= 1 )
1974  {
1975  SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) );
1976  }
1977  if( nzeros >= 1 )
1978  {
1979  SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) );
1980  }
1981  }
1982 
1983  /* we fix the variable into the direction of fewer occurrences */
1984  fixvalue = nones >= 2 ? FALSE : TRUE;
1985 
1986  /* a variable multiple times in one clique forces this variable to be zero */
1987  SCIP_CALL( SCIPvarFixBinary(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
1988  cliquetable, fixvalue, infeasible, nbdchgs) );
1989 
1990  SCIPsetDebugMsg(set, "same var %s twice in a clique with value %d fixed to %d (was %s)\n", SCIPvarGetName(var), fixvalue ? 0 : 1,
1991  fixvalue ? 1 : 0, *infeasible ? "infeasible" : "feasible");
1992 
1993  if( *infeasible )
1994  break;
1995  }
1996 
1997  /* do we have a pair of negated variables? */
1998  if( nones >= 1 && nzeros >= 1 )
1999  {
2000  SCIPsetDebugMsg(set, "var %s is paired with its negation in one clique -> fix all other variables\n", SCIPvarGetName(var));
2001 
2002  /* a pair of negated variables in one clique forces all other variables in the clique to be zero */
2003  if( nzeros + nones < *nclqvars )
2004  {
2005  int w;
2006 
2007  w = *nclqvars - 1;
2008  while( w >= 0 )
2009  {
2010  /* skip all occurrences of variable var itself, these are between curr and startidx */
2011  if( w == startidx )
2012  {
2013  if( curr == -1 )
2014  break;
2015 
2016  w = curr;
2017  }
2018  assert(clqvars[w] != var);
2019 
2020  /* if one of the other variables occurs multiple times, we can
2021  * 1) deduce infeasibility if it occurs with different values
2022  * 2) wait for the last occurence to fix it
2023  */
2024  while( w > 0 && clqvars[w-1] == clqvars[w] )
2025  {
2026  if( clqvalues[w-1] != clqvalues[w] )
2027  {
2028  *infeasible = TRUE;
2029  break;
2030  }
2031  --w;
2032  }
2033 
2034  if( *infeasible )
2035  break;
2036 
2037  if( clique != NULL )
2038  {
2039  SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[w], blkmem, clqvalues[w], clique) );
2040  }
2041  SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2042  branchcand, eventqueue, cliquetable, !clqvalues[w], infeasible, nbdchgs) );
2043 
2044  SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[w]), clqvalues[w],
2045  clqvalues[w] ? 0 : 1, *infeasible ? "infeasible" : "feasible");
2046 
2047  if( *infeasible )
2048  break;
2049 
2050  --w;
2051  }
2052  }
2053  /* all variables except for var were fixed */
2054  if( clique != NULL )
2055  {
2056  SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) );
2057  SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) );
2058  }
2059  *nclqvars = 0;
2060  *isequation = FALSE;
2061 
2062  /* break main loop */
2063  break;
2064  }
2065 
2066  /* otherwise, we would have an endless loop */
2067  assert(curr < startidx);
2068  startidx = curr;
2069  }
2070 
2071  /* we might have found an infeasibility or reduced the clique to size 0 */
2072  if( *infeasible || *nclqvars == 0 )
2073  return SCIP_OKAY;
2074 
2075  /* we fixed a variable because it appears at least twice, now we need to remove the fixings
2076  *
2077  * @note that if we are in probing or solving stage, the fixation on the variable might not be carried out yet,
2078  * because it was contradicting a local bound
2079  */
2080  if( *nbdchgs > noldbdchgs )
2081  {
2082  SCIP_VAR* onefixedvar;
2083  SCIP_Bool onefixedvalue;
2084  int w;
2085 
2086  /* we initialize the former value only to please gcc */
2087  onefixedvalue = TRUE;
2088  onefixedvar = NULL;
2089 
2090  /* remove all inactive variables, thereby checking for a variable that is fixed to one */
2091  startidx = 0;
2092  w = 0;
2093  while( startidx < *nclqvars )
2094  {
2095  SCIP_VAR* var;
2096 
2097  var = clqvars[startidx];
2098 
2101 
2102  /* check if we have a variable fixed to one for this clique */
2103  if( (clqvalues[startidx] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[startidx] && SCIPvarGetUbGlobal(var) < 0.5) )
2104  {
2105  if( onefixedvar != NULL )
2106  {
2107  *infeasible = TRUE;
2108 
2109  SCIPsetDebugMsg(set, "two variables in clique %d fixed to one %s%s and %s%s\n", (clique != NULL) ? (int) clique->id : -1,
2110  onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clqvalues[startidx] ? "" : "~", SCIPvarGetName(clqvars[startidx]));
2111  return SCIP_OKAY;
2112  }
2113  onefixedvar = var;
2114  onefixedvalue = clqvalues[startidx];
2115  }
2116  /* only keep active variables */
2117  else if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
2118  {
2119  /* we remove all fixed variables */
2120  if( startidx > w )
2121  {
2122  clqvars[w] = clqvars[startidx];
2123  clqvalues[w] = clqvalues[startidx];
2124  }
2125  ++w;
2126  }
2127  else
2128  {
2129  /* can we have some variable fixed to one? */
2130  assert((SCIPvarGetUbGlobal(var) < 0.5 && clqvalues[startidx]) || (SCIPvarGetLbGlobal(var) > 0.5 && !clqvalues[startidx]));
2131 
2132  if( clique != NULL )
2133  {
2134  SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, clqvalues[startidx], clique) );
2135  }
2136  }
2137  ++startidx;
2138  }
2139 
2140  /* the clique has been reduced to w active (unfixed) variables */
2141  *nclqvars = w;
2142 
2143  /* in rare cases, a variable fixed to one is only detected in the merging step */
2144  if( onefixedvar != NULL )
2145  {
2146  SCIPsetDebugMsg(set, "variable %s%s in clique %d fixed to one, fixing all other variables to zero\n",
2147  onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), (clique != NULL) ? (int) clique->id : -1);
2148 
2149  /* handle all active variables by fixing them */
2150  for( startidx = *nclqvars; startidx >= 0; --startidx )
2151  {
2152  assert(SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_COLUMN
2153  || SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_LOOSE);
2154 
2155  /* delete the variable from its clique lists and fix it */
2156  if( onefixedvalue != clqvalues[startidx] || clqvars[startidx] != onefixedvar )
2157  {
2158  if( clique != NULL )
2159  {
2160  SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[startidx], blkmem, clqvalues[startidx], clique) );
2161  }
2162 
2163  /* if one of the other variables occurs multiple times, we can
2164  * 1) deduce infeasibility if it occurs with different values
2165  * 2) wait for the last occurence to fix it
2166  */
2167  while( startidx > 0 && clqvars[startidx - 1] == clqvars[startidx] )
2168  {
2169  if( clqvalues[startidx - 1] != clqvalues[startidx] )
2170  {
2171  *infeasible = TRUE;
2172  return SCIP_OKAY;
2173  }
2174  --startidx; /*lint !e850*/
2175  }
2176 
2177  SCIPsetDebugMsg(set, "fixing variable %s in clique %d to %d\n", SCIPvarGetName(clqvars[startidx]), (clique != NULL) ? (int) clique->id : -1,
2178  clqvalues[startidx] ? 0 : 1);
2179 
2180  /* note that the variable status will remain unchanged */
2181  SCIP_CALL( SCIPvarFixBinary(clqvars[startidx], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2182  branchcand, eventqueue, cliquetable, !clqvalues[startidx], infeasible, nbdchgs) );
2183 
2184  if( *infeasible )
2185  return SCIP_OKAY;
2186  }
2187  }
2188 
2189  /* delete clique from onefixedvars clique list */
2190  if( clique != NULL ) /*lint !e850*/
2191  {
2192  SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2193  }
2194 
2195  *nclqvars = 0;
2196  *isequation = FALSE;
2197  }
2198  }
2199 
2200  assert(!(*infeasible));
2201 
2202  if( *isequation )
2203  {
2204  if( *nclqvars == 0 )
2205  {
2206  SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n");
2207 
2208  *infeasible = TRUE;
2209  }
2210  else if( *nclqvars == 1 )
2211  {
2212  assert(SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_COLUMN
2213  || SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_LOOSE);
2214  /* clearing data and removing variable from its clique list */
2215  if( clique != NULL )
2216  {
2217  SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[0], blkmem, clqvalues[0], clique) );
2218  }
2219  SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2220  eventqueue, cliquetable, clqvalues[0], infeasible, nbdchgs) );
2221 
2222  SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2223  clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2224 
2225  *nclqvars = 0;
2226  *isequation = FALSE;
2227  }
2228  }
2229 
2230  return SCIP_OKAY;
2231 }
2232 
2233 /** helper function that returns the graph node index for a variable during connected component detection */
2234 static
2236  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2237  SCIP_VAR* binvar /**< binary (or binary integer or implicit binary) variable */
2238  )
2239 {
2240  SCIP_VAR* activevar;
2241  int nodeindex;
2242 
2243  assert(binvar != NULL);
2244  assert(SCIPvarIsBinary(binvar));
2245 
2246  if( cliquetable->varidxtable == NULL )
2247  return -1;
2248 
2249  /* get active representative of variable */
2250  if( !SCIPvarIsActive(binvar) )
2251  {
2252  activevar = SCIPvarGetProbvar(binvar);
2253  if( !SCIPvarIsActive(activevar) )
2254  return -1;
2255  }
2256  else
2257  activevar = binvar;
2258 
2259  assert(SCIPvarIsBinary(activevar));
2260 
2261  /* if the map does not contain an index for this variable, return -1 and mark that the components must be
2262  * recomputed from scratch
2263  */
2264  if( SCIPhashmapExists(cliquetable->varidxtable, (void*)activevar) )
2265  nodeindex = SCIPhashmapGetImageInt(cliquetable->varidxtable, (void *)activevar);
2266  else
2267  {
2268  nodeindex = -1;
2269  cliquetable->compsfromscratch = TRUE;
2270  }
2271 
2272  return nodeindex;
2273 }
2274 
2275 
2276 /** updates connectedness information for the \p clique */
2277 static
2279  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2280  SCIP_CLIQUE* clique /**< clique that should be added */
2281  )
2282 {
2283  int i;
2284  int lastnode;
2285  SCIP_VAR** clqvars;
2286  int nclqvars;
2287 
2288  assert(cliquetable != NULL);
2289  assert(clique != NULL);
2290 
2291  /* check if disjoint set (union find) data structure has not been allocated yet */
2292  if( cliquetable->djset == NULL )
2293  cliquetable->compsfromscratch = TRUE;
2294 
2295  /* return immediately if a component update is already pending */
2296  if( cliquetable->compsfromscratch )
2297  return;
2298 
2299  lastnode = -1;
2300  clqvars = clique->vars;
2301  nclqvars = clique->nvars;
2302 
2303  /* loop over variables in the clique and connect the corresponding components */
2304  for( i = 0; i < nclqvars && !cliquetable->compsfromscratch; ++i )
2305  {
2306  /* this method may also detect that the clique table must entirely recompute connectedness */
2307  int currnode = cliquetableGetNodeIndexBinvar(cliquetable, clqvars[i]);
2308 
2309  /* skip inactive variables */
2310  if( currnode == - 1 )
2311  continue;
2312 
2313  /* connect this and the last active variable */
2314  if( lastnode != -1 )
2315  SCIPdisjointsetUnion(cliquetable->djset, lastnode, currnode, FALSE);
2316 
2317  lastnode = currnode;
2318  }
2319 }
2320 
2321 /** returns the index of the connected component of the clique graph that the variable belongs to, or -1 */
2323  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2324  SCIP_VAR* var /**< problem variable */
2325  )
2326 {
2327  int cmpidx = -1;
2328  assert(var != NULL);
2329  assert(cliquetable->djset != NULL);
2330 
2331  /* only binary variables can have a component index
2332  *(both integer and implicit integer variables can be binary)
2333  */
2334  if( SCIPvarIsBinary(var) )
2335  {
2336  int nodeindex = cliquetableGetNodeIndexBinvar(cliquetable, var);
2337  assert(nodeindex < SCIPdisjointsetGetSize(cliquetable->djset));
2338 
2339  if( nodeindex >= 0 )
2340  cmpidx = SCIPdisjointsetFind(cliquetable->djset, nodeindex);
2341  }
2342 
2343  return cmpidx;
2344 }
2345 
2346 
2347 /** adds a clique to the clique table, using the given values for the given variables;
2348  * performs implications if the clique contains the same variable twice
2349  */
2351  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2352  BMS_BLKMEM* blkmem, /**< block memory */
2353  SCIP_SET* set, /**< global SCIP settings */
2354  SCIP_STAT* stat, /**< problem statistics */
2355  SCIP_PROB* transprob, /**< transformed problem */
2356  SCIP_PROB* origprob, /**< original problem */
2357  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2358  SCIP_REOPT* reopt, /**< reoptimization data structure */
2359  SCIP_LP* lp, /**< current LP data */
2360  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2361  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2362  SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
2363  SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
2364  int nvars, /**< number of variables in the clique */
2365  SCIP_Bool isequation, /**< is the clique an equation or an inequality? */
2366  SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
2367  int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */
2368  )
2369 {
2370  SCIP_VAR** clqvars;
2371  SCIP_Bool* clqvalues;
2372  SCIP_CLIQUE* clique;
2373  SCIP_VAR* var;
2374  int size;
2375  int nlocalbdchgs = 0;
2376  int v;
2377  int w;
2378 
2379  assert(cliquetable != NULL);
2380  assert(vars != NULL);
2381 
2382  SCIPsetDebugMsg(set, "trying to add clique %d with %d vars to clique table\n", cliquetable->ncliques, nvars);
2383 
2384  /* check clique on debugging solution */
2385  SCIP_CALL( SCIPdebugCheckClique(set, vars, values, nvars) ); /*lint !e506 !e774*/
2386 
2387  *infeasible = FALSE;
2388  size = nvars;
2389 
2390  /* copy clique data */
2391  if( values == NULL )
2392  {
2393  SCIP_CALL( SCIPsetAllocBufferArray(set, &clqvalues, size) );
2394 
2395  /* initialize clique values data */
2396  for( v = nvars - 1; v >= 0; --v )
2397  clqvalues[v] = TRUE;
2398  }
2399  else
2400  {
2401  SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvalues, values, size) );
2402  }
2403  SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvars, vars, size) );
2404 
2405  /* get active variables */
2406  SCIP_CALL( SCIPvarsGetProbvarBinary(&clqvars, &clqvalues, nvars) );
2407 
2408  /* remove all inactive vars */
2409  for( v = nvars - 1; v >= 0; --v )
2410  {
2411  var = clqvars[v];
2412 
2417  assert(SCIPvarIsBinary(var));
2418 
2419  /* if we have a variables already fixed to one in the clique, fix all other to zero */
2421  ((clqvalues[v] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[v] && SCIPvarGetUbGlobal(var) < 0.5)) )
2422  {
2423  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);
2424 
2425  for( w = nvars - 1; w >= 0; --w )
2426  {
2427  SCIP_VAR* clqvar = clqvars[w];
2428 
2429  /* the rare case where the same variable appears several times is handled later during sort and merge */
2430  if( clqvar != var )
2431  {
2432  SCIP_Bool clqval = clqvalues[w];
2433 
2434  /* check if variable is fixed already and terminate with infeasible if this fixing contradicts the clique info */
2435  if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2436  {
2437  /* check if fixing contradicts clique constraint */
2438  if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2439  || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2440  {
2441  *infeasible = TRUE;
2442 
2443  goto FREEMEM;
2444  }
2445 
2446  continue;
2447  }
2448 
2449 /* the following piece of code is disabled because it assumes the clqvars to be sorted which they aren't until the method
2450  * sortAndMergeClique() is called
2451  */
2452 #ifdef SCIP_DISABLED_CODE
2453  /* if one of the other variables occurs multiple times, we can
2454  * 1) deduce infeasibility if it occurs with different values
2455  * 2) wait for the last occurence to fix it
2456  */
2457  while( w > 0 && clqvars[w - 1] == clqvars[w] )
2458  {
2459  if( clqvalues[w - 1] != clqvalues[w] )
2460  {
2461  *infeasible = TRUE;
2462  return SCIP_OKAY;
2463  }
2464  --w;
2465  }
2466 #endif
2467 
2468  /* fix the variable */
2469  SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2470  branchcand, eventqueue, cliquetable, !clqval, infeasible, &nlocalbdchgs) );
2471 
2472  SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvar), clqval,
2473  clqval ? 0 : 1, *infeasible ? "infeasible" : "feasible");
2474 
2475  if( *infeasible )
2476  break;
2477  }
2478  }
2479 
2480  /* all variables are fixed so we can stop */
2481  break; /*lint !e850*/
2482  }
2483 
2484  /* only unfixed column and loose variables may be member of a clique */
2485  if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) < 0.5 ||
2488  {
2489  --nvars;
2490  clqvars[v] = clqvars[nvars];
2491  clqvalues[v] = clqvalues[nvars];
2492  isequation = isequation && !(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR) && ! SCIPvarIsMarkedDeleteGlobalStructures(var);
2493  }
2494  }
2495 
2496  if( nbdchgs != NULL )
2497  *nbdchgs += nlocalbdchgs;
2498 
2499  /* did we fix all variables or are we infeasible? */
2500  if( v >= 0 )
2501  goto FREEMEM;
2502 
2503  assert(!*infeasible);
2504 
2505  /* check if only one or less variables are left */
2506  if( v < 0 && nvars <= 1)
2507  {
2508  if( isequation )
2509  {
2510  if( nvars == 1 )
2511  {
2512  nlocalbdchgs = 0;
2513 
2514  SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2515  branchcand, eventqueue, cliquetable, clqvalues[0], infeasible, &nlocalbdchgs) );
2516 
2517  SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2518  clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2519 
2520  if( nbdchgs != NULL )
2521  *nbdchgs += nlocalbdchgs;
2522  }
2523  else if( nvars == 0 )
2524  {
2525  SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n");
2526 
2527  *infeasible = TRUE;
2528  }
2529  }
2530 
2531  goto FREEMEM;
2532  }
2533 
2534  nlocalbdchgs = 0;
2535 
2536  /* sort the variables and values and remove multiple entries of the same variable */
2537  SCIP_CALL( sortAndMergeClique(clqvars, clqvalues, &nvars, &isequation, NULL, blkmem, set, stat, transprob, origprob, tree,
2538  reopt, lp, branchcand, eventqueue, cliquetable, &nlocalbdchgs, infeasible) );
2539 
2540  if( nbdchgs != NULL )
2541  *nbdchgs += nlocalbdchgs;
2542 
2543  /* did we stop early due to a pair of negated variables? */
2544  if( nvars == 0 || *infeasible )
2545  goto FREEMEM;
2546 
2547  if( !SCIPsetIsInfinity(set, set->presol_clqtablefac) && SCIPcliquetableGetNEntries(cliquetable) + nvars > set->presol_clqtablefac * stat->nnz )
2548  {
2549  SCIPsetDebugMsg(set, "reject %d-variable clique to keep clique table entries below threshold of %g entries\n",
2550  nvars, set->presol_clqtablefac * stat->nnz);
2551 
2552  goto FREEMEM;
2553  }
2554 
2555  /* if less than two variables are left over, the clique is redundant */
2556  if( nvars > 1 )
2557  {
2558  SCIP_CLIQUE* sameclique;
2559 
2560  /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2561 
2562  /* create the clique data structure */
2563  SCIP_CALL( cliqueCreateWithData(&clique, blkmem, nvars, clqvars, clqvalues, nvars, cliquetable->ncreatedcliques, isequation) );
2564 
2565  sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
2566 
2567  if( sameclique == NULL )
2568  {
2569  SCIPsetDebugMsg(set, "adding clique %u with %d vars to clique table\n", clique->id, nvars);
2570 
2571  cliquetable->ncreatedcliques++;
2572 
2573  /* add clique to clique table */
2574  SCIP_CALL( cliquetableEnsureSize(cliquetable, set, cliquetable->ncliques+1) );
2575  cliquetable->cliques[cliquetable->ncliques] = clique;
2576  clique->index = cliquetable->ncliques;
2577  cliquetable->ncliques++;
2578  cliquetable->nentries += nvars;
2579  cliquetableUpdateConnectednessClique(cliquetable, clique);
2580 
2581  SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
2582 
2583  /* add filled clique to the cliquelists of all corresponding variables */
2584  SCIP_CALL( SCIPvarsAddClique(clqvars, clqvalues, nvars, blkmem, set, clique) );
2585  }
2586  else
2587  {
2588  SCIPsetDebugMsg(set, "same clique %p (id: %d) already found in cliquetable -> discard new one\n", (void*) sameclique, sameclique->id);
2589 
2590  /* update equation status of clique */
2591  /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
2592  * the sameclique from the hashmap while adding the new clique
2593  */
2594  if( !sameclique->equation && clique->equation )
2595  sameclique->equation = TRUE;
2596 
2597  cliqueFree(&clique, blkmem);
2598 
2599  goto FREEMEM;
2600  }
2601  }
2602  else
2603  {
2604  assert(!isequation);
2605  assert(nvars == 1);
2606 
2607  goto FREEMEM;
2608  }
2609  cliqueCheck(clique);
2610 
2611  FREEMEM:
2612  SCIPsetFreeBufferArray(set, &clqvars);
2613  SCIPsetFreeBufferArray(set, &clqvalues);
2614 
2615  return SCIP_OKAY;
2616 }
2617 
2618 /** clean up given clique by removing fixed variables */
2619 static
2621  SCIP_CLIQUE* clique, /**< clique data structure */
2622  BMS_BLKMEM* blkmem, /**< block memory */
2623  SCIP_SET* set, /**< global SCIP settings */
2624  SCIP_STAT* stat, /**< problem statistics */
2625  SCIP_PROB* transprob, /**< transformed problem */
2626  SCIP_PROB* origprob, /**< original problem */
2627  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2628  SCIP_REOPT* reopt, /**< reoptimization data structure */
2629  SCIP_LP* lp, /**< current LP data */
2630  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2631  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2632  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2633  int* nchgbds, /**< pointer to store number of fixed variables */
2634  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2635  )
2636 {
2637  assert(clique != NULL);
2638  assert(blkmem != NULL);
2639  assert(set != NULL);
2640  assert(nchgbds != NULL);
2641  assert(infeasible != NULL);
2642 
2643  /* do we need to clean up fixed variables? */
2644  if( !SCIPcliqueIsCleanedUp(clique) )
2645  {
2646  SCIP_VAR* onefixedvar = NULL;
2647  SCIP_Bool onefixedvalue;
2648  SCIP_Bool needsorting = FALSE;
2649  int v;
2650  int w;
2651 
2652  w = clique->startcleanup;
2653 
2654  SCIPsetDebugMsg(set, "Starting clean up of clique %u (size %d) from position %d\n", clique->id, clique->nvars, w);
2655 
2656  /* exchange inactive by active variables */
2657  for( v = w; v < clique->nvars; ++v )
2658  {
2659  SCIP_Bool addvartoclique; /* has the variable status changed such that it needs to be replaced by an active representative? */
2660 
2661  addvartoclique = FALSE;
2663  || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED
2664  || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2665  {
2666  needsorting = TRUE;
2667 
2668  SCIP_CALL( SCIPvarGetProbvarBinary(&(clique->vars[v]), &(clique->values[v])) );
2669  if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED )
2670  {
2671  clique->vars[v] = SCIPvarGetNegationVar(clique->vars[v]);
2672  clique->values[v] = !clique->values[v];
2673  }
2674  else if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2675  {
2676  clique->equation = FALSE;
2677  continue;
2678  }
2679 
2680  addvartoclique = TRUE;
2681  }
2682 
2683  assert(SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_COLUMN
2684  || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_LOOSE
2685  || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_FIXED);
2686 
2687  /* check for variables that are either fixed to zero or marked for deletion from global structures */
2688  if( (clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) ||
2689  (!clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5) ||
2691  {
2692  if( clique->equation && SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2693  clique->equation = FALSE;
2694 
2695  /* the variable will be overwritten by subsequent active variables */
2696  continue;
2697  }
2698 
2699  /* check for a variable fixed to one in the clique */
2700  else if( (clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5)
2701  || (!clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) )
2702  {
2703  if( onefixedvar != NULL )
2704  {
2705  *infeasible = TRUE;
2706 
2707  SCIPsetDebugMsg(set, "two variables in clique %u fixed to one %s%s and %s%s\n", clique->id,
2708  onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->values[v] ? "" : "~",
2709  SCIPvarGetName(clique->vars[v])); /*lint !e530*/
2710  return SCIP_OKAY;
2711  }
2712  onefixedvar = clique->vars[v];
2713  onefixedvalue = clique->values[v];
2714  }
2715  else
2716  {
2717  assert(SCIPvarGetStatus(clique->vars[v]) != SCIP_VARSTATUS_FIXED);
2718  assert(w <= v);
2719 
2720  if( w < v )
2721  {
2722  clique->vars[w] = clique->vars[v];
2723  clique->values[w] = clique->values[v];
2724  }
2725 
2726  /* add clique to active variable if it replaced a aggregated or negated var */
2727  if( addvartoclique )
2728  {
2729  SCIP_CALL( SCIPvarAddCliqueToList(clique->vars[w], blkmem, set, clique->values[w], clique) );
2730  }
2731  /* increase indexer of last active, i.e. unfixed, variable in clique */
2732  ++w;
2733  }
2734  }
2735  clique->nvars = w;
2736 
2737  if( onefixedvar != NULL )
2738  {
2739  SCIPsetDebugMsg(set, "variable %s%s in clique %u fixed to one, fixing all other variables to zero\n",
2740  onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->id);
2741 
2742  for( v = 0; v < clique->nvars ; ++v )
2743  {
2744  SCIP_VAR* clqvar = clique->vars[v];
2745  SCIP_Bool clqval = clique->values[v];
2746 
2747  assert(SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_COLUMN
2748  || SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_LOOSE);
2749 
2750  if( onefixedvalue != clqval || clqvar != onefixedvar )
2751  {
2752  /* the variable could have been fixed already because it appears more than once in the clique */
2753  if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2754  {
2755  /* the fixing must have occurred previously inside this loop. It may happen that
2756  * the variable occurs together with its negation in that clique, which is usually
2757  * handled during the merge step, but leads to a direct infeasibility because it
2758  * contradicts any other variable fixed to one in this clique
2759  */
2760  if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2761  || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2762  {
2763  /* impossible because we would have detected this in the previous cleanup loop */
2764  assert(clqvar != onefixedvar);
2765  *infeasible = TRUE;
2766 
2767  return SCIP_OKAY;
2768  }
2769  continue;
2770  }
2771 
2772  SCIP_CALL( SCIPvarDelCliqueFromList(clqvar, blkmem, clqval, clique) );
2773 
2774 /* the following piece of code is wrong at this point because it assumes sorted variables. can be enabled if sorting
2775  * of variables is performed earlier than it is now
2776  */
2777 #ifdef SCIP_DISABLED_CODE
2778  /* if one of the other variables occurs multiple times, we can
2779  * 1) deduce infeasibility if it occurs with different values
2780  * 2) wait for the last occurence to fix it
2781  */
2782  while( v < clique->nvars - 1 && clique->vars[v + 1] == clqvar )
2783  {
2784  if( clique->values[v + 1] != clique->values[v] )
2785  {
2786  *infeasible = TRUE;
2787  return SCIP_OKAY;
2788  }
2789  ++v;
2790  }
2791 #endif
2792  SCIPsetDebugMsg(set, "fixing variable %s in clique %u to %d\n", SCIPvarGetName(clqvar), clique->id, clqval ? 0 : 1);
2793 
2794  SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2795  eventqueue, cliquetable, !clqval, infeasible, nchgbds) );
2796 
2797  if( *infeasible )
2798  return SCIP_OKAY;
2799  }
2800  }
2801 
2802  if( SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_COLUMN /*lint !e850*/
2803  || SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_LOOSE )
2804  {
2805  SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2806  }
2807 
2808  clique->nvars = 0;
2809  clique->equation = FALSE;
2810  clique->startcleanup = -1;
2811 
2812  return SCIP_OKAY;
2813  }
2814 
2815  if( clique->equation )
2816  {
2817  if( clique->nvars == 0 )
2818  {
2819  *infeasible = TRUE;
2820  return SCIP_OKAY;
2821  }
2822  else if( clique->nvars == 1 )
2823  {
2824  assert(SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_COLUMN
2825  || SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_LOOSE);
2826 
2827  /* clearing data and removing variable from its clique list */
2828  SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[0], blkmem, clique->values[0], clique) );
2829 
2830  SCIPsetDebugMsg(set, "fixing last variable %s in clique %u to %d\n", SCIPvarGetName(clique->vars[0]), clique->id,
2831  clique->values[0] ? 1 : 0);
2832 
2833  SCIP_CALL( SCIPvarFixBinary(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2834  branchcand, eventqueue, cliquetable, clique->values[0], infeasible, nchgbds) );
2835 
2836  clique->nvars = 0;
2837  clique->equation = FALSE;
2838  clique->startcleanup = -1;
2839 
2840  return SCIP_OKAY;
2841  }
2842  }
2843 
2844  if( needsorting )
2845  {
2846  SCIP_Bool isequation = clique->equation;
2847 
2848  /* remove multiple entries of the same variable */
2849  SCIP_CALL( sortAndMergeClique(clique->vars, clique->values, &(clique->nvars), &isequation, clique, blkmem, set, stat,
2850  transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, nchgbds, infeasible) );
2851 
2852  clique->equation = isequation;
2853  }
2854 
2855  /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2856 
2857  clique->startcleanup = -1;
2858  }
2859  assert(SCIPcliqueIsCleanedUp(clique));
2860 
2861  return SCIP_OKAY;
2862 }
2863 
2864 #ifdef SCIP_MORE_DEBUG
2865 /** checks whether clique appears in all clique lists of the involved variables */
2866 static
2868  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2869  )
2870 {
2871  SCIP_Longint nentries = 0;
2872  int c;
2873 
2874  assert(cliquetable != NULL);
2875 
2876  for( c = cliquetable->ncliques - 1; c >= 0; --c )
2877  nentries += cliquetable->cliques[c]->nvars;
2878 
2879  return (nentries == cliquetable->nentries);
2880 }
2881 #else
2882 #define checkNEntries(cliquetable) TRUE
2883 #endif
2884 
2885 /** removes all empty and single variable cliques from the clique table; removes double entries from the clique table
2886  *
2887  * @note cliques can be processed several times by this method
2888  *
2889  * @todo try to detect infeasible implications, e.g., x = 1 => (y = 0 && y = 1)
2890  */
2892  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2893  BMS_BLKMEM* blkmem, /**< block memory */
2894  SCIP_SET* set, /**< global SCIP settings */
2895  SCIP_STAT* stat, /**< problem statistics */
2896  SCIP_PROB* transprob, /**< transformed problem */
2897  SCIP_PROB* origprob, /**< original problem */
2898  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2899  SCIP_REOPT* reopt, /**< reoptimization data structure */
2900  SCIP_LP* lp, /**< current LP data */
2901  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2902  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2903  int* nchgbds, /**< pointer to store number of fixed variables */
2904  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2905  )
2906 {
2907  assert(cliquetable != NULL);
2908  assert(stat != NULL);
2909  assert(infeasible != NULL);
2910 
2911  *infeasible = FALSE;
2912 
2913  /* check if we have anything to do */
2914  if( stat->npresolfixedvars == cliquetable->ncleanupfixedvars
2915  && stat->npresolaggrvars == cliquetable->ncleanupaggrvars
2916  && cliquetable->ndirtycliques == 0 )
2917  return SCIP_OKAY;
2918 
2919  SCIPsetDebugMsg(set, "cleaning up clique table with %d cliques (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
2920 
2921  /* delay events */
2922  SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
2923 
2924  cliquetable->incleanup = TRUE;
2925  while( cliquetable->ndirtycliques > 0 && !(*infeasible) )
2926  {
2927  SCIP_CLIQUE* clique;
2928  SCIP_CLIQUE* sameclique;
2929 
2930  clique = cliquetable->cliques[0];
2931 
2932  assert(!SCIPcliqueIsCleanedUp(clique));
2933 
2934  /* remove not clean up clique from hastable */
2935  SCIP_CALL( SCIPhashtableRemove(cliquetable->hashtable, (void*)clique) );
2936  cliquetable->nentries -= clique->nvars;
2937  assert(cliquetable->nentries >= 0);
2938 
2939  SCIP_CALL( cliqueCleanup(clique, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2940  cliquetable, nchgbds, infeasible) );
2941 
2942  if( *infeasible )
2943  break;
2944 
2945  assert(SCIPcliqueIsCleanedUp(clique));
2946 
2947  /* swap freshly cleaned clique with last dirty clique */
2948  cliquetable->ndirtycliques--;
2949  cliquetableSwapCliques(cliquetable, 0, cliquetable->ndirtycliques);
2950  cliqueCheck(clique);
2951 
2952  /* @todo check if we can/want to aggregate variables with the following code */
2953 #ifdef SCIP_DISABLED_CODE
2954  if( clique->nvars == 2 && clique->equation && SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING )
2955  {
2956  SCIP_VAR* var0;
2957  SCIP_VAR* var1;
2958  SCIP_Real scalarx;
2959  SCIP_Real scalary;
2960  SCIP_Real rhs = 1.0;
2961  SCIP_Bool aggregated;
2962 
2963  printf("aggr vars, clique %d\n", clique->id);
2964 
2965  if( SCIPvarGetType(clique->vars[0]) >= SCIPvarGetType(clique->vars[1]) )
2966  {
2967  var0 = clique->vars[0];
2968  var1 = clique->vars[1];
2969 
2970  if( !clique->values[0] )
2971  {
2972  scalarx = -1.0;
2973  rhs -= 1.0;
2974  }
2975  else
2976  scalarx = 1.0;
2977 
2978  if( !clique->values[1] )
2979  {
2980  scalary = -1.0;
2981  rhs -= 1.0;
2982  }
2983  else
2984  scalary = 1.0;
2985  }
2986  else
2987  {
2988  var0 = clique->vars[1];
2989  var1 = clique->vars[0];
2990 
2991  if( !clique->values[0] )
2992  {
2993  scalary = -1.0;
2994  rhs -= 1.0;
2995  }
2996  else
2997  scalary = 1.0;
2998 
2999  if( !clique->values[1] )
3000  {
3001  scalarx = -1.0;
3002  rhs -= 1.0;
3003  }
3004  else
3005  scalarx = 1.0;
3006  }
3007 
3010 
3011  /* aggregate the variable */
3012  SCIP_CALL( SCIPvarTryAggregateVars(set, blkmem, stat, transprob, origprob, primal,
3013  tree, lp, cliquetable, branchcand, eventfilter, eventqueue,
3014  var0, var1, scalarx, scalary, rhs, infeasible, &aggregated) );
3015 
3016  assert(aggregated || *infeasible);
3017  }
3018 #endif
3019 
3020  sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
3021 
3022  /* check if the clique is already contained in the clique table, or if it is redundant (too small) */
3023  if( clique->nvars <= 1 || sameclique != NULL )
3024  {
3025  int j;
3026 
3027  /* infeasible or fixing should be performed already on trivial clique */
3028  assert(clique->nvars > 1 || !clique->equation);
3029 
3030  /* if the clique which is already in the hashtable is an inequality and the current clique is an equation, we
3031  * update the equation status of the old one
3032  */
3033  if( clique->nvars > 1 && clique->equation && !sameclique->equation )
3034  {
3035  assert(sameclique->nvars >= 2);
3036 
3037  /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
3038  * the sameclique from the hashmap while adding the new clique
3039  */
3040  sameclique->equation = TRUE;
3041  }
3042 
3043  /* delete the clique from the variables' clique lists */
3044  for( j = 0; j < clique->nvars; ++j )
3045  {
3046  SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[j], blkmem, clique->values[j], clique) );
3047  }
3048 
3049  /* free clique and remove it from clique table */
3050  cliqueFree(&clique, blkmem);
3051  cliquetable->ncliques--;
3052  /* insert a clean clique from the end of the array */
3053  if( cliquetable->ndirtycliques < cliquetable->ncliques )
3054  {
3055  assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ncliques]));
3056  cliquetable->cliques[cliquetable->ndirtycliques] = cliquetable->cliques[cliquetable->ncliques];
3057  cliquetable->cliques[cliquetable->ndirtycliques]->index = cliquetable->ndirtycliques;
3058  }
3059  }
3060  else
3061  {
3062  cliquetable->nentries += clique->nvars;
3063 
3064  SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
3065  if( !clique->eventsissued )
3066  {
3067  int j;
3068 
3069  /* issue IMPLADDED event on each variable in the clique */
3070  for( j = 0; j < clique->nvars; ++j )
3071  {
3072  SCIP_EVENT* event;
3073 
3074  SCIP_CALL( SCIPeventCreateImplAdded(&event, blkmem, clique->vars[j]) );
3075  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3076  }
3077  clique->eventsissued = TRUE;
3078  }
3079  }
3080  }
3081  cliquetable->incleanup = FALSE;
3082 
3083  /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */
3084  cliquetable->ncleanupfixedvars = stat->npresolfixedvars;
3085  cliquetable->ncleanupaggrvars = stat->npresolaggrvars;
3086  assert(*infeasible || cliquetable->ndirtycliques == 0);
3087 
3088  assert(*infeasible || checkNEntries(cliquetable)); /*lint !e506*/
3089 
3090  SCIPsetDebugMsg(set, "cleaned up clique table has %d cliques left (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
3091 
3092  /* process events */
3093  SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, NULL, lp, branchcand, NULL) );
3094 
3095  return SCIP_OKAY;
3096 }
3097 
3098 /** computes connected components of the clique table
3099  *
3100  * an update becomes necessary if a clique gets added with variables from different components
3101  */
3103  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3104  SCIP_SET* set, /**< global SCIP settings */
3105  BMS_BLKMEM* blkmem, /**< block memory */
3106  SCIP_VAR** vars, /**< array of problem variables, sorted by variable type */
3107  int nbinvars, /**< number of binary variables */
3108  int nintvars, /**< number of integer variables */
3109  int nimplvars /**< number of implicit integer variables */
3110  )
3111 {
3112  SCIP_DISJOINTSET* djset;
3113  int nimplbinvars;
3114  int v;
3115  int c;
3116  int nbinvarstotal;
3117  int ndiscvars;
3118  int nnonbinvars;
3119 
3120  SCIP_CLIQUE** cliques;
3121 
3122  assert(cliquetable != NULL);
3123  assert(vars != NULL);
3124 
3125  nimplbinvars = 0;
3126  cliquetable->compsfromscratch = FALSE;
3127  ndiscvars = nbinvars + nintvars + nimplvars;
3128 
3129  /* detect integer and implicit integer variables with bounds {0,1} because they might appear in cliques, as well */
3130  for( v = nbinvars; v < ndiscvars; ++v )
3131  {
3132  if( SCIPvarIsBinary(vars[v]) )
3133  ++nimplbinvars;
3134  }
3135 
3136  /* count binary and implicit binary variables */
3137  nbinvarstotal = nbinvars + nimplbinvars;
3138 
3139  /* if there are no binary variables, return */
3140  if( nbinvarstotal == 0 )
3141  {
3142  SCIPsetDebugMsg(set, "0 binary variables in total --> 0 connected components in the clique table");
3143  cliquetable->ncliquecomponents = 0;
3144  return SCIP_OKAY;
3145  }
3146 
3147  /* no cliques are present */
3148  if( cliquetable->ncliques == 0 )
3149  {
3150  SCIPsetDebugMsg(set, "0 cliques --> Clique table has %d isolated nodes", nbinvarstotal);
3151  cliquetable->ncliquecomponents = nbinvarstotal;
3152  return SCIP_OKAY;
3153  }
3154 
3155  /* create or clear the variable index mapping */
3156  if( cliquetable->varidxtable == NULL )
3157  {
3158  SCIP_CALL( SCIPhashmapCreate(&(cliquetable)->varidxtable, blkmem, ndiscvars) );
3159  }
3160  else
3161  {
3162  SCIP_CALL( SCIPhashmapRemoveAll(cliquetable->varidxtable) );
3163  }
3164 
3165  /* loop through variables and store their respective positions in the hash map if they are binary */
3166  for( v = 0; v < ndiscvars; ++v )
3167  {
3168  SCIP_VAR* var = vars[v];
3169  if( SCIPvarIsBinary(var) )
3170  {
3171  /* consider only active representatives */
3172  if( SCIPvarIsActive(var) )
3173  {
3174  SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3175  }
3176  else
3177  {
3178  var = SCIPvarGetProbvar(var);
3179  if( SCIPvarIsActive(var) )
3180  {
3181  SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3182  }
3183  }
3184  }
3185  }
3186 
3187  /* free previous disjoint set (union find) data structure which has become outdated if new variables are present */
3188  if( cliquetable->djset != NULL )
3189  SCIPdisjointsetFree(&cliquetable->djset, blkmem);
3190 
3191  /* we need to consider integer and implicit integer variables for which SCIPvarIsBinary() returns TRUE.
3192  * These may be scattered across the ninteger + nimplvars implicit integer variables.
3193  * For simplicity, we add all integer and implicit integer variables as nodes to the graph, and subtract
3194  * the amount of nonbinary integer and implicit integer variables afterwards.
3195  */
3196  SCIP_CALL( SCIPdisjointsetCreate(&cliquetable->djset, blkmem, ndiscvars) );
3197  djset = cliquetable->djset;
3198 
3199  /* subtract all (implicit) integer for which SCIPvarIsBinary() returns FALSE */
3200  nnonbinvars = (nintvars + nimplvars) - nimplbinvars;
3201 
3202  cliques = cliquetable->cliques;
3203 
3204  /* for every clique, we connect clique variable components, treating a clique as a path
3205  *
3206  * if the graph turns out to be completely connected (except for the nonbinary variables), we terminate */
3207  for( c = 0; c < cliquetable->ncliques && SCIPdisjointsetGetComponentCount(djset) > 1 + nnonbinvars; ++c )
3208  {
3209  SCIP_CLIQUE* clique;
3210 
3211  clique = cliques[c];
3212  cliquetableUpdateConnectednessClique(cliquetable, clique);
3213  }
3214 
3215  /* subtract superfluous integer and implicit integer variables added to the auxiliary graph */
3216  cliquetable->ncliquecomponents = SCIPdisjointsetGetComponentCount(djset) - nnonbinvars;
3217  assert(cliquetable->ncliquecomponents >= 0);
3218  assert(cliquetable->ncliquecomponents <= nbinvarstotal);
3219 
3220  SCIPsetDebugMsg(set, "connected components detection: %d comps (%d clqs, %d vars)", cliquetable->ncliquecomponents, cliquetable->ncliques, nbinvarstotal);
3221 
3222  return SCIP_OKAY;
3223 }
3224 
3225 /*
3226  * simple functions implemented as defines
3227  */
3228 
3229 /* In debug mode, the following methods are implemented as function calls to ensure
3230  * type validity.
3231  * In optimized mode, the methods are implemented as defines to improve performance.
3232  * However, we want to have them in the library anyways, so we have to undef the defines.
3233  */
3234 
3235 #undef SCIPvboundsGetNVbds
3236 #undef SCIPvboundsGetVars
3237 #undef SCIPvboundsGetCoefs
3238 #undef SCIPvboundsGetConstants
3239 #undef SCIPimplicsGetNImpls
3240 #undef SCIPimplicsGetVars
3241 #undef SCIPimplicsGetTypes
3242 #undef SCIPimplicsGetBounds
3243 #undef SCIPimplicsGetIds
3244 #undef SCIPcliqueGetNVars
3245 #undef SCIPcliqueGetVars
3246 #undef SCIPcliqueGetValues
3247 #undef SCIPcliqueGetId
3248 #undef SCIPcliqueGetIndex
3249 #undef SCIPcliqueIsCleanedUp
3250 #undef SCIPcliqueIsEquation
3251 #undef SCIPcliquelistGetNCliques
3252 #undef SCIPcliquelistGetCliques
3253 #undef SCIPcliquelistCheck
3254 #undef SCIPcliquetableGetNCliques
3255 #undef SCIPcliquetableGetCliques
3256 #undef SCIPcliquetableGetNEntries
3257 #undef SCIPcliquetableGetNCliqueComponents
3258 #undef SCIPcliquetableNeedsComponentUpdate
3259 
3260 /** gets number of variable bounds contained in given variable bounds data structure */
3262  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3263  )
3264 {
3265  return vbounds != NULL ? vbounds->len : 0;
3266 }
3267 
3268 /** gets array of variables contained in given variable bounds data structure */
3270  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3271  )
3272 {
3273  return vbounds != NULL ? vbounds->vars : NULL;
3274 }
3275 
3276 /** gets array of coefficients contained in given variable bounds data structure */
3278  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3279  )
3280 {
3281  return vbounds != NULL ? vbounds->coefs : NULL;
3282 }
3283 
3284 /** gets array of constants contained in given variable bounds data structure */
3286  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3287  )
3288 {
3289  return vbounds != NULL ? vbounds->constants : NULL;
3290 }
3291 
3292 /** gets number of implications for a given binary variable fixing */
3294  SCIP_IMPLICS* implics, /**< implication data */
3295  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3296  )
3297 {
3298  return implics != NULL ? implics->nimpls[varfixing] : 0;
3299 }
3300 
3301 /** gets array with implied variables for a given binary variable fixing */
3303  SCIP_IMPLICS* implics, /**< implication data */
3304  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3305  )
3306 {
3307  return implics != NULL ? implics->vars[varfixing] : NULL;
3308 }
3309 
3310 /** gets array with implication types for a given binary variable fixing */
3312  SCIP_IMPLICS* implics, /**< implication data */
3313  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3314  )
3315 {
3316  return implics != NULL ? implics->types[varfixing] : NULL;
3317 }
3318 
3319 /** gets array with implication bounds for a given binary variable fixing */
3321  SCIP_IMPLICS* implics, /**< implication data */
3322  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3323  )
3324 {
3325  return implics != NULL ? implics->bounds[varfixing] : NULL;
3326 }
3327 
3328 /** Gets array with unique implication identifiers for a given binary variable fixing.
3329  * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
3330  * its id is negative, otherwise it is nonnegative.
3331  */
3333  SCIP_IMPLICS* implics, /**< implication data */
3334  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3335  )
3336 {
3337  return implics != NULL ? implics->ids[varfixing] : NULL;
3338 }
3339 
3340 /** gets number of variables in the cliques */
3342  SCIP_CLIQUE* clique /**< clique data structure */
3343  )
3344 {
3345  assert(clique != NULL);
3346 
3347  return clique->nvars;
3348 }
3349 
3350 /** gets array of active problem variables in the cliques */
3352  SCIP_CLIQUE* clique /**< clique data structure */
3353  )
3354 {
3355  assert(clique != NULL);
3356 
3357  return clique->vars;
3358 }
3359 
3360 /** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or
3361  * to TRUE in the clique
3362  */
3364  SCIP_CLIQUE* clique /**< clique data structure */
3365  )
3366 {
3367  assert(clique != NULL);
3368 
3369  return clique->values;
3370 }
3371 
3372 /** gets unique identifier of the clique */
3373 unsigned int SCIPcliqueGetId(
3374  SCIP_CLIQUE* clique /**< clique data structure */
3375  )
3376 {
3377  unsigned int id;
3378 
3379  assert(clique != NULL);
3380 
3381  id = clique->id; /*lint !e732*/
3382 
3383  return id;
3384 }
3385 
3386 /** gets index of the clique in the clique table */
3388  SCIP_CLIQUE* clique /**< clique data structure */
3389  )
3390 {
3391  assert(clique != NULL);
3392 
3393  return clique->index;
3394 }
3395 
3396 /** gets unique identifier of the clique */
3398  SCIP_CLIQUE* clique /**< clique data structure */
3399  )
3400 {
3401  assert(clique != NULL);
3402 
3403  return (clique->startcleanup == -1);
3404 }
3405 
3406 /** return whether the given clique is an equation */
3408  SCIP_CLIQUE* clique /**< clique data structure */
3409  )
3410 {
3411  assert(clique != NULL);
3412 
3413  return (SCIP_Bool)(clique->equation); /*lint !e571*/
3414 }
3415 
3416 /** returns the number of cliques stored in the clique list */
3418  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3419  SCIP_Bool value /**< value of the variable for which the cliques should be returned */
3420  )
3421 {
3422  return cliquelist != NULL ? cliquelist->ncliques[value] : 0;
3423 }
3424 
3425 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */
3427  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3428  SCIP_Bool value /**< value of the variable for which the cliques should be returned */
3429  )
3430 {
3431  return cliquelist != NULL ? cliquelist->cliques[value] : NULL;
3432 }
3433 
3434 /** checks whether variable is contained in all cliques of the cliquelist */
3436  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3437  SCIP_VAR* var /**< variable, the clique list belongs to */
3438  )
3439 {
3440  /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MORE_DEBUG because it can take at lot of time to check for
3441  * correctness
3442  */
3443 #ifndef NDEBUG
3444  int value;
3445 
3446  assert(SCIPvarGetNCliques(var, FALSE) == SCIPcliquelistGetNCliques(cliquelist, FALSE));
3447  assert(SCIPvarGetCliques(var, FALSE) == SCIPcliquelistGetCliques(cliquelist, FALSE));
3448  assert(SCIPvarGetNCliques(var, TRUE) == SCIPcliquelistGetNCliques(cliquelist, TRUE));
3449  assert(SCIPvarGetCliques(var, TRUE) == SCIPcliquelistGetCliques(cliquelist, TRUE));
3450 
3451  for( value = 0; value < 2; ++value )
3452  {
3453  SCIP_CLIQUE** cliques;
3454  int ncliques;
3455  int i;
3456 
3457  ncliques = SCIPcliquelistGetNCliques(cliquelist, (SCIP_Bool)value);
3458  cliques = SCIPcliquelistGetCliques(cliquelist, (SCIP_Bool)value);
3459  for( i = 0; i < ncliques; ++i )
3460  {
3461  SCIP_CLIQUE* clique;
3462  int pos;
3463 
3464  clique = cliques[i];
3465  assert(clique != NULL);
3466 
3467  pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value);
3468  assert(0 <= pos && pos < clique->nvars);
3469  assert(clique->vars[pos] == var);
3470  assert(clique->values[pos] == (SCIP_Bool)value);
3471  }
3472  }
3473 #endif
3474 }
3475 
3476 /** gets the number of cliques stored in the clique table */
3478  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3479  )
3480 {
3481  assert(cliquetable != NULL);
3482 
3483  return cliquetable->ncliques;
3484 }
3485 
3486 /** gets the number of cliques created so far by the clique table */
3488  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3489  )
3490 {
3491  assert(cliquetable != NULL);
3492 
3493  return cliquetable->ncreatedcliques;
3494 }
3495 
3496 /** gets the array of cliques stored in the clique table */
3498  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3499  )
3500 {
3501  assert(cliquetable != NULL);
3502 
3503  return cliquetable->cliques;
3504 }
3505 
3506 /** gets the number of entries in the whole clique table */
3508  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3509  )
3510 {
3511  assert(cliquetable != NULL);
3512 
3513  return cliquetable->nentries;
3514 }
3515 
3516 /** returns the number of clique components, or -1 if update is necessary first */
3518  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3519  )
3520 {
3521  return cliquetable->compsfromscratch ? -1 : cliquetable->ncliquecomponents;
3522 }
3523 
3524 /** returns TRUE iff the connected clique components need an update (because new cliques were added) */
3526  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3527  )
3528 {
3529  return cliquetable->compsfromscratch || cliquetable->djset == NULL;
3530 }
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:1657
#define HASHTABLE_CLIQUETABLE_SIZE
Definition: implics.c:1757
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:5987
static int cliquetableGetNodeIndexBinvar(SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *binvar)
Definition: implics.c:2235
SCIP_HASHMAP * varidxtable
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:459
internal methods for managing events
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3351
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
int SCIPcliquetableGetVarComponentIdx(SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var)
Definition: implics.c:2322
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:140
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:3507
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:1125
#define SCIPsetDuplicateBufferArray(set, ptr, source, num)
Definition: set.h:1687
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:10997
public methods for implications, variable bounds, and cliques
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
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
int SCIPdisjointsetGetSize(SCIP_DISJOINTSET *djset)
Definition: misc.c:11104
SCIP_Real * constants
#define SCIP_HASHSIZE_CLIQUES_SMALL
Definition: def.h:294
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:3302
int npresolaggrvars
Definition: struct_stat.h:235
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
static SCIP_RETCODE cliquetableEnsureSize(SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, int num)
Definition: implics.c:1833
int npresolfixedvars
Definition: struct_stat.h:234
int SCIPcliquelistGetNCliques(SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)
Definition: implics.c:3417
SCIP_VAR ** SCIPvboundsGetVars(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3269
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
#define SCIPdebugCheckClique(set, vars, values, nvars)
Definition: debug.h:270
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1115
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3387
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:2620
#define FALSE
Definition: def.h:73
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:1746
SCIP_Bool SCIPsetIsZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6099
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
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3407
SCIP_RETCODE SCIPcliquetableCreate(SCIP_CLIQUETABLE **cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem)
Definition: implics.c:1760
#define SCIPsetAllocBufferArray(set, ptr, num)
Definition: set.h:1685
#define checkNEntries(cliquetable)
Definition: implics.c:2882
static SCIP_RETCODE cliquelistCreate(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
Definition: implics.c:1396
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:2891
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5580
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17340
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:1796
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2617
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17136
SCIP_CLIQUE ** SCIPcliquelistGetCliques(SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)
Definition: implics.c:3426
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:1456
#define SCIPsetFreeBufferArray(set, ptr)
Definition: set.h:1692
#define BMSfreeMemory(ptr)
Definition: memory.h:137
SCIP_Real * coefs
static void implicsSearchVar(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, int *poslower, int *posupper, int *posadd)
Definition: implics.c:503
Definition: heur_padm.c:125
static void cliquetableSwapCliques(SCIP_CLIQUETABLE *cliquetable, int first, int second)
Definition: implics.c:930
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:956
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
SCIP_EXPORT void SCIPsortPtrBool(void **ptrarray, SCIP_Bool *boolarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPcliquetableGetNCliquesCreated(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3487
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
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:978
int * ids[2]
#define SCIP_HASHSIZE_CLIQUES
Definition: def.h:291
void SCIPcliquelistFree(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
Definition: implics.c:1415
int SCIPcliqueSearchVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1055
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
int SCIPcliquetableGetNCliques(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3477
SCIP_VAR * w
Definition: circlepacking.c:58
SCIP_Bool compsfromscratch
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:453
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:514
SCIP_BOUNDTYPE * SCIPimplicsGetTypes(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3311
SCIP_EXPORT SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
Definition: var.c:12049
void SCIPcliqueDelVar(SCIP_CLIQUE *clique, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1259
SCIP_Bool SCIPimplicsContainsImpl(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: implics.c:907
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11075
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
static SCIP_DECL_HASHGETKEY(hashgetkeyClique)
Definition: implics.c:1713
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11024
#define BMSmoveMemoryArray(ptr, source, num)
Definition: memory.h:130
static int cliquesSearchClique(SCIP_CLIQUE **cliques, int ncliques, SCIP_CLIQUE *clique)
Definition: implics.c:1307
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11094
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real * SCIPvboundsGetCoefs(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3277
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:370
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:6473
SCIP_VAR ** vars
SCIP_Real * SCIPvboundsGetConstants(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3285
Definition: grphload.c:88
static void cliquetableUpdateConnectednessClique(SCIP_CLIQUETABLE *cliquetable, SCIP_CLIQUE *clique)
Definition: implics.c:2278
unsigned int equation
SCIP_Bool SCIPcliquelistsHaveCommonClique(SCIP_CLIQUELIST *cliquelist1, SCIP_Bool value1, SCIP_CLIQUELIST *cliquelist2, SCIP_Bool value2)
Definition: implics.c:1579
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6429
int SCIPcliquetableGetNCliqueComponents(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3517
void SCIPvboundsShrink(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, int newnvbds)
Definition: implics.c:324
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:456
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:5160
datastructures for implications, variable bounds, and cliques
public data structures and miscellaneous methods
SCIP_Bool SCIPcliquetableNeedsComponentUpdate(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3525
SCIP_EXPORT SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17493
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2286
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_EXPORT SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11989
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:458
int * SCIPimplicsGetIds(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3332
SCIP_RETCODE SCIPcliquetableComputeCliqueComponents(SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_VAR **vars, int nbinvars, int nintvars, int nimplvars)
Definition: implics.c:3102
#define MAX(x, y)
Definition: tclique_def.h:83
int SCIPimplicsGetNImpls(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3293
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3363
#define SCIPsetDebugMsg
Definition: set.h:1721
SCIP_RETCODE SCIPvarAddCliqueToList(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: var.c:11167
static SCIP_DECL_HASHKEYEQ(hashkeyeqClique)
Definition: implics.c:1720
SCIP_BOUNDTYPE * types[2]
#define cliqueCheck(clique)
Definition: implics.c:1391
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:10953
datastructures for problem statistics
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3573
SCIP_EXPORT SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18030
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6407
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:2350
static SCIP_RETCODE vboundsCreate(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem)
Definition: implics.c:46
SCIP_Longint nnz
Definition: struct_stat.h:177
int SCIPvboundsGetNVbds(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3261
static void cliqueFree(SCIP_CLIQUE **clique, BMS_BLKMEM *blkmem)
Definition: implics.c:1012
static SCIP_RETCODE cliqueEnsureSize(SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
Definition: implics.c:1029
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:1856
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
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
unsigned int id
public methods for message output
void SCIPcliquelistCheck(SCIP_CLIQUELIST *cliquelist, SCIP_VAR *var)
Definition: implics.c:3435
SCIP_CLIQUE ** cliques[2]
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define SCIP_Real
Definition: def.h:163
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:119
#define SCIP_Longint
Definition: def.h:148
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
Definition: implics.c:3373
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:10957
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6451
static SCIP_RETCODE cliquelistEnsureSize(SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, int num)
Definition: implics.c:1432
SCIP_STAGE SCIPsetGetStage(SCIP_SET *set)
Definition: set.c:2924
SCIP_EXPORT SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:12081
SCIP_Bool SCIPvarIsMarkedDeleteGlobalStructures(SCIP_VAR *var)
Definition: var.c:17284
SCIP_Bool SCIPcliqueIsCleanedUp(SCIP_CLIQUE *clique)
Definition: implics.c:3397
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3341
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:443
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:429
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18019
SCIP_Real * SCIPimplicsGetBounds(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3320
#define SCIP_ALLOC(x)
Definition: def.h:381
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:11129
datastructures for global SCIP settings
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:449
SCIP_CLIQUE ** SCIPcliquetableGetCliques(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3497
void SCIPimplicsFree(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem)
Definition: implics.c:442
SCIP_EXPORT int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17350
SCIP_RETCODE SCIPcliquelistDel(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: implics.c:1501
SCIP_Longint nentries
int nimplications
Definition: struct_stat.h:229
SCIP_RETCODE SCIPvarDelCliqueFromList(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: var.c:11189