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