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