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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file implics.c
17  * @brief methods for implications, variable bounds, and clique tables
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <stdlib.h>
24 #include <assert.h>
25 
26 #include "scip/def.h"
27 #include "scip/set.h"
28 #include "scip/stat.h"
29 #include "scip/event.h"
30 #include "scip/var.h"
31 #include "scip/implics.h"
32 #include "scip/pub_message.h"
33 #include "scip/pub_misc.h"
34 #include "scip/debug.h"
35 
36 #ifndef NDEBUG
37 #include "scip/struct_implics.h"
38 #endif
39 
40 
41 
42 /*
43  * methods for variable bounds
44  */
45 
46 /** creates a variable bounds data structure */
47 static
48 SCIP_RETCODE vboundsCreate(
49  SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
50  BMS_BLKMEM* blkmem /**< block memory */
51  )
52 {
53  assert(vbounds != NULL);
54 
55  SCIP_ALLOC( BMSallocBlockMemory(blkmem, vbounds) );
56  (*vbounds)->vars = NULL;
57  (*vbounds)->coefs = NULL;
58  (*vbounds)->constants = NULL;
59  (*vbounds)->len = 0;
60  (*vbounds)->size = 0;
61 
62  return SCIP_OKAY;
63 }
64 
65 /** frees a variable bounds data structure */
66 void SCIPvboundsFree(
67  SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
68  BMS_BLKMEM* blkmem /**< block memory */
69  )
70 {
71  assert(vbounds != NULL);
72 
73  if( *vbounds != NULL )
74  {
75  BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->vars, (*vbounds)->size);
76  BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->coefs, (*vbounds)->size);
77  BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->constants, (*vbounds)->size);
78  BMSfreeBlockMemory(blkmem, vbounds);
79  }
80 }
81 
82 /** ensures, that variable bounds arrays can store at least num entries */
83 static
84 SCIP_RETCODE vboundsEnsureSize(
85  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
86  BMS_BLKMEM* blkmem, /**< block memory */
87  SCIP_SET* set, /**< global SCIP settings */
88  int num /**< minimum number of entries to store */
89  )
90 {
91  assert(vbounds != NULL);
92 
93  /* create variable bounds data structure, if not yet existing */
94  if( *vbounds == NULL )
95  {
96  SCIP_CALL( vboundsCreate(vbounds, blkmem) );
97  }
98  assert(*vbounds != NULL);
99  assert((*vbounds)->len <= (*vbounds)->size);
100 
101  if( num > (*vbounds)->size )
102  {
103  int newsize;
104 
105  newsize = SCIPsetCalcMemGrowSize(set, num);
106  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->vars, (*vbounds)->size, newsize) );
107  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->coefs, (*vbounds)->size, newsize) );
108  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->constants, (*vbounds)->size, newsize) );
109  (*vbounds)->size = newsize;
110  }
111  assert(num <= (*vbounds)->size);
112 
113  return SCIP_OKAY;
114 }
115 
116 /** binary searches the insertion position of the given variable in the vbounds data structure */
117 static
118 SCIP_RETCODE vboundsSearchPos(
119  SCIP_VBOUNDS* vbounds, /**< variable bounds data structure, or NULL */
120  SCIP_VAR* var, /**< variable to search in vbounds data structure */
121  SCIP_Bool negativecoef, /**< is coefficient b negative? */
122  int* insertpos, /**< pointer to store position where to insert new entry */
123  SCIP_Bool* found /**< pointer to store whether the same variable was found at the returned pos */
124  )
125 {
126  SCIP_Bool exists;
127  int pos;
128 
129  assert(insertpos != NULL);
130  assert(found != NULL);
131 
132  /* check for empty vbounds data */
133  if( vbounds == NULL )
134  {
135  *insertpos = 0;
136  *found = FALSE;
137  return SCIP_OKAY;
138  }
139  assert(vbounds->len >= 0);
140 
141  /* binary search for the given variable */
142  exists = SCIPsortedvecFindPtr((void**)vbounds->vars, SCIPvarComp, var, vbounds->len, &pos);
143 
144  if( exists )
145  {
146  /* we found the variable: check if the sign of the coefficient matches */
147  assert(var == vbounds->vars[pos]);
148  if( (vbounds->coefs[pos] < 0.0) == negativecoef )
149  {
150  /* the variable exists with the same sign at the current position */
151  *insertpos = pos;
152  *found = TRUE;
153  }
154  else if( negativecoef )
155  {
156  assert(vbounds->coefs[pos] > 0.0);
157  if( pos+1 < vbounds->len && vbounds->vars[pos+1] == var )
158  {
159  /* the variable exists with the desired sign at the next position */
160  assert(vbounds->coefs[pos+1] < 0.0);
161  *insertpos = pos+1;
162  *found = TRUE;
163  }
164  else
165  {
166  /* the negative coefficient should be inserted to the right of the positive one */
167  *insertpos = pos+1;
168  *found = FALSE;
169  }
170  }
171  else
172  {
173  assert(vbounds->coefs[pos] < 0.0);
174  if( pos-1 >= 0 && vbounds->vars[pos-1] == var )
175  {
176  /* the variable exists with the desired sign at the previous position */
177  assert(vbounds->coefs[pos-1] > 0.0);
178  *insertpos = pos-1;
179  *found = TRUE;
180  }
181  else
182  {
183  /* the positive coefficient should be inserted to the left of the negative one */
184  *insertpos = pos;
185  *found = FALSE;
186  }
187  }
188  }
189  else
190  {
191  *insertpos = pos;
192  *found = FALSE;
193  }
194 
195  return SCIP_OKAY;
196 }
197 
198 /** adds a variable bound to the variable bounds data structure */
199 SCIP_RETCODE SCIPvboundsAdd(
200  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
201  BMS_BLKMEM* blkmem, /**< block memory */
202  SCIP_SET* set, /**< global SCIP settings */
203  SCIP_BOUNDTYPE vboundtype, /**< type of variable bound (LOWER or UPPER) */
204  SCIP_VAR* var, /**< variable z in x <= b*z + d or x >= b*z + d */
205  SCIP_Real coef, /**< coefficient b in x <= b*z + d or x >= b*z + d */
206  SCIP_Real constant, /**< constant d in x <= b*z + d or x >= b*z + d */
207  SCIP_Bool* added /**< pointer to store whether the variable bound was added */
208  )
209 {
210  int insertpos;
211  SCIP_Bool found;
212 
213  assert(vbounds != NULL);
214  assert(var != NULL);
215  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
216  assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
217  assert(added != NULL);
218  assert(!SCIPsetIsZero(set, coef));
219 
220  *added = FALSE;
221 
222  /* identify insertion position of variable */
223  SCIP_CALL( vboundsSearchPos(*vbounds, var, (coef < 0.0), &insertpos, &found) );
224  if( found )
225  {
226  /* the same variable already exists in the vbounds data structure: use the better vbound */
227  assert(*vbounds != NULL);
228  assert(0 <= insertpos && insertpos < (*vbounds)->len);
229  assert((*vbounds)->vars[insertpos] == var);
230  assert(((*vbounds)->coefs[insertpos] < 0.0) == (coef < 0.0));
231 
232  if( vboundtype == SCIP_BOUNDTYPE_UPPER )
233  {
234  if( constant + MIN(coef, 0.0) < (*vbounds)->constants[insertpos] + MIN((*vbounds)->coefs[insertpos], 0.0) )
235  {
236  (*vbounds)->coefs[insertpos] = coef;
237  (*vbounds)->constants[insertpos] = constant;
238  *added = TRUE;
239  }
240  }
241  else
242  {
243  if( constant + MAX(coef, 0.0) > (*vbounds)->constants[insertpos] + MAX((*vbounds)->coefs[insertpos], 0.0) )
244  {
245  (*vbounds)->coefs[insertpos] = coef;
246  (*vbounds)->constants[insertpos] = constant;
247  *added = TRUE;
248  }
249  }
250  }
251  else
252  {
253  int i;
254 
255  /* the given variable does not yet exist in the vbounds */
256  SCIP_CALL( vboundsEnsureSize(vbounds, blkmem, set, *vbounds != NULL ? (*vbounds)->len+1 : 1) );
257  assert(*vbounds != NULL);
258  assert(0 <= insertpos && insertpos <= (*vbounds)->len);
259  assert(0 <= insertpos && insertpos < (*vbounds)->size);
260 
261  /* insert variable at the correct position */
262  for( i = (*vbounds)->len; i > insertpos; --i )
263  {
264  assert(!SCIPsetIsZero(set, (*vbounds)->coefs[i-1]));
265  (*vbounds)->vars[i] = (*vbounds)->vars[i-1];
266  (*vbounds)->coefs[i] = (*vbounds)->coefs[i-1];
267  (*vbounds)->constants[i] = (*vbounds)->constants[i-1];
268  }
269  assert(!SCIPsetIsZero(set, coef));
270  (*vbounds)->vars[insertpos] = var;
271  (*vbounds)->coefs[insertpos] = coef;
272  (*vbounds)->constants[insertpos] = constant;
273  (*vbounds)->len++;
274  *added = TRUE;
275  }
276 
277  return SCIP_OKAY;
278 }
279 
280 /** removes from variable x a variable bound x >=/<= b*z + d with binary or integer z */
281 SCIP_RETCODE SCIPvboundsDel(
282  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
283  BMS_BLKMEM* blkmem, /**< block memory */
284  SCIP_VAR* vbdvar, /**< variable z in x >=/<= b*z + d */
285  SCIP_Bool negativecoef /**< is coefficient b negative? */
286  )
287 {
288  SCIP_Bool found;
289  int pos;
290  int i;
291 
292  assert(vbounds != NULL);
293  assert(*vbounds != NULL);
294 
295  /* searches for variable z in variable bounds of x */
296  SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) );
297  if( !found )
298  return SCIP_OKAY;
299 
300  assert(0 <= pos && pos < (*vbounds)->len);
301  assert((*vbounds)->vars[pos] == vbdvar);
302  assert(((*vbounds)->coefs[pos] < 0.0) == negativecoef);
303 
304  /* removes z from variable bounds of x */
305  for( i = pos; i < (*vbounds)->len - 1; i++ )
306  {
307  (*vbounds)->vars[i] = (*vbounds)->vars[i+1];
308  (*vbounds)->coefs[i] = (*vbounds)->coefs[i+1];
309  (*vbounds)->constants[i] = (*vbounds)->constants[i+1];
310  }
311  (*vbounds)->len--;
312 
313 #ifndef NDEBUG
314  SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) );
315  assert(!found);
316 #endif
317 
318  /* free vbounds data structure, if it is empty */
319  if( (*vbounds)->len == 0 )
320  SCIPvboundsFree(vbounds, blkmem);
321 
322  return SCIP_OKAY;
323 }
324 
325 /** reduces the number of variable bounds stored in the given variable bounds data structure */
326 void SCIPvboundsShrink(
327  SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
328  BMS_BLKMEM* blkmem, /**< block memory */
329  int newnvbds /**< new number of variable bounds */
330  )
331 {
332  assert(vbounds != NULL);
333  assert(*vbounds != NULL);
334  assert(newnvbds <= (*vbounds)->len);
335 
336  if( newnvbds == 0 )
337  SCIPvboundsFree(vbounds, blkmem);
338  else
339  (*vbounds)->len = newnvbds;
340 }
341 
342 
343 
344 
345 /*
346  * methods for implications
347  */
348 
349 #ifndef NDEBUG
350 /** comparator function for implication variables in the implication data structure */
351 static
352 SCIP_DECL_SORTPTRCOMP(compVars)
353 { /*lint --e{715}*/
354  SCIP_VAR* var1;
355  SCIP_VAR* var2;
356  SCIP_VARTYPE var1type;
357  SCIP_VARTYPE var2type;
358  int var1idx;
359  int var2idx;
360 
361  var1 = (SCIP_VAR*)elem1;
362  var2 = (SCIP_VAR*)elem2;
363  assert(var1 != NULL);
364  assert(var2 != NULL);
365  var1type = SCIPvarGetType(var1);
366  var2type = SCIPvarGetType(var2);
367  var1idx = SCIPvarGetIndex(var1);
368  var2idx = SCIPvarGetIndex(var2);
369 
370  if( var1type == var2type )
371  {
372  if( var1idx < var2idx )
373  return -1;
374  else if( var1idx > var2idx )
375  return +1;
376  else
377  return 0;
378  }
379  else
380  {
381  if( var1type == SCIP_VARTYPE_BINARY )
382  return -1;
383  if( var2type == SCIP_VARTYPE_BINARY )
384  return +1;
385  else if( var1idx < var2idx )
386  return -1;
387  else if( var1idx > var2idx )
388  return +1;
389  else
390  {
391  SCIPABORT();
392  /*lint --e{527}*/
393  return 0;
394  }
395  }
396 }
397 
398 /** performs integrity check on implications data structure */
399 static
400 void checkImplics(
401  SCIP_IMPLICS* implics, /**< implications data structure */
402  SCIP_SET* set /**< global SCIP settings */
403  )
404 {
405  SCIP_Bool varfixing;
406 
407  if( implics == NULL )
408  return;
409 
410  varfixing = FALSE;
411  do
412  {
413  SCIP_VAR** vars;
414  SCIP_BOUNDTYPE* types;
415  SCIP_Real* bounds;
416  int nimpls;
417  int nbinimpls;
418  int i;
419 
420  vars = implics->vars[varfixing];
421  types = implics->types[varfixing];
422  bounds = implics->bounds[varfixing];
423  nimpls = implics->nimpls[varfixing];
424  nbinimpls = implics->nbinimpls[varfixing];
425 
426  assert(0 <= nbinimpls && nbinimpls <= nimpls && nimpls <= implics->size[varfixing]);
427  assert(nimpls == 0 || vars != NULL);
428  assert(nimpls == 0 || types != NULL);
429  assert(nimpls == 0 || bounds != NULL);
430 
431  if( nbinimpls > 0 )
432  {
433  /* in case of implication we cannot use SCIPvarIsBinary() to check for binaries since the implication are
434  * sorted with respect to variable type; this means first the binary variables (SCIPvarGetType(var) ==
435  * SCIP_VARTYPE_BINARY) and second all others;
436  */
437  assert(SCIPvarGetType(vars[0]) == SCIP_VARTYPE_BINARY);
438  assert((types[0] == SCIP_BOUNDTYPE_LOWER) == (bounds[0] > 0.5));
439  assert(SCIPsetIsFeasZero(set, bounds[0]) || SCIPsetIsFeasEQ(set, bounds[0], 1.0));
440  }
441 
442  for( i = 1; i < nbinimpls; ++i )
443  {
444  int cmp;
445 
446  /* in case of implication we cannot use SCIPvarIsBinary() to check for binaries since the implication are
447  * sorted with respect to variable type; this means first the binary variables (SCIPvarGetType(var) ==
448  * SCIP_VARTYPE_BINARY) and second all others;
449  */
450  assert(SCIPvarGetType(vars[i]) == SCIP_VARTYPE_BINARY);
451  assert((types[i] == SCIP_BOUNDTYPE_LOWER) == (bounds[i] > 0.5));
452  assert(SCIPsetIsFeasZero(set, bounds[i]) || SCIPsetIsFeasEQ(set, bounds[i], 1.0));
453 
454  cmp = compVars(vars[i-1], vars[i]);
455  assert(cmp <= 0);
456  assert((cmp == 0) == (vars[i-1] == vars[i]));
457  assert(cmp < 0 || (types[i-1] == SCIP_BOUNDTYPE_LOWER && types[i] == SCIP_BOUNDTYPE_UPPER));
458  }
459 
460  for( i = nbinimpls; i < nimpls; ++i )
461  {
462  int cmp;
463 
464  /* in case of implication we cannot use SCIPvarIsBinary() to check for binaries since the implication are
465  * sorted with respect to variable type; this means first the binary variables (SCIPvarGetType(var) ==
466  * SCIP_VARTYPE_BINARY) and second all others;
467  */
468  assert(SCIPvarGetType(vars[i]) != SCIP_VARTYPE_BINARY);
469 
470  if( i == 0 )
471  continue;
472 
473  cmp = compVars(vars[i-1], vars[i]);
474  assert(cmp <= 0);
475  assert((cmp == 0) == (vars[i-1] == vars[i]));
476  assert(cmp < 0 || (types[i-1] == SCIP_BOUNDTYPE_LOWER && types[i] == SCIP_BOUNDTYPE_UPPER));
477  }
478 
479  varfixing = !varfixing;
480  }
481  while( varfixing == TRUE );
482 }
483 #else
484 #define checkImplics(implics,set) /**/
485 #endif
486 
487 /** creates an implications data structure */
488 static
489 SCIP_RETCODE implicsCreate(
490  SCIP_IMPLICS** implics, /**< pointer to store implications data structure */
491  BMS_BLKMEM* blkmem /**< block memory */
492  )
493 {
494  assert(implics != NULL);
495 
496  SCIP_ALLOC( BMSallocBlockMemory(blkmem, implics) );
497 
498  (*implics)->vars[0] = NULL;
499  (*implics)->types[0] = NULL;
500  (*implics)->bounds[0] = NULL;
501  (*implics)->ids[0] = NULL;
502  (*implics)->size[0] = 0;
503  (*implics)->nimpls[0] = 0;
504  (*implics)->nbinimpls[0] = 0;
505 
506  (*implics)->vars[1] = NULL;
507  (*implics)->types[1] = NULL;
508  (*implics)->bounds[1] = NULL;
509  (*implics)->ids[1] = NULL;
510  (*implics)->size[1] = 0;
511  (*implics)->nimpls[1] = 0;
512  (*implics)->nbinimpls[1] = 0;
513 
514  return SCIP_OKAY;
515 }
516 
517 /** frees an implications data structure */
518 void SCIPimplicsFree(
519  SCIP_IMPLICS** implics, /**< pointer of implications data structure to free */
520  BMS_BLKMEM* blkmem /**< block memory */
521  )
522 {
523  assert(implics != NULL);
524 
525  if( *implics != NULL )
526  {
527  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[0], (*implics)->size[0]);
528  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[0], (*implics)->size[0]);
529  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[0], (*implics)->size[0]);
530  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[0], (*implics)->size[0]);
531  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[1], (*implics)->size[1]);
532  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[1], (*implics)->size[1]);
533  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[1], (*implics)->size[1]);
534  BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[1], (*implics)->size[1]);
535  BMSfreeBlockMemory(blkmem, implics);
536  }
537 }
538 
539 /** ensures, that arrays for x == 0 or x == 1 in implications data structure can store at least num entries */
540 static
541 SCIP_RETCODE implicsEnsureSize(
542  SCIP_IMPLICS** implics, /**< pointer to implications data structure */
543  BMS_BLKMEM* blkmem, /**< block memory */
544  SCIP_SET* set, /**< global SCIP settings */
545  SCIP_Bool varfixing, /**< FALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1 */
546  int num /**< minimum number of entries to store */
547  )
548 {
549  assert(implics != NULL);
550 
551  /* create implications data structure, if not yet existing */
552  if( *implics == NULL )
553  {
554  SCIP_CALL( implicsCreate(implics, blkmem) );
555  }
556  assert(*implics != NULL);
557  assert((*implics)->nimpls[varfixing] <= (*implics)->size[varfixing]);
558 
559  if( num > (*implics)->size[varfixing] )
560  {
561  int newsize;
562 
563  newsize = SCIPsetCalcMemGrowSize(set, num);
564  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->vars[varfixing], (*implics)->size[varfixing],
565  newsize) ); /*lint !e866*/
566  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->types[varfixing], (*implics)->size[varfixing],
567  newsize) ); /*lint !e866*/
568  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->bounds[varfixing], (*implics)->size[varfixing],
569  newsize) ); /*lint !e866*/
570  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->ids[varfixing], (*implics)->size[varfixing],
571  newsize) ); /*lint !e866*/
572  (*implics)->size[varfixing] = newsize;
573  }
574  assert(num <= (*implics)->size[varfixing]);
575 
576  return SCIP_OKAY;
577 }
578 
579 /** gets the positions of the implications y >= l and y <= u in the implications data structure;
580  * if no lower or upper bound implication for y was found, -1 is returned
581  */
582 static
583 void implicsSearchVar(
584  SCIP_IMPLICS* implics, /**< implications data structure */
585  SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */
586  SCIP_VAR* implvar, /**< variable y to search for */
587  int* poslower, /**< pointer to store position of y_lower (-1 if not found) */
588  int* posupper, /**< pointer to store position of y_upper (-1 if not found) */
589  int* posadd /**< pointer to store position of first y entry, or where a new y entry
590  * should be placed */
591  )
592 {
593  SCIP_Bool found;
594  int left;
595  int right;
596  int pos;
597 
598  assert(implics != NULL);
599  assert(poslower != NULL);
600  assert(posupper != NULL);
601  assert(posadd != NULL);
602 
603  /* set left and right pointer */
604  if( SCIPvarGetType(implvar) == SCIP_VARTYPE_BINARY )
605  {
606  /* check whether there are implications with binary variable y */
607  if( implics->nbinimpls[varfixing] == 0 )
608  {
609  /* there are no implications with binary variable y */
610  *posadd = 0;
611  *poslower = -1;
612  *posupper = -1;
613  return;
614  }
615  left = 0;
616  right = implics->nbinimpls[varfixing] - 1;
617  }
618  else
619  {
620  /* check whether there are implications with non-binary variable y */
621  if( implics->nimpls[varfixing] == implics->nbinimpls[varfixing] )
622  {
623  /* there are no implications with non-binary variable y */
624  *posadd = implics->nbinimpls[varfixing];
625  *poslower = -1;
626  *posupper = -1;
627  return;
628  }
629  left = implics->nbinimpls[varfixing];
630  right = implics->nimpls[varfixing] - 1;
631  }
632  assert(left <= right);
633 
634  /* search for the position in the sorted array (via binary search) */
635  found = SCIPsortedvecFindPtr((void**)(&(implics->vars[varfixing][left])), SCIPvarComp, (void*)implvar, right-left+1, &pos);
636 
637  /* adjust position */
638  pos += left;
639 
640  if( !found )
641  {
642  /* y was not found */
643  assert(pos >= right || compVars((void*)implics->vars[varfixing][pos], (void*)implvar) > 0);
644  assert(pos == left || compVars((void*)implics->vars[varfixing][pos-1], (void*)implvar) < 0);
645  *poslower = -1;
646  *posupper = -1;
647  *posadd = pos;
648  }
649  else
650  {
651  /* y was found */
652  assert(implvar == implics->vars[varfixing][pos]);
653 
654  /* set poslower and posupper */
655  if( implics->types[varfixing][pos] == SCIP_BOUNDTYPE_LOWER )
656  {
657  /* y was found as y_lower (on position middle) */
658  *poslower = pos;
659  if( pos + 1 < implics->nimpls[varfixing] && implics->vars[varfixing][pos+1] == implvar )
660  {
661  assert(implics->types[varfixing][pos+1] == SCIP_BOUNDTYPE_UPPER);
662  *posupper = pos + 1;
663  }
664  else
665  *posupper = -1;
666  *posadd = pos;
667  }
668  else
669  {
670  /* y was found as y_upper (on position pos) */
671  *posupper = pos;
672  if( pos - 1 >= 0 && implics->vars[varfixing][pos-1] == implvar )
673  {
674  assert(implics->types[varfixing][pos-1] == SCIP_BOUNDTYPE_LOWER);
675  *poslower = pos - 1;
676  *posadd = pos - 1;
677  }
678  else
679  {
680  *poslower = -1;
681  *posadd = pos;
682  }
683  }
684  }
685 }
686 
687 /** returns whether variable y is already contained in implications for x == 0 or x == 1 with the given impltype
688  * y can be contained in structure with y >= b (y_lower) and y <= b (y_upper)
689  */
690 static
691 SCIP_Bool implicsSearchImplic(
692  SCIP_IMPLICS* implics, /**< implications data structure */
693  SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */
694  SCIP_VAR* implvar, /**< variable y to search for */
695  SCIP_BOUNDTYPE impltype, /**< type of implication y <=/>= b to search for */
696  int* poslower, /**< pointer to store position of y_lower (inf if not found) */
697  int* posupper, /**< pointer to store position of y_upper (inf if not found) */
698  int* posadd /**< pointer to store correct position (with respect to impltype) to add y */
699  )
700 {
701  assert(implics != NULL);
702  assert(poslower != NULL);
703  assert(posupper != NULL);
704  assert(posadd != NULL);
705 
706  implicsSearchVar(implics, varfixing, implvar, poslower, posupper, posadd);
707  assert(*poslower == -1 || *posupper == -1 || *posupper == (*poslower)+1);
708  assert(*poslower == -1 || *posadd == *poslower);
709  assert(*poslower >= 0 || *posupper == -1 || *posadd == *posupper);
710  assert(0 <= *posadd && *posadd <= implics->nimpls[varfixing]);
711 
712  if( impltype == SCIP_BOUNDTYPE_LOWER )
713  return (*poslower >= 0);
714  else
715  {
716  if( *poslower >= 0 )
717  {
718  assert(*posadd == *poslower);
719  (*posadd)++;
720  }
721  return (*posupper >= 0);
722  }
723 }
724 
725 /** adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure;
726  * the implication must be non-redundant
727  */
728 SCIP_RETCODE SCIPimplicsAdd(
729  SCIP_IMPLICS** implics, /**< pointer to implications data structure */
730  BMS_BLKMEM* blkmem, /**< block memory */
731  SCIP_SET* set, /**< global SCIP settings */
732  SCIP_STAT* stat, /**< problem statistics */
733  SCIP_Bool varfixing, /**< FALSE if implication for x == 0 has to be added, TRUE for x == 1 */
734  SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
735  SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
736  SCIP_Real implbound, /**< bound b in implication y <= b or y >= b */
737  SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */
738  SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */
739  SCIP_Bool* added /**< pointer to store whether the implication was added */
740  )
741 {
742  int poslower;
743  int posupper;
744  int posadd;
745  SCIP_Bool found;
746 #ifndef NDEBUG
747  int k;
748 #endif
749 
750  assert(implics != NULL);
751  assert(*implics == NULL || (*implics)->nbinimpls[varfixing] <= (*implics)->nimpls[varfixing]);
752  assert(stat != NULL);
753  assert(SCIPvarIsActive(implvar));
754  assert(SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_LOOSE);
755  assert((impltype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, implbound, SCIPvarGetLbGlobal(implvar)))
756  || (impltype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, implbound, SCIPvarGetUbGlobal(implvar))));
757  assert(conflict != NULL);
758  assert(added != NULL);
759 
760  SCIPdebugMessage("adding implication to implics %p [%u]: <%s> %s %g\n",
761  (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbound);
762 
763  checkImplics(*implics, set);
764 
765  *conflict = FALSE;
766  *added = FALSE;
767 
768  /* check if variable is already contained in implications data structure */
769  if( *implics != NULL )
770  {
771  found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
772  assert(-1 <= poslower && poslower < (*implics)->nimpls[varfixing]);
773  assert(-1 <= posupper && posupper < (*implics)->nimpls[varfixing]);
774  assert(0 <= posadd && posadd <= (*implics)->nimpls[varfixing]);
775  assert(poslower == -1 || (*implics)->types[varfixing][poslower] == SCIP_BOUNDTYPE_LOWER);
776  assert(posupper == -1 || (*implics)->types[varfixing][posupper] == SCIP_BOUNDTYPE_UPPER);
777  }
778  else
779  {
780  found = FALSE;
781  poslower = -1;
782  posupper = -1;
783  posadd = 0;
784  }
785 
786  if( impltype == SCIP_BOUNDTYPE_LOWER )
787  {
788  assert(found == (poslower >= 0));
789 
790  /* check if y >= b is redundant */
791  if( poslower >= 0 && SCIPsetIsFeasLE(set, implbound, (*implics)->bounds[varfixing][poslower]) )
792  {
793  SCIPdebugMessage(" -> implication is redundant to <%s> >= %g\n",
794  SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
795  return SCIP_OKAY;
796  }
797 
798  /* check if y >= b causes conflict for x (i.e. y <= a (with a < b) is also valid) */
799  if( posupper >= 0 && SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][posupper]) )
800  {
801  SCIPdebugMessage(" -> implication is conflicting to <%s> <= %g\n",
802  SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
803  *conflict = TRUE;
804  return SCIP_OKAY;
805  }
806 
807  *added = TRUE;
808 
809  /* check if entry of the same type already exists */
810  if( found )
811  {
812  assert(poslower >= 0);
813  assert(posadd == poslower);
814 
815  /* add y >= b by changing old entry on poslower */
816  assert((*implics)->vars[varfixing][poslower] == implvar);
817  assert(SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][poslower]));
818  (*implics)->bounds[varfixing][poslower] = implbound;
819  }
820  else
821  {
822  assert(poslower == -1);
823 
824  /* add y >= b by creating a new entry on posadd */
825  SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing,
826  *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) );
827  assert(*implics != NULL);
828 
829  if( (*implics)->nimpls[varfixing] - posadd > 0 )
830  {
831  int amount = ((*implics)->nimpls[varfixing] - posadd);
832 
833 #ifndef NDEBUG
834  for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- )
835  {
836  assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0);
837  }
838 #endif
839  BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
840  BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
841  BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
842  BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
843  }
844 
845  (*implics)->vars[varfixing][posadd] = implvar;
846  (*implics)->types[varfixing][posadd] = impltype;
847  (*implics)->bounds[varfixing][posadd] = implbound;
848  (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications);
849  if( SCIPvarGetType(implvar) == SCIP_VARTYPE_BINARY )
850  (*implics)->nbinimpls[varfixing]++;
851  (*implics)->nimpls[varfixing]++;
852 #ifndef NDEBUG
853  for( k = posadd-1; k >= 0; k-- )
854  assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0);
855 #endif
856  stat->nimplications++;
857  }
858  }
859  else
860  {
861  assert(found == (posupper >= 0));
862 
863  /* check if y <= b is redundant */
864  if( posupper >= 0 && SCIPsetIsFeasGE(set, implbound, (*implics)->bounds[varfixing][posupper]) )
865  {
866  SCIPdebugMessage(" -> implication is redundant to <%s> <= %g\n",
867  SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
868  return SCIP_OKAY;
869  }
870 
871  /* check if y <= b causes conflict for x (i.e. y >= a (with a > b) is also valid) */
872  if( poslower >= 0 && SCIPsetIsFeasLT(set, implbound, (*implics)->bounds[varfixing][poslower]) )
873  {
874  SCIPdebugMessage(" -> implication is conflicting to <%s> >= %g\n",
875  SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
876  *conflict = TRUE;
877  return SCIP_OKAY;
878  }
879 
880  *added = TRUE;
881 
882  /* check if entry of the same type already exists */
883  if( found )
884  {
885  assert(posupper >= 0);
886  assert(posadd == posupper);
887 
888  /* add y <= b by changing old entry on posupper */
889  assert((*implics)->vars[varfixing][posupper] == implvar);
890  assert(SCIPsetIsFeasLT(set, implbound,(*implics)->bounds[varfixing][posupper]));
891  (*implics)->bounds[varfixing][posupper] = implbound;
892  }
893  else
894  {
895  /* add y <= b by creating a new entry on posadd */
896  assert(posupper == -1);
897 
898  SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing,
899  *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) );
900  assert(*implics != NULL);
901 
902  if( (*implics)->nimpls[varfixing] - posadd > 0 )
903  {
904  int amount = ((*implics)->nimpls[varfixing] - posadd);
905 
906 #ifndef NDEBUG
907  for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- )
908  {
909  assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0);
910  }
911 #endif
912  BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
913  BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
914  BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
915  BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
916  }
917 
918  (*implics)->vars[varfixing][posadd] = implvar;
919  (*implics)->types[varfixing][posadd] = impltype;
920  (*implics)->bounds[varfixing][posadd] = implbound;
921  (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications);
922  if( SCIPvarGetType(implvar) == SCIP_VARTYPE_BINARY )
923  (*implics)->nbinimpls[varfixing]++;
924  (*implics)->nimpls[varfixing]++;
925 #ifndef NDEBUG
926  for( k = posadd-1; k >= 0; k-- )
927  assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0);
928 #endif
929  stat->nimplications++;
930  }
931  }
932 
933  checkImplics(*implics, set);
934 
935  return SCIP_OKAY;
936 }
937 
938 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */
939 SCIP_RETCODE SCIPimplicsDel(
940  SCIP_IMPLICS** implics, /**< pointer to implications data structure */
941  BMS_BLKMEM* blkmem, /**< block memory */
942  SCIP_SET* set, /**< global SCIP settings */
943  SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */
944  SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
945  SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
946  )
947 {
948  int poslower;
949  int posupper;
950  int posadd;
951  SCIP_Bool found;
952 
953  assert(implics != NULL);
954  assert(*implics != NULL);
955  assert(implvar != NULL);
956 
957  SCIPdebugMessage("deleting implication from implics %p [%u]: <%s> %s x\n",
958  (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=");
959 
960  checkImplics(*implics, set);
961 
962  /* searches for y in implications of x */
963  found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
964  if( !found )
965  {
966  SCIPdebugMessage(" -> implication was not found\n");
967  return SCIP_OKAY;
968  }
969 
970  assert((impltype == SCIP_BOUNDTYPE_LOWER && poslower >= 0 && posadd == poslower)
971  || (impltype == SCIP_BOUNDTYPE_UPPER && posupper >= 0 && posadd == posupper));
972  assert(0 <= posadd && posadd < (*implics)->nimpls[varfixing]);
973  assert((SCIPvarGetType(implvar) == SCIP_VARTYPE_BINARY) == (posadd < (*implics)->nbinimpls[varfixing]));
974  assert((*implics)->vars[varfixing][posadd] == implvar);
975  assert((*implics)->types[varfixing][posadd] == impltype);
976 
977  /* removes y from implications of x */
978  if( (*implics)->nimpls[varfixing] - posadd > 1 )
979  {
980  int amount = ((*implics)->nimpls[varfixing] - posadd - 1);
981 
982  BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd]), &((*implics)->types[varfixing][posadd+1]), amount); /*lint !e866*/
983  BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd]), &((*implics)->vars[varfixing][posadd+1]), amount); /*lint !e866*/
984  BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd]), &((*implics)->bounds[varfixing][posadd+1]), amount); /*lint !e866*/
985  }
986  (*implics)->nimpls[varfixing]--;
987 
988  if( SCIPvarGetType(implvar) == SCIP_VARTYPE_BINARY )
989  {
990  assert(posadd < (*implics)->nbinimpls[varfixing]);
991  (*implics)->nbinimpls[varfixing]--;
992  }
993 
994  /* free implics data structure, if it is empty */
995  if( (*implics)->nimpls[0] == 0 && (*implics)->nimpls[1] == 0 )
996  SCIPimplicsFree(implics, blkmem);
997 
998  checkImplics(*implics, set);
999 
1000  return SCIP_OKAY;
1001 }
1002 
1003 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
1004 void SCIPimplicsGetVarImplics(
1005  SCIP_IMPLICS* implics, /**< implications data structure */
1006  SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
1007  SCIP_VAR* implvar, /**< variable y to search for */
1008  SCIP_Bool* haslowerimplic, /**< pointer to store whether there exists an implication y >= l */
1009  SCIP_Bool* hasupperimplic /**< pointer to store whether there exists an implication y <= u */
1010  )
1011 {
1012  int poslower;
1013  int posupper;
1014  int posadd;
1015 
1016  assert(haslowerimplic != NULL);
1017  assert(hasupperimplic != NULL);
1018 
1019  implicsSearchVar(implics, varfixing, implvar, &poslower, &posupper, &posadd);
1020 
1021  *haslowerimplic = (poslower >= 0);
1022  *hasupperimplic = (posupper >= 0);
1023 }
1024 
1025 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */
1026 SCIP_Bool SCIPimplicsContainsImpl(
1027  SCIP_IMPLICS* implics, /**< implications data structure */
1028  SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
1029  SCIP_VAR* implvar, /**< variable y to search for */
1030  SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */
1031  )
1032 {
1033  int poslower;
1034  int posupper;
1035  int posadd;
1036 
1037  return implicsSearchImplic(implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
1038 }
1039 
1040 
1041 
1042 
1043 /*
1044  * methods for cliques
1045  */
1046 
1047 #if 0
1048 /** creates a clique data structure */
1049 static
1050 SCIP_RETCODE cliqueCreate(
1051  SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
1052  BMS_BLKMEM* blkmem, /**< block memory */
1053  int size, /**< initial size of clique */
1054  int id /**< unique identifier of the clique */
1055  )
1056 {
1057  assert(clique != NULL);
1058 
1059  SCIP_ALLOC( BMSallocBlockMemory(blkmem, clique) );
1060  if( size > 0 )
1061  {
1062  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*clique)->vars, size) );
1063  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*clique)->values, size) );
1064  }
1065  else
1066  {
1067  (*clique)->vars = NULL;
1068  (*clique)->values = NULL;
1069  }
1070  (*clique)->nvars = 0;
1071  (*clique)->size = size;
1072  (*clique)->id = (unsigned int)id;
1073  (*clique)->eventsissued = FALSE;
1074 
1075  return SCIP_OKAY;
1076 }
1077 #endif
1078 
1079 /** creates a clique data structure with already created variables and values arrays in the size of 'size' */
1080 static
1081 SCIP_RETCODE cliqueCreateWithData(
1082  SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
1083  BMS_BLKMEM* blkmem, /**< block memory */
1084  int size, /**< initial size of clique */
1085  SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given
1086  * value */
1087  SCIP_Bool* values, /**< values of the variables in the clique */
1088  int nvars, /**< number of variables in the clique */
1089  int id /**< unique identifier of the clique */
1090  )
1091 {
1092  assert(clique != NULL);
1093  assert(blkmem != NULL);
1094  assert(size >= nvars && nvars > 0);
1095  assert(vars != NULL);
1096  assert(values != NULL);
1097 
1098  SCIP_ALLOC( BMSallocBlockMemory(blkmem, clique) );
1099  (*clique)->vars = vars;
1100  (*clique)->values = values;
1101  (*clique)->nvars = nvars;
1102  (*clique)->size = size;
1103  (*clique)->id = (unsigned int)id;
1104  (*clique)->eventsissued = FALSE;
1105 
1106  return SCIP_OKAY;
1107 }
1108 
1109 /** frees a clique data structure */
1110 static
1111 void cliqueFree(
1112  SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
1113  BMS_BLKMEM* blkmem /**< block memory */
1114  )
1115 {
1116  assert(clique != NULL);
1117 
1118  if( *clique != NULL )
1119  {
1120  BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->vars, (*clique)->size);
1121  BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->values, (*clique)->size);
1122  BMSfreeBlockMemory(blkmem, clique);
1123  }
1124 }
1125 
1126 /** ensures, that clique arrays can store at least num entries */
1127 static
1128 SCIP_RETCODE cliqueEnsureSize(
1129  SCIP_CLIQUE* clique, /**< clique data structure */
1130  BMS_BLKMEM* blkmem, /**< block memory */
1131  SCIP_SET* set, /**< global SCIP settings */
1132  int num /**< minimum number of entries to store */
1133  )
1134 {
1135  assert(clique != NULL);
1136 
1137  if( num > clique->size )
1138  {
1139  int newsize;
1140 
1141  newsize = SCIPsetCalcMemGrowSize(set, num);
1142  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->vars, clique->size, newsize) );
1143  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->values, clique->size, newsize) );
1144  clique->size = newsize;
1145  }
1146  assert(num <= clique->size);
1147 
1148  return SCIP_OKAY;
1149 }
1150 
1151 /** returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member
1152  * of the clique
1153  */
1154 int SCIPcliqueSearchVar(
1155  SCIP_CLIQUE* clique, /**< clique data structure */
1156  SCIP_VAR* var, /**< variable to search for */
1157  SCIP_Bool value /**< value of the variable in the clique */
1158  )
1159 {
1160  int varidx;
1161  int left;
1162  int right;
1163 
1164  assert(clique != NULL);
1165 
1166  varidx = SCIPvarGetIndex(var);
1167  left = -1;
1168  right = clique->nvars;
1169  while( left < right-1 )
1170  {
1171  int middle;
1172  int idx;
1173 
1174  middle = (left+right)/2;
1175  idx = SCIPvarGetIndex(clique->vars[middle]);
1176  assert(idx >= 0);
1177  if( varidx < idx )
1178  right = middle;
1179  else if( varidx > idx )
1180  left = middle;
1181  else
1182  {
1183  assert(var == clique->vars[middle]);
1184 
1185  /* now watch out for the correct value */
1186  if( clique->values[middle] < value )
1187  {
1188  int i;
1189  for( i = middle+1; i < clique->nvars && clique->vars[i] == var; ++i )
1190  {
1191  if( clique->values[i] == value )
1192  return i;
1193  }
1194  return -1;
1195  }
1196  if( clique->values[middle] > value )
1197  {
1198  int i;
1199  for( i = middle-1; i >= 0 && clique->vars[i] == var; --i )
1200  {
1201  if( clique->values[i] == value )
1202  return i;
1203  }
1204  return -1;
1205  }
1206  return middle;
1207  }
1208  }
1209 
1210  return -1;
1211 }
1212 
1213 /** returns whether the given variable/value pair is member of the given clique */
1214 SCIP_Bool SCIPcliqueHasVar(
1215  SCIP_CLIQUE* clique, /**< clique data structure */
1216  SCIP_VAR* var, /**< variable to remove from the clique */
1217  SCIP_Bool value /**< value of the variable in the clique */
1218  )
1219 {
1220  return (SCIPcliqueSearchVar(clique, var, value) >= 0);
1221 }
1222 
1223 /** adds a single variable to the given clique */
1224 SCIP_RETCODE SCIPcliqueAddVar(
1225  SCIP_CLIQUE* clique, /**< clique data structure */
1226  BMS_BLKMEM* blkmem, /**< block memory */
1227  SCIP_SET* set, /**< global SCIP settings */
1228  SCIP_VAR* var, /**< variable to add to the clique */
1229  SCIP_Bool value, /**< value of the variable in the clique */
1230  SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */
1231  SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */
1232  )
1233 {
1234  int pos;
1235  int i;
1236 
1237  assert(clique != NULL);
1238  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
1239  assert(SCIPvarIsBinary(var));
1240  assert(doubleentry != NULL);
1241  assert(oppositeentry != NULL);
1242 
1243  SCIPdebugMessage("adding variable <%s> == %u to clique %u\n", SCIPvarGetName(var), value, clique->id);
1244 
1245  *doubleentry = FALSE;
1246  *oppositeentry = FALSE;
1247 
1248  /* allocate memory */
1249  SCIP_CALL( cliqueEnsureSize(clique, blkmem, set, clique->nvars+1) );
1250 
1251  /* search for insertion position by binary variable, note that first the entries are order after variable index and
1252  * second after the bool value of the corresponding variable
1253  */
1254  (void) SCIPsortedvecFindPtr((void**) clique->vars, SCIPvarComp, var, clique->nvars, &pos);
1255 
1256  assert(pos >= 0 && pos <= clique->nvars);
1257  /* remember insertion position for later, pos might change */
1258  i = pos;
1259 
1260  if( pos < clique->nvars )
1261  {
1262  const int amount = clique->nvars - pos;
1263 
1264  /* moving elements to correct position */
1265  BMSmoveMemoryArray(&(clique->vars[pos+1]), &(clique->vars[pos]), amount); /*lint !e866*/
1266  BMSmoveMemoryArray(&(clique->values[pos+1]), &(clique->values[pos]), amount); /*lint !e866*/
1267  clique->nvars++;
1268 
1269  /* insertion for a variable with cliquevalue FALSE */
1270  if( !value )
1271  {
1272  /* find last entry with the same variable and value behind the insertion position */
1273  for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] == value; ++pos ); /*lint !e722*/
1274 
1275  /* check if the same variable with other value also exists */
1276  if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1277  {
1278  assert(clique->values[pos + 1] != value);
1279  *oppositeentry = TRUE;
1280  }
1281 
1282  /* check if we found the same variable with the same value more than once */
1283  if( pos != i )
1284  *doubleentry = TRUE;
1285  else
1286  {
1287  /* find last entry with the same variable and different value before the insertion position */
1288  for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value; --pos ); /*lint !e722*/
1289 
1290  /* check if we found the same variable with the same value more than once */
1291  if( pos > 0 && clique->vars[pos - 1] == var )
1292  {
1293  assert(clique->values[pos - 1] == value);
1294 
1295  *doubleentry = TRUE;
1296  }
1297  /* if we found the same variable with different value, we need to order them correctly */
1298  if( pos != i )
1299  {
1300  assert(clique->vars[pos] == var);
1301  assert(clique->values[pos] != value);
1302 
1303  clique->values[pos] = value;
1304  value = !value;
1305  }
1306  }
1307  }
1308  /* insertion for a variable with cliquevalue TRUE */
1309  else
1310  {
1311  /* find last entry with the same variable and different value behind the insertion position */
1312  for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] != value; ++pos ); /*lint !e722*/
1313 
1314  /* check if the same variable with other value also exists */
1315  if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1316  {
1317  assert(clique->values[pos + 1] == value);
1318  *doubleentry = TRUE;
1319  }
1320 
1321  /* check if we found the same variable with different value */
1322  if( pos != i )
1323  {
1324  *oppositeentry = TRUE;
1325 
1326  /* if we found the same variable with different value, we need to order them correctly */
1327  assert(clique->vars[pos] == var);
1328  assert(clique->values[pos] != value);
1329 
1330  clique->values[pos] = value;
1331  value = !value;
1332  }
1333  else
1334  {
1335  /* find last entry with the same variable and value before the insertion position */
1336  for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] == value; --pos ); /*lint !e722*/
1337 
1338  if( pos != i )
1339  *doubleentry = TRUE;
1340 
1341  /* check if we found the same variable with different value up front */
1342  if( pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value )
1343  *oppositeentry = TRUE;
1344  }
1345  }
1346  }
1347  else
1348  clique->nvars++;
1349 
1350  clique->vars[i] = var;
1351  clique->values[i] = value;
1352  clique->eventsissued = FALSE;
1353 
1354  return SCIP_OKAY;
1355 }
1356 
1357 /** removes a single variable from the given clique */
1358 SCIP_RETCODE SCIPcliqueDelVar(
1359  SCIP_CLIQUE* clique, /**< clique data structure */
1360  SCIP_VAR* var, /**< variable to remove from the clique */
1361  SCIP_Bool value /**< value of the variable in the clique */
1362  )
1363 {
1364  int pos;
1365 
1366  assert(clique != NULL);
1367  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
1368  assert(SCIPvarIsBinary(var));
1369 
1370  SCIPdebugMessage("deleting variable <%s> == %u from clique %u\n", SCIPvarGetName(var), value, clique->id);
1371 
1372  /* find variable in clique */
1373  pos = SCIPcliqueSearchVar(clique, var, value);
1374  assert(0 <= pos && pos < clique->nvars);
1375  assert(clique->vars[pos] == var);
1376  assert(clique->values[pos] == value);
1377 
1378  /* remove entry from clique */
1379  for( ; pos < clique->nvars-1; ++pos )
1380  {
1381  clique->vars[pos] = clique->vars[pos+1];
1382  clique->values[pos] = clique->values[pos+1];
1383  }
1384  clique->nvars--;
1385 
1386  return SCIP_OKAY;
1387 }
1388 
1389 /** gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array */
1390 static
1391 int cliquesSearchClique(
1392  SCIP_CLIQUE** cliques, /**< array of cliques */
1393  int ncliques, /**< number of cliques in the cliques array */
1394  SCIP_CLIQUE* clique /**< clique to search for */
1395  )
1396 {
1397  unsigned int cliqueid;
1398  int left;
1399  int right;
1400 
1401  assert(cliques != NULL || ncliques == 0);
1402  assert(clique != NULL);
1403 
1404  cliqueid = clique->id; /*lint !e732*/
1405  left = -1;
1406  right = ncliques;
1407  while( left < right-1 )
1408  {
1409  unsigned int id;
1410  int middle;
1411 
1412  assert(cliques != NULL);
1413  middle = (left+right)/2;
1414  id = cliques[middle]->id; /*lint !e732*/
1415  if( cliqueid < id )
1416  right = middle;
1417  else if( cliqueid > id )
1418  left = middle;
1419  else
1420  {
1421  assert(clique == cliques[middle]);
1422  return middle;
1423  }
1424  }
1425 
1426  return -1;
1427 }
1428 
1429 #ifndef NDEBUG
1430 /** checks whether clique appears in all clique lists of the involved variables */
1431 static
1432 void cliqueCheck(
1433  SCIP_CLIQUE* clique /**< clique data structure */
1434  )
1435 {
1436  int i;
1437 
1438  assert(clique != NULL);
1439 
1440  for( i = 0; i < clique->nvars; ++i )
1441  {
1442  SCIP_CLIQUE** cliques;
1443  int ncliques;
1444  int pos;
1445 
1446  assert(i == 0 || SCIPvarGetIndex(clique->vars[i-1]) <= SCIPvarGetIndex(clique->vars[i]));
1447  assert(i == 0 || clique->vars[i-1] != clique->vars[i] || clique->values[i-1] <= clique->values[i]);
1448  ncliques = SCIPvarGetNCliques(clique->vars[i], clique->values[i]);
1449  cliques = SCIPvarGetCliques(clique->vars[i], clique->values[i]);
1450  pos = cliquesSearchClique(cliques, ncliques, clique);
1451  assert(0 <= pos && pos < ncliques);
1452  assert(cliques[pos] == clique);
1453  }
1454 }
1455 #else
1456 #define cliqueCheck(clique) /**/
1457 #endif
1458 
1459 /** creates a clique list data structure */
1460 static
1461 SCIP_RETCODE cliquelistCreate(
1462  SCIP_CLIQUELIST** cliquelist, /**< pointer to store clique list data structure */
1463  BMS_BLKMEM* blkmem /**< block memory */
1464  )
1465 {
1466  assert(cliquelist != NULL);
1467 
1468  SCIP_ALLOC( BMSallocBlockMemory(blkmem, cliquelist) );
1469  (*cliquelist)->cliques[0] = NULL;
1470  (*cliquelist)->cliques[1] = NULL;
1471  (*cliquelist)->ncliques[0] = 0;
1472  (*cliquelist)->ncliques[1] = 0;
1473  (*cliquelist)->size[0] = 0;
1474  (*cliquelist)->size[1] = 0;
1475 
1476  return SCIP_OKAY;
1477 }
1478 
1479 /** frees a clique list data structure */
1480 void SCIPcliquelistFree(
1481  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1482  BMS_BLKMEM* blkmem /**< block memory */
1483  )
1484 {
1485  assert(cliquelist != NULL);
1486 
1487  if( *cliquelist != NULL )
1488  {
1489  BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[0], (*cliquelist)->size[0]);
1490  BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[1], (*cliquelist)->size[1]);
1491  BMSfreeBlockMemory(blkmem, cliquelist);
1492  }
1493 }
1494 
1495 /** ensures, that clique list arrays can store at least num entries */
1496 static
1497 SCIP_RETCODE cliquelistEnsureSize(
1498  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1499  BMS_BLKMEM* blkmem, /**< block memory */
1500  SCIP_SET* set, /**< global SCIP settings */
1501  SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1502  int num /**< minimum number of entries to store */
1503  )
1504 {
1505  assert(cliquelist != NULL);
1506 
1507  if( num > cliquelist->size[value] )
1508  {
1509  int newsize;
1510 
1511  newsize = SCIPsetCalcMemGrowSize(set, num);
1512  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &cliquelist->cliques[value], cliquelist->size[value], newsize) ); /*lint !e866*/
1513  cliquelist->size[value] = newsize;
1514  }
1515  assert(num <= cliquelist->size[value]);
1516 
1517  return SCIP_OKAY;
1518 }
1519 
1520 /** adds a clique to the clique list */
1521 SCIP_RETCODE SCIPcliquelistAdd(
1522  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1523  BMS_BLKMEM* blkmem, /**< block memory */
1524  SCIP_SET* set, /**< global SCIP settings */
1525  SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1526  SCIP_CLIQUE* clique /**< clique that should be added to the clique list */
1527  )
1528 {
1529  unsigned int id;
1530  int i;
1531 
1532  assert(cliquelist != NULL);
1533 
1534  /* allocate memory */
1535  if( *cliquelist == NULL )
1536  {
1537  SCIP_CALL( cliquelistCreate(cliquelist, blkmem) );
1538  }
1539  assert(*cliquelist != NULL);
1540  SCIP_CALL( cliquelistEnsureSize(*cliquelist, blkmem, set, value, (*cliquelist)->ncliques[value]+1) );
1541  assert((*cliquelist)->cliques[value] != NULL);
1542 
1543  SCIPdebugMessage("adding clique %u to cliquelist %p value %u (length: %d)\n",
1544  clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1545 
1546  /* insert clique into list, sorted by clique id */
1547  id = clique->id; /*lint !e732*/
1548  for( i = (*cliquelist)->ncliques[value]; i > 0 && (*cliquelist)->cliques[value][i-1]->id > id; --i ) /*lint !e574*/
1549  (*cliquelist)->cliques[value][i] = (*cliquelist)->cliques[value][i-1];
1550  (*cliquelist)->cliques[value][i] = clique;
1551  (*cliquelist)->ncliques[value]++;
1552 
1553  return SCIP_OKAY;
1554 }
1555 
1556 /** removes a clique from the clique list */
1557 SCIP_RETCODE SCIPcliquelistDel(
1558  SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1559  BMS_BLKMEM* blkmem, /**< block memory */
1560  SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */
1561  SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */
1562  )
1563 {
1564  int pos;
1565 
1566  assert(cliquelist != NULL);
1567  assert(*cliquelist != NULL);
1568 
1569  SCIPdebugMessage("deleting clique %u from cliquelist %p value %u (length: %d)\n",
1570  clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1571 
1572  pos = cliquesSearchClique((*cliquelist)->cliques[value], (*cliquelist)->ncliques[value], clique);
1573  assert(0 <= pos && pos < (*cliquelist)->ncliques[value]);
1574  assert((*cliquelist)->cliques[value][pos] == clique);
1575 
1576  /* remove clique from list */
1577  (*cliquelist)->ncliques[value]--;
1578  if( pos < (*cliquelist)->ncliques[value] )
1579  {
1580  BMSmoveMemoryArray(&((*cliquelist)->cliques[value][pos]), &((*cliquelist)->cliques[value][pos+1]),
1581  (*cliquelist)->ncliques[value] - pos); /*lint !e866*/
1582  }
1583 
1584  /* free cliquelist if it is empty */
1585  if( (*cliquelist)->ncliques[0] == 0 && (*cliquelist)->ncliques[1] == 0 )
1586  SCIPcliquelistFree(cliquelist, blkmem);
1587 
1588  return SCIP_OKAY;
1589 }
1590 
1591 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears
1592  * in both lists
1593  */
1594 SCIP_Bool SCIPcliquelistsHaveCommonClique(
1595  SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */
1596  SCIP_Bool value1, /**< value of first variable */
1597  SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */
1598  SCIP_Bool value2 /**< value of second variable */
1599  )
1600 {
1601  SCIP_CLIQUE** cliques1;
1602  SCIP_CLIQUE** cliques2;
1603  int ncliques1;
1604  int ncliques2;
1605  int i1;
1606  int i2;
1607 
1608  if( cliquelist1 == NULL || cliquelist2 == NULL )
1609  return FALSE;
1610 
1611  ncliques1 = cliquelist1->ncliques[value1];
1612  cliques1 = cliquelist1->cliques[value1];
1613  ncliques2 = cliquelist2->ncliques[value2];
1614  cliques2 = cliquelist2->cliques[value2];
1615 
1616  i1 = 0;
1617  i2 = 0;
1618 
1619  if( i1 < ncliques1 && i2 < ncliques2 )
1620  {
1621  int cliqueid;
1622 
1623  /* make the bigger clique the first one */
1624  if( ncliques2 > ncliques1 )
1625  {
1626  SCIP_CLIQUE** tmpc;
1627  int tmpi;
1628 
1629  tmpc = cliques1;
1630  tmpi = ncliques1;
1631  cliques1 = cliques2;
1632  ncliques1 = ncliques2;
1633  cliques2 = tmpc;
1634  ncliques2 = tmpi;
1635  }
1636 
1637  /* check whether both clique lists have a same clique */
1638  while( TRUE ) /*lint !e716*/
1639  {
1640  cliqueid = SCIPcliqueGetId(cliques2[i2]);
1641 
1642  /* if last item in clique1 has a smaller index than the actual clique in clique2, than cause of increasing order
1643  * there will be no same item and we can stop */
1644  if( SCIPcliqueGetId(cliques1[ncliques1 - 1]) < cliqueid )
1645  break;
1646 
1647  while( SCIPcliqueGetId(cliques1[i1]) < cliqueid )
1648  {
1649  ++i1;
1650  assert(i1 < ncliques1);
1651  }
1652  cliqueid = SCIPcliqueGetId(cliques1[i1]);
1653 
1654  /* if last item in clique2 has a smaller index than the actual clique in clique1, than cause of increasing order
1655  * there will be no same item and we can stop */
1656  if( SCIPcliqueGetId(cliques2[ncliques2 - 1]) < cliqueid )
1657  break;
1658 
1659  while( SCIPcliqueGetId(cliques2[i2]) < cliqueid )
1660  {
1661  ++i2;
1662  assert(i2 < ncliques2);
1663  }
1664  if( SCIPcliqueGetId(cliques2[i2]) == cliqueid )
1665  return TRUE;
1666  }
1667  }
1668  return FALSE;
1669 }
1670 
1671 /** removes all listed entries from the cliques */
1672 void SCIPcliquelistRemoveFromCliques(
1673  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1674  SCIP_VAR* var /**< active problem variable the clique list belongs to */
1675  )
1676 {
1677  assert(SCIPvarIsBinary(var));
1678 
1679  if( cliquelist != NULL )
1680  {
1681  int value;
1682 
1683  SCIPdebugMessage("removing variable <%s> from cliques (%d with value 0, %d with value 1)\n",
1684  SCIPvarGetName(var), cliquelist->ncliques[0], cliquelist->ncliques[1]);
1685 
1686  for( value = 0; value < 2; ++value )
1687  {
1688  int i;
1689 
1690  assert(SCIPvarGetCliques(var, (SCIP_Bool)value) == cliquelist->cliques[value]);
1691  assert(SCIPvarGetNCliques(var, (SCIP_Bool)value) == cliquelist->ncliques[value]);
1692  for( i = 0; i < cliquelist->ncliques[value]; ++i )
1693  {
1694  SCIP_CLIQUE* clique;
1695  int pos;
1696 
1697  clique = cliquelist->cliques[value][i];
1698  assert(clique != NULL);
1699 
1700  SCIPdebugMessage(" -> removing variable <%s> == %d from clique %u (size %d)\n",
1701  SCIPvarGetName(var), value, clique->id, clique->nvars);
1702 
1703  /* binary search the position of the variable in the clique */
1704  pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value);
1705  assert(0 <= pos && pos < clique->nvars);
1706  assert(clique->vars[pos] == var);
1707  assert(clique->values[pos] == (SCIP_Bool)value);
1708 
1709  /* remove the entry from the clique */
1710  if( clique->nvars - pos - 1 > 0 )
1711  {
1712  BMSmoveMemoryArray(&(clique->vars[pos]), &(clique->vars[pos+1]), clique->nvars - pos - 1); /*lint !e866*/
1713  BMSmoveMemoryArray(&(clique->values[pos]), &(clique->values[pos+1]), clique->nvars - pos - 1); /*lint !e866*/
1714  }
1715  clique->nvars--;
1716 
1717  cliqueCheck(clique);
1718  }
1719  }
1720  }
1721 }
1722 
1723 /** creates a clique table data structure */
1724 SCIP_RETCODE SCIPcliquetableCreate(
1725  SCIP_CLIQUETABLE** cliquetable /**< pointer to store clique table data structure */
1726  )
1727 {
1728  assert(cliquetable != NULL);
1729 
1730  SCIP_ALLOC( BMSallocMemory(cliquetable) );
1731  (*cliquetable)->cliques = NULL;
1732  (*cliquetable)->ncliques = 0;
1733  (*cliquetable)->size = 0;
1734  (*cliquetable)->ncreatedcliques = 0;
1735  (*cliquetable)->ncleanupfixedvars = 0;
1736  (*cliquetable)->ncleanupaggrvars = 0;
1737  (*cliquetable)->ncleanupcliques = 0;
1738 
1739  return SCIP_OKAY;
1740 }
1741 
1742 /** frees a clique table data structure */
1743 SCIP_RETCODE SCIPcliquetableFree(
1744  SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1745  BMS_BLKMEM* blkmem /**< block memory */
1746  )
1747 {
1748  int i;
1749 
1750  assert(cliquetable != NULL);
1751  assert(*cliquetable != NULL);
1752 
1753  /* free all cliques */
1754  for( i = 0; i < (*cliquetable)->ncliques; ++i )
1755  {
1756  cliqueFree(&(*cliquetable)->cliques[i], blkmem);
1757  }
1758 
1759  /* free clique table data */
1760  BMSfreeMemoryArrayNull(&(*cliquetable)->cliques);
1761  BMSfreeMemory(cliquetable);
1762 
1763  return SCIP_OKAY;
1764 }
1765 
1766 /** ensures, that clique table arrays can store at least num entries */
1767 static
1768 SCIP_RETCODE cliquetableEnsureSize(
1769  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1770  SCIP_SET* set, /**< global SCIP settings */
1771  int num /**< minimum number of entries to store */
1772  )
1773 {
1774  assert(cliquetable != NULL);
1775 
1776  if( num > cliquetable->size )
1777  {
1778  int newsize;
1779 
1780  newsize = SCIPsetCalcMemGrowSize(set, num);
1781  SCIP_ALLOC( BMSreallocMemoryArray(&cliquetable->cliques, newsize) );
1782  cliquetable->size = newsize;
1783  }
1784  assert(num <= cliquetable->size);
1785 
1786  return SCIP_OKAY;
1787 }
1788 
1789 /** adds a clique to the clique table, using the given values for the given variables;
1790  * performs implications if the clique contains the same variable twice
1791  */
1792 SCIP_RETCODE SCIPcliquetableAdd(
1793  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1794  BMS_BLKMEM* blkmem, /**< block memory */
1795  SCIP_SET* set, /**< global SCIP settings */
1796  SCIP_STAT* stat, /**< problem statistics */
1797  SCIP_PROB* transprob, /**< transformed problem */
1798  SCIP_PROB* origprob, /**< original problem */
1799  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
1800  SCIP_LP* lp, /**< current LP data */
1801  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1802  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1803  SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
1804  SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
1805  int nvars, /**< number of variables in the clique */
1806  SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
1807  int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */
1808  )
1809 {
1810  SCIP_VAR** clqvars;
1811  SCIP_Bool* clqvalues;
1812  SCIP_CLIQUE* clique;
1813  SCIP_VAR* var;
1814  int size;
1815  int nlocalnbdchgs = 0;
1816  int v;
1817  int w;
1818 
1819  assert(cliquetable != NULL);
1820  assert(vars != NULL);
1821 
1822  SCIPdebugMessage("adding clique %d with %d vars to clique table\n", cliquetable->ncliques, nvars);
1823 
1824  /* check clique on debugging solution */
1825  SCIP_CALL( SCIPdebugCheckClique(set, vars, values, nvars) ); /*lint !e506 !e774*/
1826 
1827  *infeasible = FALSE;
1828  size = nvars;
1829 
1830  /* copy clique data */
1831  if( values == NULL )
1832  {
1833  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &clqvalues, size) );
1834 
1835  /* initialize clique values data */
1836  for( v = nvars - 1; v >= 0; --v )
1837  clqvalues[v] = TRUE;
1838  }
1839  else
1840  {
1841  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvalues, values, size) );
1842  }
1843  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvars, vars, size) );
1844 
1845  /* get active variables */
1846  SCIP_CALL( SCIPvarsGetProbvarBinary(&clqvars, &clqvalues, nvars) );
1847 
1848  /* remove all inactive vars */
1849  for( v = nvars - 1; v >= 0; --v )
1850  {
1851  var = clqvars[v];
1852 
1853  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
1854  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
1855  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
1856  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
1857  assert(SCIPvarIsBinary(var));
1858 
1859  /* if we have a variables already fixed to one in the clique, fix all other to zero */
1860  if( (clqvalues[v] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[v] && SCIPvarGetUbGlobal(var) < 0.5) )
1861  {
1862  for( w = nvars - 1; w >= 0; --w )
1863  {
1864  if( clqvars[w] != var )
1865  {
1866  SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, lp, branchcand,
1867  eventqueue, !clqvalues[w], infeasible, &nlocalnbdchgs) );
1868 
1869  if( *infeasible )
1870  break;
1871  }
1872  }
1873 
1874  /* all variables are fixed so we can stop */
1875  break;
1876  }
1877 
1878  /* only column and loose variables may be member of a clique */
1879  if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN && SCIPvarGetStatus(var) != SCIP_VARSTATUS_LOOSE )
1880  {
1881  --nvars;
1882  clqvars[v] = clqvars[nvars];
1883  clqvalues[v] = clqvalues[nvars];
1884  }
1885  }
1886 
1887  *nbdchgs += nlocalnbdchgs;
1888 
1889  /* did we fix all variables? */
1890  if( v >= 0 )
1891  {
1892  BMSfreeBlockMemoryArray(blkmem, &clqvars, size);
1893  BMSfreeBlockMemoryArray(blkmem, &clqvalues, size);
1894 
1895  return SCIP_OKAY;
1896  }
1897 
1898  nlocalnbdchgs = 0;
1899 
1900  /* sort variables and corresponding clique values after variables indices */
1901  SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, nvars);
1902 
1903  /* check for multiple occurences or pairs of negations in the variable array, this should be very rar when creating a
1904  * new clique, and therefore the sortation before removing them should be ok, otherwise we may need to remove these
1905  * variables before sorting
1906  */
1907  for( v = nvars - 1; v > 0; --v )
1908  {
1909  var = clqvars[v - 1];
1910 
1911  /* only column and loose variables can exist now */
1912  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
1913  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
1914  assert(SCIPvarIsBinary(var));
1915 
1916  /* do we have same variables at least twice? */
1917  if( clqvars[v] == var )
1918  {
1919  /* do we have a pair of negated variables? */
1920  if( clqvalues[v] != clqvalues[v - 1] )
1921  {
1922  /* a pair of negated variable in one clique forces all other variables in the clique to be zero */
1923 
1924  for( w = nvars - 1; w >= 0; --w )
1925  {
1926  if( clqvars[w] != var )
1927  {
1928  SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, lp, branchcand,
1929  eventqueue, !clqvalues[w], infeasible, &nlocalnbdchgs) );
1930 
1931  if( *infeasible )
1932  break;
1933  }
1934  }
1935 
1936  /* all variables are fixed so we can stop */
1937  break;
1938  }
1939  /* do we have the same variable with the same clique value twice? */
1940  else
1941  {
1942  /* a variable multiple times in one clique forces this variable to be zero */
1943 
1944  SCIP_CALL( SCIPvarFixBinary(var, blkmem, set, stat, transprob, origprob, tree, lp, branchcand, eventqueue,
1945  !clqvalues[v], infeasible, &nlocalnbdchgs) );
1946 
1947  if( *infeasible )
1948  break;
1949  }
1950  }
1951  }
1952 
1953  *nbdchgs += nlocalnbdchgs;
1954 
1955  /* did we stop early do to a pair of negated variables? */
1956  if( v > 0 )
1957  {
1958  BMSfreeBlockMemoryArray(blkmem, &clqvars, size);
1959  BMSfreeBlockMemoryArray(blkmem, &clqvalues, size);
1960 
1961  return SCIP_OKAY;
1962  }
1963  else if( nlocalnbdchgs > 0 )
1964  {
1965  /* infeasible should be handle before */
1966  assert(!*infeasible);
1967 
1968  /* we fixed a variable because it appears at least twice, now we need to remove the fixings */
1969  /* @note that if we are in probing or solving stage, the fixation on the variable might not be carried out yet,
1970  * because it was contradicting a local bound
1971  */
1972 
1973  /* remove all inactive variables */
1974  v = 0;
1975  w = 0;
1976  while( v < nvars )
1977  {
1978  var = clqvars[v];
1979 
1980  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
1981  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
1982  || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED);
1983 
1984  /* check that we have no variable fixed to one in the clique, these should already be handle before that */
1985  assert(clqvalues[v] ? SCIPvarGetLbGlobal(var) < 0.5 : SCIPvarGetUbGlobal(var) > 0.5);
1986 
1987  /* only remember active variables */
1988  if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
1989  {
1990  /* we need to remove all fixed variables */
1991  if( v > w )
1992  {
1993  clqvars[w] = clqvars[v];
1994  clqvalues[w] = clqvalues[v];
1995  }
1996 
1997  ++w;
1998  }
1999  ++v;
2000  }
2001 
2002  nvars = w;
2003  }
2004 
2005  /* if less than two variables are left over, the clique is redundant */
2006  if( nvars > 1 )
2007  {
2008  /* create the clique data structure */
2009  SCIP_CALL( cliqueCreateWithData(&clique, blkmem, size, clqvars, clqvalues, nvars, cliquetable->ncreatedcliques) );
2010  cliquetable->ncreatedcliques++;
2011 
2012  /* add clique to clique table */
2013  SCIP_CALL( cliquetableEnsureSize(cliquetable, set, cliquetable->ncliques+1) );
2014  cliquetable->cliques[cliquetable->ncliques] = clique;
2015  cliquetable->ncliques++;
2016 
2017  /* add filled clique to the cliquelists of all corresponding variables */
2018  SCIP_CALL( SCIPvarsAddClique(clqvars, clqvalues, nvars, blkmem, set, clique) );
2019  }
2020  else
2021  {
2022  BMSfreeBlockMemoryArray(blkmem, &clqvars, size);
2023  BMSfreeBlockMemoryArray(blkmem, &clqvalues, size);
2024 
2025  return SCIP_OKAY;
2026  }
2027 #if 0 /* old variant */
2028  /* create the clique data structure */
2029  SCIP_CALL( cliqueCreate(&clique, blkmem, nvars, cliquetable->ncreatedcliques) );
2030  cliquetable->ncreatedcliques++;
2031 
2032  /* add clique to clique table */
2033  SCIP_CALL( cliquetableEnsureSize(cliquetable, set, cliquetable->ncliques+1) );
2034  cliquetable->cliques[cliquetable->ncliques] = clique;
2035  cliquetable->ncliques++;
2036 
2037  /* check clique on debugging solution */
2038  SCIP_CALL( SCIPdebugCheckClique(set, vars, values, nvars) ); /*lint !e506 !e774*/
2039 
2040  /* add the corresponding active problem variables to the clique */
2041  for( i = 0; i < nvars; ++i )
2042  {
2043  /* put the clique into the sorted clique table of the variable */
2044  SCIP_CALL( SCIPvarAddClique(vars[i], blkmem, set, stat, transprob, origprob, tree, lp, branchcand, eventqueue,
2045  values != NULL ? values[i] : TRUE, clique, infeasible, nbdchgs) );
2046  }
2047 #endif
2048  cliqueCheck(clique);
2049 
2050  return SCIP_OKAY;
2051 }
2052 
2053 /** gets the key of the given element */
2054 static
2055 SCIP_DECL_HASHGETKEY(hashgetkeyClique)
2056 { /*lint --e{715}*/
2057  return elem;
2058 }
2059 
2060 /** returns TRUE iff both keys are equal */
2061 static
2062 SCIP_DECL_HASHKEYEQ(hashkeyeqClique)
2063 { /*lint --e{715}*/
2064  SCIP_CLIQUE* clique1;
2065  SCIP_CLIQUE* clique2;
2066  int i;
2067 
2068  clique1 = (SCIP_CLIQUE*)key1;
2069  clique2 = (SCIP_CLIQUE*)key2;
2070  assert(clique1 != NULL);
2071  assert(clique2 != NULL);
2072 
2073  if( clique1->nvars != clique2->nvars )
2074  return FALSE;
2075 
2076  /* the variables are sorted: we can simply check the equality of each pair of variable/values */
2077  for( i = 0; i < clique1->nvars; ++i )
2078  {
2079  if( clique1->vars[i] != clique2->vars[i] || clique1->values[i] != clique2->values[i] )
2080  return FALSE;
2081  }
2082 
2083  return TRUE;
2084 }
2085 
2086 /** returns the hash value of the key */
2087 static
2088 SCIP_DECL_HASHKEYVAL(hashkeyvalClique)
2089 { /*lint --e{715}*/
2090  SCIP_CLIQUE* clique;
2091  unsigned int hashval;
2092  int i;
2093 
2094  clique = (SCIP_CLIQUE*)key;
2095  hashval = 0;
2096  for( i = 0; i < clique->nvars; ++i )
2097  {
2098  hashval *= 31;
2099  hashval += (unsigned int)(((size_t)clique->vars[i]) >> 1) + (unsigned int)clique->values[i];
2100  }
2101 
2102  return hashval;
2103 }
2104 
2105 /** removes all empty and single variable cliques from the clique table, and converts all two variable cliques
2106  * into implications; removes double entries from the clique table
2107  */
2108 SCIP_RETCODE SCIPcliquetableCleanup(
2109  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2110  BMS_BLKMEM* blkmem, /**< block memory */
2111  SCIP_SET* set, /**< global SCIP settings */
2112  SCIP_STAT* stat, /**< problem statistics */
2113  SCIP_PROB* transprob, /**< transformed problem */
2114  SCIP_PROB* origprob, /**< original problem */
2115  SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2116  SCIP_LP* lp, /**< current LP data */
2117  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2118  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2119  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2120  )
2121 {
2122  SCIP_HASHTABLE* hashtable;
2123  int hashtablesize;
2124  int i;
2125 
2126  assert(cliquetable != NULL);
2127  assert(stat != NULL);
2128  assert(infeasible != NULL);
2129 
2130  *infeasible = FALSE;
2131 
2132  /* check if we have anything to do */
2133  if( stat->npresolfixedvars == cliquetable->ncleanupfixedvars
2134  && stat->npresolaggrvars == cliquetable->ncleanupaggrvars
2135  && cliquetable->ncliques == cliquetable->ncleanupcliques )
2136  return SCIP_OKAY;
2137 
2138  /* delay events */
2139  SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
2140 
2141  /* create hash table to test for multiple cliques */
2142  hashtablesize = SCIPcalcHashtableSize(10*cliquetable->ncliques);
2143  hashtablesize = MAX(hashtablesize, (set->misc_usesmalltables ? SCIP_HASHSIZE_CLIQUES_SMALL : SCIP_HASHSIZE_CLIQUES));
2144  SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
2145  hashgetkeyClique, hashkeyeqClique, hashkeyvalClique, NULL) );
2146 
2147  i = cliquetable->ncliques - 1;
2148  while( i >= 0 && !(*infeasible) )
2149  {
2150  SCIP_CLIQUE* clique;
2151 
2152  clique = cliquetable->cliques[i];
2153  if( clique->nvars == 2 )
2154  {
2155  /* add the 2-clique as implication (don't use transitive closure; otherwise new cliques can be generated) */
2156  if( SCIPvarGetType(clique->vars[0]) == SCIP_VARTYPE_BINARY )
2157  {
2158  SCIP_CALL( SCIPvarAddImplic(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, lp, cliquetable,
2159  branchcand, eventqueue,
2160  clique->values[0], clique->vars[1], clique->values[1] ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER,
2161  (SCIP_Real)(!clique->values[1]), FALSE, infeasible, NULL) );
2162  }
2163  else if( SCIPvarGetType(clique->vars[1]) == SCIP_VARTYPE_BINARY )
2164  {
2165  SCIP_CALL( SCIPvarAddImplic(clique->vars[1], blkmem, set, stat, transprob, origprob, tree, lp, cliquetable,
2166  branchcand, eventqueue,
2167  clique->values[1], clique->vars[0], clique->values[0] ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER,
2168  (SCIP_Real)(!clique->values[0]), FALSE, infeasible, NULL) );
2169  }
2170  else
2171  {
2172  /* in case the variable are not of binary type we have to add the implication as variable bound */
2173 
2174  assert(SCIPvarGetType(clique->vars[0]) != SCIP_VARTYPE_BINARY && SCIPvarIsBinary(clique->vars[0]));
2175 
2176  /* add variable upper or rather variable lower bound on vars[0] */
2177  if( clique->values[0] )
2178  {
2179  SCIP_CALL( SCIPvarAddVub(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, lp, cliquetable, branchcand, eventqueue,
2180  clique->vars[1], clique->values[1] ? -1.0 : 1.0, clique->values[1] ? 1.0 : 0.0, FALSE, infeasible, NULL) );
2181  }
2182  else
2183  {
2184  SCIP_CALL( SCIPvarAddVlb(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, lp, cliquetable, branchcand, eventqueue,
2185  clique->vars[1], clique->values[1] ? 1.0 : -1.0, clique->values[1] ? 0.0 : 1.0, FALSE, infeasible, NULL) );
2186  }
2187  }
2188  }
2189 
2190  /* check if the clique is already contained in the clique table, or if it is redundant (too small) */
2191  if( clique->nvars <= 2 || SCIPhashtableExists(hashtable, (void*)clique) )
2192  {
2193  int j;
2194 
2195  /* delete the clique from the variables' clique lists */
2196  for( j = 0; j < clique->nvars; ++j )
2197  {
2198  SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[j], blkmem, clique->values[j], clique) );
2199  }
2200 
2201  /* free clique and remove it from clique table */
2202  cliqueFree(&cliquetable->cliques[i], blkmem);
2203  cliquetable->cliques[i] = cliquetable->cliques[cliquetable->ncliques-1];
2204  cliquetable->ncliques--;
2205  }
2206  else
2207  {
2208  SCIP_CALL( SCIPhashtableInsert(hashtable, (void*)clique) );
2209  if( !clique->eventsissued )
2210  {
2211  int j;
2212 
2213  /* issue IMPLADDED event on each variable in the clique */
2214  for( j = 0; j < clique->nvars; ++j )
2215  {
2216  SCIP_EVENT* event;
2217 
2218  SCIP_CALL( SCIPeventCreateImplAdded(&event, blkmem, clique->vars[j]) );
2219  SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
2220  }
2221  clique->eventsissued = TRUE;
2222  }
2223  }
2224  --i;
2225  }
2226 
2227  /* free hash table */
2228  SCIPhashtableFree(&hashtable);
2229 
2230  /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */
2231  cliquetable->ncleanupfixedvars = stat->npresolfixedvars;
2232  cliquetable->ncleanupaggrvars = stat->npresolaggrvars;
2233  cliquetable->ncleanupcliques = cliquetable->ncliques;
2234 
2235  /* process events */
2236  SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, NULL, lp, branchcand, NULL) );
2237 
2238  return SCIP_OKAY;
2239 }
2240 
2241 
2242 /*
2243  * simple functions implemented as defines
2244  */
2245 
2246 /* In debug mode, the following methods are implemented as function calls to ensure
2247  * type validity.
2248  * In optimized mode, the methods are implemented as defines to improve performance.
2249  * However, we want to have them in the library anyways, so we have to undef the defines.
2250  */
2251 
2252 #undef SCIPvboundsGetNVbds
2253 #undef SCIPvboundsGetVars
2254 #undef SCIPvboundsGetCoefs
2255 #undef SCIPvboundsGetConstants
2256 #undef SCIPimplicsGetNImpls
2257 #undef SCIPimplicsGetNBinImpls
2258 #undef SCIPimplicsGetVars
2259 #undef SCIPimplicsGetTypes
2260 #undef SCIPimplicsGetBounds
2261 #undef SCIPimplicsGetIds
2262 #undef SCIPcliqueGetNVars
2263 #undef SCIPcliqueGetVars
2264 #undef SCIPcliqueGetValues
2265 #undef SCIPcliqueGetId
2266 #undef SCIPcliquelistGetNCliques
2267 #undef SCIPcliquelistGetCliques
2268 #undef SCIPcliquelistCheck
2269 #undef SCIPcliquetableGetNCliques
2270 #undef SCIPcliquetableGetCliques
2271 
2272 /** gets number of variable bounds contained in given variable bounds data structure */
2273 int SCIPvboundsGetNVbds(
2274  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
2275  )
2276 {
2277  return vbounds != NULL ? vbounds->len : 0;
2278 }
2279 
2280 /** gets array of variables contained in given variable bounds data structure */
2281 SCIP_VAR** SCIPvboundsGetVars(
2282  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
2283  )
2284 {
2285  return vbounds != NULL ? vbounds->vars : NULL;
2286 }
2287 
2288 /** gets array of coefficients contained in given variable bounds data structure */
2289 SCIP_Real* SCIPvboundsGetCoefs(
2290  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
2291  )
2292 {
2293  return vbounds != NULL ? vbounds->coefs : NULL;
2294 }
2295 
2296 /** gets array of constants contained in given variable bounds data structure */
2297 SCIP_Real* SCIPvboundsGetConstants(
2298  SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
2299  )
2300 {
2301  return vbounds != NULL ? vbounds->constants : NULL;
2302 }
2303 
2304 /** gets number of implications for a given binary variable fixing */
2305 int SCIPimplicsGetNImpls(
2306  SCIP_IMPLICS* implics, /**< implication data */
2307  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
2308  )
2309 {
2310  return implics != NULL ? implics->nimpls[varfixing] : 0;
2311 }
2312 
2313 /** gets number of implications on binary variables for a given binary variable fixing */
2314 int SCIPimplicsGetNBinImpls(
2315  SCIP_IMPLICS* implics, /**< implication data */
2316  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
2317  )
2318 {
2319  return implics != NULL ? implics->nbinimpls[varfixing] : 0;
2320 }
2321 
2322 /** gets array with implied variables for a given binary variable fixing */
2323 SCIP_VAR** SCIPimplicsGetVars(
2324  SCIP_IMPLICS* implics, /**< implication data */
2325  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
2326  )
2327 {
2328  return implics != NULL ? implics->vars[varfixing] : NULL;
2329 }
2330 
2331 /** gets array with implication types for a given binary variable fixing */
2332 SCIP_BOUNDTYPE* SCIPimplicsGetTypes(
2333  SCIP_IMPLICS* implics, /**< implication data */
2334  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
2335  )
2336 {
2337  return implics != NULL ? implics->types[varfixing] : NULL;
2338 }
2339 
2340 /** gets array with implication bounds for a given binary variable fixing */
2341 SCIP_Real* SCIPimplicsGetBounds(
2342  SCIP_IMPLICS* implics, /**< implication data */
2343  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
2344  )
2345 {
2346  return implics != NULL ? implics->bounds[varfixing] : NULL;
2347 }
2348 
2349 /** Gets array with unique implication identifiers for a given binary variable fixing.
2350  * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
2351  * its id is negative, otherwise it is nonnegative.
2352  */
2353 int* SCIPimplicsGetIds(
2354  SCIP_IMPLICS* implics, /**< implication data */
2355  SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
2356  )
2357 {
2358  return implics != NULL ? implics->ids[varfixing] : NULL;
2359 }
2360 
2361 /** gets number of variables in the cliques */
2362 int SCIPcliqueGetNVars(
2363  SCIP_CLIQUE* clique /**< clique data structure */
2364  )
2365 {
2366  assert(clique != NULL);
2367 
2368  return clique->nvars;
2369 }
2370 
2371 /** gets array of active problem variables in the cliques */
2372 SCIP_VAR** SCIPcliqueGetVars(
2373  SCIP_CLIQUE* clique /**< clique data structure */
2374  )
2375 {
2376  assert(clique != NULL);
2377 
2378  return clique->vars;
2379 }
2380 
2381 /** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or
2382  * to TRUE in the clique
2383  */
2384 SCIP_Bool* SCIPcliqueGetValues(
2385  SCIP_CLIQUE* clique /**< clique data structure */
2386  )
2387 {
2388  assert(clique != NULL);
2389 
2390  return clique->values;
2391 }
2392 
2393 /** gets unique identifier of the clique */
2394 int SCIPcliqueGetId(
2395  SCIP_CLIQUE* clique /**< clique data structure */
2396  )
2397 {
2398  assert(clique != NULL);
2399 
2400  return (int) clique->id;
2401 }
2402 
2403 /** returns the number of cliques stored in the clique list */
2404 int SCIPcliquelistGetNCliques(
2405  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
2406  SCIP_Bool value /**< value of the variable for which the cliques should be returned */
2407  )
2408 {
2409  return cliquelist != NULL ? cliquelist->ncliques[value] : 0;
2410 }
2411 
2412 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */
2413 SCIP_CLIQUE** SCIPcliquelistGetCliques(
2414  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
2415  SCIP_Bool value /**< value of the variable for which the cliques should be returned */
2416  )
2417 {
2418  return cliquelist != NULL ? cliquelist->cliques[value] : NULL;
2419 }
2420 
2421 /** checks whether variable is contained in all cliques of the cliquelist */
2422 void SCIPcliquelistCheck(
2423  SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
2424  SCIP_VAR* var /**< variable, the clique list belongs to */
2425  )
2426 {
2427  /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MOREDEBUG because it can take at lot of time to check for
2428  * correctness
2429  */
2430 #ifndef NDEBUG
2431  int value;
2432 
2433  assert(SCIPvarGetNCliques(var, FALSE) == SCIPcliquelistGetNCliques(cliquelist, FALSE));
2434  assert(SCIPvarGetCliques(var, FALSE) == SCIPcliquelistGetCliques(cliquelist, FALSE));
2435  assert(SCIPvarGetNCliques(var, TRUE) == SCIPcliquelistGetNCliques(cliquelist, TRUE));
2436  assert(SCIPvarGetCliques(var, TRUE) == SCIPcliquelistGetCliques(cliquelist, TRUE));
2437 
2438  for( value = 0; value < 2; ++value )
2439  {
2440  SCIP_CLIQUE** cliques;
2441  int ncliques;
2442  int i;
2443 
2444  ncliques = SCIPcliquelistGetNCliques(cliquelist, (SCIP_Bool)value);
2445  cliques = SCIPcliquelistGetCliques(cliquelist, (SCIP_Bool)value);
2446  for( i = 0; i < ncliques; ++i )
2447  {
2448  SCIP_CLIQUE* clique;
2449  int pos;
2450 
2451  clique = cliques[i];
2452  assert(clique != NULL);
2453 
2454  pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value);
2455  assert(0 <= pos && pos < clique->nvars);
2456  assert(clique->vars[pos] == var);
2457  assert(clique->values[pos] == (SCIP_Bool)value);
2458  }
2459  }
2460 #endif
2461 }
2462 
2463 /** gets the number of cliques stored in the clique table */
2464 int SCIPcliquetableGetNCliques(
2465  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2466  )
2467 {
2468  assert(cliquetable != NULL);
2469 
2470  return cliquetable->ncliques;
2471 }
2472 
2473 /** gets the array of cliques stored in the clique table */
2474 SCIP_CLIQUE** SCIPcliquetableGetCliques(
2475  SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2476  )
2477 {
2478  assert(cliquetable != NULL);
2479 
2480  return cliquetable->cliques;
2481 }
2482