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