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