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
55   	SCIP_RETCODE vboundsCreate(
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 */
73   	void SCIPvboundsFree(
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
91   	SCIP_RETCODE vboundsEnsureSize(
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
125  	SCIP_RETCODE vboundsSearchPos(
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 */
206  	SCIP_RETCODE SCIPvboundsAdd(
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);
222  	   assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
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 */
288  	SCIP_RETCODE SCIPvboundsDel(
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 */
333  	void SCIPvboundsShrink(
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
359  	SCIP_DECL_SORTPTRCOMP(compVars)
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
383  	void checkImplics(
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
425  	SCIP_RETCODE implicsCreate(
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 */
451  	void SCIPimplicsFree(
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
474  	SCIP_RETCODE implicsEnsureSize(
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
512  	void implicsSearchVar(
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
596  	SCIP_Bool implicsSearchImplic(
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  	 */
633  	SCIP_RETCODE SCIPimplicsAdd(
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));
659  	   assert(SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_LOOSE); 
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 */
836  	SCIP_RETCODE SCIPimplicsDel(
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 */
894  	void SCIPimplicsGetVarImplics(
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 */
916  	void SCIPimplicsGetVarImplicPoss(
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 */
933  	SCIP_Bool SCIPimplicsContainsImpl(
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
956  	void cliquetableSwapCliques(
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
982  	void cliquetableMarkCliqueForCleanup(
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
1004 	SCIP_RETCODE cliqueCreateWithData(
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
1038 	void cliqueFree(
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
1055 	SCIP_RETCODE cliqueEnsureSize(
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 	 */
1081 	int SCIPcliqueSearchVar(
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 */
1141 	SCIP_Bool SCIPcliqueHasVar(
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 */
1151 	SCIP_RETCODE SCIPcliqueAddVar(
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);
1165 	   assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
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 */
1285 	void SCIPcliqueDelVar(
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
1333 	int cliquesSearchClique(
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
1422 	SCIP_RETCODE cliquelistCreate(
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 */
1441 	void SCIPcliquelistFree(
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
1458 	SCIP_RETCODE cliquelistEnsureSize(
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 */
1482 	SCIP_RETCODE SCIPcliquelistAdd(
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 */
1527 	SCIP_RETCODE SCIPcliquelistDel(
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 	 */
1605 	SCIP_Bool SCIPcliquelistsHaveCommonClique(
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 */
1683 	void SCIPcliquelistRemoveFromCliques(
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 */
1786 	SCIP_RETCODE SCIPcliquetableCreate(
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 */
1822 	SCIP_RETCODE SCIPcliquetableFree(
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
1859 	SCIP_RETCODE cliquetableEnsureSize(
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
1882 	SCIP_RETCODE sortAndMergeClique(
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 */
1941 	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
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 	
2125 	         assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
2126 	            || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
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
2261 	int cliquetableGetNodeIndexBinvar(
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
2304 	void cliquetableUpdateConnectednessClique(
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  */
2348 	int SCIPcliquetableGetVarComponentIdx(
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 	 */
2376 	SCIP_RETCODE SCIPcliquetableAdd(
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 	
2439 	      assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
2440 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
2441 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
2442 	         || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
2443 	      assert(SCIPvarIsBinary(var));
2444 	
2445 	      /* if we have a variables already fixed to one in the clique, fix all other to zero */
2446 	      if( ! SCIPvarIsMarkedDeleteGlobalStructures(var) &&
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 ||
2512 	            (SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN && SCIPvarGetStatus(var) != SCIP_VARSTATUS_LOOSE) ||
2513 	            SCIPvarIsMarkedDeleteGlobalStructures(var) )
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
2646 	SCIP_RETCODE cliqueCleanup(
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;
2688 	         if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_AGGREGATED
2689 	            || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED
2690 	            || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2691 	         {
2692 	            needsorting = TRUE;
2693 	            SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[v], blkmem, clique->values[v], clique) );
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) ||
2716 	               SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2717 	         {
2718 	            if( !addvartoclique )
2719 	               SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[v], blkmem, clique->values[v], clique) );
2720 	
2721 	            if( clique->equation && SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2722 	               clique->equation = FALSE;
2723 	
2724 	            /* the variable will be overwritten by subsequent active variables */
2725 	            continue;
2726 	         }
2727 	
2728 	         /* check for a variable fixed to one in the clique */
2729 	         else if( (clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5)
2730 	               || (!clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) )
2731 	         {
2732 	            if( onefixedvar != NULL )
2733 	            {
2734 	               *infeasible = TRUE;
2735 	
2736 	               SCIPsetDebugMsg(set, "two variables in clique %u fixed to one %s%s and %s%s\n", clique->id,
2737 	                     onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->values[v] ? "" : "~",
2738 	                           SCIPvarGetName(clique->vars[v])); /*lint !e530*/
2739 	               return SCIP_OKAY;
2740 	            }
2741 	            onefixedvar = clique->vars[v];
2742 	            onefixedvalue = clique->values[v];
2743 	         }
2744 	         else
2745 	         {
2746 	            assert(SCIPvarGetStatus(clique->vars[v]) != SCIP_VARSTATUS_FIXED);
2747 	            assert(w <= v);
2748 	
2749 	            if( w < v )
2750 	            {
2751 	               clique->vars[w] = clique->vars[v];
2752 	               clique->values[w] = clique->values[v];
2753 	            }
2754 	
2755 	            /* add clique to active variable if it replaced a aggregated or negated var */
2756 	            if( addvartoclique )
2757 	            {
2758 	               SCIP_CALL( SCIPvarAddCliqueToList(clique->vars[w], blkmem, set, clique->values[w], clique) );
2759 	            }
2760 	            /* increase indexer of last active, i.e. unfixed, variable in clique */
2761 	            ++w;
2762 	         }
2763 	      }
2764 	      clique->nvars = w;
2765 	
2766 	      if( onefixedvar != NULL )
2767 	      {
2768 	         SCIPsetDebugMsg(set, "variable %s%s in clique %u fixed to one, fixing all other variables to zero\n",
2769 	            onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->id);
2770 	
2771 	         for( v = 0; v < clique->nvars ; ++v )
2772 	         {
2773 	            SCIP_VAR* clqvar = clique->vars[v];
2774 	            SCIP_Bool clqval = clique->values[v];
2775 	
2776 	            assert(SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_COLUMN
2777 	               || SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_LOOSE);
2778 	
2779 	            if( onefixedvalue != clqval || clqvar != onefixedvar )
2780 	            {
2781 	               /* the variable could have been fixed already because it appears more than once in the clique */
2782 	               if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2783 	               {
2784 	                  /* the fixing must have occurred previously inside this loop. It may happen that
2785 	                   * the variable occurs together with its negation in that clique, which is usually
2786 	                   * handled during the merge step, but leads to a direct infeasibility because it
2787 	                   * contradicts any other variable fixed to one in this clique
2788 	                   */
2789 	                  if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2790 	                     || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2791 	                  {
2792 	                     /* impossible because we would have detected this in the previous cleanup loop */
2793 	                     assert(clqvar != onefixedvar);
2794 	                     *infeasible = TRUE;
2795 	
2796 	                     return SCIP_OKAY;
2797 	                  }
2798 	                  continue;
2799 	               }
2800 	
2801 	               SCIP_CALL( SCIPvarDelCliqueFromList(clqvar, blkmem, clqval, clique) );
2802 	
2803 	/* the following piece of code is wrong at this point because it assumes sorted variables. can be enabled if sorting
2804 	 * of variables is performed earlier than it is now
2805 	 */
2806 	#ifdef SCIP_DISABLED_CODE
2807 	               /* if one of the other variables occurs multiple times, we can
2808 	                * 1) deduce infeasibility if it occurs with different values
2809 	                * 2) wait for the last occurence to fix it
2810 	                */
2811 	               while( v < clique->nvars - 1 && clique->vars[v + 1] == clqvar )
2812 	               {
2813 	                  if( clique->values[v + 1] != clique->values[v] )
2814 	                  {
2815 	                     *infeasible = TRUE;
2816 	                     return SCIP_OKAY;
2817 	                  }
2818 	                  ++v;
2819 	               }
2820 	#endif
2821 	               SCIPsetDebugMsg(set, "fixing variable %s in clique %u to %d\n", SCIPvarGetName(clqvar), clique->id, clqval ? 0 : 1);
2822 	
2823 	               SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2824 	                     eventqueue, cliquetable, !clqval, infeasible, nchgbds) );
2825 	
2826 	               if( *infeasible )
2827 	                  return SCIP_OKAY;
2828 	            }
2829 	         }
2830 	
2831 	         if( SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_COLUMN /*lint !e850*/
2832 	            || SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_LOOSE )
2833 	         {
2834 	            SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2835 	         }
2836 	
2837 	         clique->nvars = 0;
2838 	         clique->equation = FALSE;
2839 	         clique->startcleanup = -1;
2840 	
2841 	         return SCIP_OKAY;
2842 	      }
2843 	
2844 	      if( clique->equation )
2845 	      {
2846 	         if( clique->nvars == 0 )
2847 	         {
2848 	            *infeasible = TRUE;
2849 	            return SCIP_OKAY;
2850 	         }
2851 	         else if( clique->nvars == 1 )
2852 	         {
2853 	            assert(SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_COLUMN
2854 	               || SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_LOOSE);
2855 	
2856 	            /* clearing data and removing variable from its clique list */
2857 	            SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[0], blkmem, clique->values[0], clique) );
2858 	
2859 	            SCIPsetDebugMsg(set, "fixing last variable %s in clique %u to %d\n", SCIPvarGetName(clique->vars[0]), clique->id,
2860 	               clique->values[0] ? 1 : 0);
2861 	
2862 	            SCIP_CALL( SCIPvarFixBinary(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2863 	                  branchcand, eventqueue, cliquetable, clique->values[0], infeasible, nchgbds) );
2864 	
2865 	            clique->nvars = 0;
2866 	            clique->equation = FALSE;
2867 	            clique->startcleanup = -1;
2868 	
2869 	            return SCIP_OKAY;
2870 	         }
2871 	      }
2872 	
2873 	      if( needsorting )
2874 	      {
2875 	         SCIP_Bool isequation = clique->equation;
2876 	
2877 	         /* remove multiple entries of the same variable */
2878 	         SCIP_CALL( sortAndMergeClique(clique->vars, clique->values, &(clique->nvars), &isequation, clique, blkmem, set, stat,
2879 	               transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, nchgbds, infeasible) );
2880 	
2881 	         clique->equation = isequation;
2882 	      }
2883 	
2884 	      /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2885 	
2886 	      clique->startcleanup = -1;
2887 	   }
2888 	   assert(SCIPcliqueIsCleanedUp(clique));
2889 	
2890 	   return SCIP_OKAY;
2891 	}
2892 	
2893 	#ifdef SCIP_MORE_DEBUG
2894 	/** checks whether clique appears in all clique lists of the involved variables */
2895 	static
2896 	SCIP_Bool checkNEntries(
2897 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
2898 	   )
2899 	{
2900 	   SCIP_Longint nentries = 0;
2901 	   int c;
2902 	
2903 	   assert(cliquetable != NULL);
2904 	
2905 	   for( c = cliquetable->ncliques - 1; c >= 0; --c )
2906 	      nentries += cliquetable->cliques[c]->nvars;
2907 	
2908 	   return (nentries == cliquetable->nentries);
2909 	}
2910 	#else
2911 	#define checkNEntries(cliquetable) TRUE
2912 	#endif
2913 	
2914 	/** removes all empty and single variable cliques from the clique table; removes double entries from the clique table
2915 	 *
2916 	 * @note cliques can be processed several times by this method
2917 	 *
2918 	 * @todo try to detect infeasible implications, e.g., x = 1 => (y = 0 && y = 1)
2919 	 */
2920 	SCIP_RETCODE SCIPcliquetableCleanup(
2921 	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
2922 	   BMS_BLKMEM*           blkmem,             /**< block memory */
2923 	   SCIP_SET*             set,                /**< global SCIP settings */
2924 	   SCIP_STAT*            stat,               /**< problem statistics */
2925 	   SCIP_PROB*            transprob,          /**< transformed problem */
2926 	   SCIP_PROB*            origprob,           /**< original problem */
2927 	   SCIP_TREE*            tree,               /**< branch and bound tree if in solving stage */
2928 	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
2929 	   SCIP_LP*              lp,                 /**< current LP data */
2930 	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
2931 	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
2932 	   int*                  nchgbds,            /**< pointer to store number of fixed variables */
2933 	   SCIP_Bool*            infeasible          /**< pointer to store whether an infeasibility was detected */
2934 	   )
2935 	{
2936 	   assert(cliquetable != NULL);
2937 	   assert(stat != NULL);
2938 	   assert(infeasible != NULL);
2939 	
2940 	   *infeasible = FALSE;
2941 	
2942 	   /* check if we have anything to do */
2943 	   if( stat->npresolfixedvars == cliquetable->ncleanupfixedvars
2944 	      && stat->npresolaggrvars == cliquetable->ncleanupaggrvars
2945 	      && cliquetable->ndirtycliques == 0 )
2946 	      return SCIP_OKAY;
2947 	
2948 	   SCIPsetDebugMsg(set, "cleaning up clique table with %d cliques (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
2949 	
2950 	   /* delay events */
2951 	   SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
2952 	
2953 	   cliquetable->incleanup = TRUE;
2954 	   while( cliquetable->ndirtycliques > 0 && !(*infeasible) )
2955 	   {
2956 	      SCIP_CLIQUE* clique;
2957 	      SCIP_CLIQUE* sameclique;
2958 	
2959 	      clique = cliquetable->cliques[0];
2960 	
2961 	      assert(!SCIPcliqueIsCleanedUp(clique));
2962 	
2963 	      /* remove not clean up clique from hastable */
2964 	      SCIP_CALL( SCIPhashtableRemove(cliquetable->hashtable, (void*)clique) );
2965 	      cliquetable->nentries -= clique->nvars;
2966 	      assert(cliquetable->nentries >= 0);
2967 	
2968 	      SCIP_CALL( cliqueCleanup(clique, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2969 	            cliquetable, nchgbds, infeasible) );
2970 	
2971 	      if( *infeasible )
2972 	         break;
2973 	
2974 	      assert(SCIPcliqueIsCleanedUp(clique));
2975 	
2976 	      /* swap freshly cleaned clique with last dirty clique */
2977 	      cliquetable->ndirtycliques--;
2978 	      cliquetableSwapCliques(cliquetable, 0, cliquetable->ndirtycliques);
2979 	      cliqueCheck(clique);
2980 	
2981 	      /* @todo check if we can/want to aggregate variables with the following code */
2982 	#ifdef SCIP_DISABLED_CODE
2983 	      if( clique->nvars == 2 && clique->equation && SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING )
2984 	      {
2985 	         SCIP_VAR* var0;
2986 	         SCIP_VAR* var1;
2987 	         SCIP_Real scalarx;
2988 	         SCIP_Real scalary;
2989 	         SCIP_Real rhs = 1.0;
2990 	         SCIP_Bool aggregated;
2991 	
2992 	         printf("aggr vars, clique %u\n", clique->id);
2993 	
2994 	         if( SCIPvarGetType(clique->vars[0]) >= SCIPvarGetType(clique->vars[1]) )
2995 	         {
2996 	            var0 = clique->vars[0];
2997 	            var1 = clique->vars[1];
2998 	
2999 	            if( !clique->values[0] )
3000 	            {
3001 	               scalarx = -1.0;
3002 	               rhs -= 1.0;
3003 	            }
3004 	            else
3005 	               scalarx = 1.0;
3006 	
3007 	            if( !clique->values[1] )
3008 	            {
3009 	               scalary = -1.0;
3010 	               rhs -= 1.0;
3011 	            }
3012 	            else
3013 	               scalary = 1.0;
3014 	         }
3015 	         else
3016 	         {
3017 	            var0 = clique->vars[1];
3018 	            var1 = clique->vars[0];
3019 	
3020 	            if( !clique->values[0] )
3021 	            {
3022 	               scalary = -1.0;
3023 	               rhs -= 1.0;
3024 	            }
3025 	            else
3026 	               scalary = 1.0;
3027 	
3028 	            if( !clique->values[1] )
3029 	            {
3030 	               scalarx = -1.0;
3031 	               rhs -= 1.0;
3032 	            }
3033 	            else
3034 	               scalarx = 1.0;
3035 	         }
3036 	
3037 	         assert((SCIPvarGetStatus(var0) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var0) == SCIP_VARSTATUS_COLUMN)
3038 	            && (SCIPvarGetStatus(var1) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_COLUMN));
3039 	
3040 	         /* aggregate the variable */
3041 	         SCIP_CALL( SCIPvarTryAggregateVars(set, blkmem, stat, transprob, origprob, primal,
3042 		    tree, lp, cliquetable, branchcand, eventfilter, eventqueue,
3043 		    var0, var1, scalarx, scalary, rhs, infeasible, &aggregated) );
3044 	
3045 	         assert(aggregated || *infeasible);
3046 	      }
3047 	#endif
3048 	
3049 	      sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
3050 	
3051 	      /* check if the clique is already contained in the clique table, or if it is redundant (too small) */
3052 	      if( clique->nvars <= 1 || sameclique != NULL )
3053 	      {
3054 	         int j;
3055 	
3056 	         /* infeasible or fixing should be performed already on trivial clique */
3057 	         assert(clique->nvars > 1 || !clique->equation);
3058 	
3059 	         /* if the clique which is already in the hashtable is an inequality and the current clique is an equation, we
3060 	          * update the equation status of the old one
3061 	          */
3062 	         if( clique->nvars > 1 && clique->equation && !sameclique->equation )
3063 	         {
3064 	            assert(sameclique->nvars >= 2);
3065 	
3066 	            /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
3067 	             *       the sameclique from the hashmap while adding the new clique
3068 	             */
3069 	            sameclique->equation = TRUE;
3070 	         }
3071 	
3072 	         /* delete the clique from the variables' clique lists */
3073 	         for( j = 0; j < clique->nvars; ++j )
3074 	         {
3075 	            SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[j], blkmem, clique->values[j], clique) );
3076 	         }
3077 	
3078 	         /* free clique and remove it from clique table */
3079 	         cliqueFree(&clique, blkmem);
3080 	         cliquetable->ncliques--;
3081 	         /* insert a clean clique from the end of the array */
3082 	         if( cliquetable->ndirtycliques < cliquetable->ncliques )
3083 	         {
3084 	            assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ncliques]));
3085 	            cliquetable->cliques[cliquetable->ndirtycliques] = cliquetable->cliques[cliquetable->ncliques];
3086 	            cliquetable->cliques[cliquetable->ndirtycliques]->index = cliquetable->ndirtycliques;
3087 	         }
3088 	      }
3089 	      else
3090 	      {
3091 	         cliquetable->nentries += clique->nvars;
3092 	
3093 	         SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
3094 	         if( !clique->eventsissued )
3095 	         {
3096 	            int j;
3097 	
3098 	            /* issue IMPLADDED event on each variable in the clique */
3099 	            for( j = 0; j < clique->nvars; ++j )
3100 	            {
3101 	               SCIP_EVENT* event;
3102 	
3103 	               SCIP_CALL( SCIPeventCreateImplAdded(&event, blkmem, clique->vars[j]) );
3104 	               SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3105 	            }
3106 	            clique->eventsissued = TRUE;
3107 	         }
3108 	      }
3109 	   }
3110 	   cliquetable->incleanup = FALSE;
3111 	
3112 	   /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */
3113 	   cliquetable->ncleanupfixedvars = stat->npresolfixedvars;
3114 	   cliquetable->ncleanupaggrvars = stat->npresolaggrvars;
3115 	   assert(*infeasible || cliquetable->ndirtycliques == 0);
3116 	
3117 	   assert(*infeasible || checkNEntries(cliquetable)); /*lint !e506*/
3118 	
3119 	   SCIPsetDebugMsg(set, "cleaned up clique table has %d cliques left (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
3120 	
3121 	   /* process events */
3122 	   SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, NULL, lp, branchcand, NULL) );
3123 	
3124 	   return SCIP_OKAY;
3125 	}
3126 	
3127 	/** computes connected components of the clique table
3128 	 *
3129 	 *  an update becomes necessary if a clique gets added with variables from different components
3130 	 */
3131 	SCIP_RETCODE SCIPcliquetableComputeCliqueComponents(
3132 	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
3133 	   SCIP_SET*             set,                /**< global SCIP settings */
3134 	   BMS_BLKMEM*           blkmem,             /**< block memory */
3135 	   SCIP_VAR**            vars,               /**< array of problem variables, sorted by variable type */
3136 	   int                   nbinvars,           /**< number of binary variables */
3137 	   int                   nintvars,           /**< number of integer variables */
3138 	   int                   nimplvars           /**< number of implicit integer variables */
3139 	   )
3140 	{
3141 	   SCIP_DISJOINTSET* djset;
3142 	   int nimplbinvars;
3143 	   int v;
3144 	   int c;
3145 	   int nbinvarstotal;
3146 	   int ndiscvars;
3147 	   int nnonbinvars;
3148 	
3149 	   SCIP_CLIQUE** cliques;
3150 	
3151 	   assert(cliquetable != NULL);
3152 	   assert(vars != NULL);
3153 	
3154 	   nimplbinvars = 0;
3155 	   cliquetable->compsfromscratch = FALSE;
3156 	   ndiscvars = nbinvars + nintvars + nimplvars;
3157 	
3158 	   /* detect integer and implicit integer variables with bounds {0,1} because they might appear in cliques, as well */
3159 	   for( v = nbinvars; v < ndiscvars; ++v )
3160 	   {
3161 	      if( SCIPvarIsBinary(vars[v]) )
3162 	         ++nimplbinvars;
3163 	   }
3164 	
3165 	   /* count binary and implicit binary variables */
3166 	   nbinvarstotal = nbinvars + nimplbinvars;
3167 	
3168 	   /* if there are no binary variables, return */
3169 	   if( nbinvarstotal == 0 )
3170 	   {
3171 	      SCIPsetDebugMsg(set, "0 binary variables in total --> 0 connected components in the clique table");
3172 	      cliquetable->ncliquecomponents = 0;
3173 	      return SCIP_OKAY;
3174 	   }
3175 	
3176 	   /* no cliques are present */
3177 	   if( cliquetable->ncliques == 0 )
3178 	   {
3179 	      SCIPsetDebugMsg(set, "0 cliques --> Clique table has %d isolated nodes", nbinvarstotal);
3180 	      cliquetable->ncliquecomponents = nbinvarstotal;
3181 	      return SCIP_OKAY;
3182 	   }
3183 	
3184 	   /* create or clear the variable index mapping */
3185 	   if( cliquetable->varidxtable == NULL )
3186 	   {
3187 	      SCIP_CALL( SCIPhashmapCreate(&(cliquetable)->varidxtable, blkmem, ndiscvars) );
3188 	   }
3189 	   else
3190 	   {
3191 	      SCIP_CALL( SCIPhashmapRemoveAll(cliquetable->varidxtable) );
3192 	   }
3193 	
3194 	   /* loop through variables and store their respective positions in the hash map if they are binary */
3195 	   for( v = 0; v < ndiscvars; ++v )
3196 	   {
3197 	      SCIP_VAR* var = vars[v];
3198 	      if( SCIPvarIsBinary(var) )
3199 	      {
3200 	         /* consider only active representatives */
3201 	         if( SCIPvarIsActive(var) )
3202 	         {
3203 	            SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3204 	         }
3205 	         else
3206 	         {
3207 	            var = SCIPvarGetProbvar(var);
3208 	            if( SCIPvarIsActive(var) )
3209 	            {
3210 	               SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3211 	            }
3212 	         }
3213 	      }
3214 	   }
3215 	
3216 	   /* free previous disjoint set (union find) data structure which has become outdated if new variables are present */
3217 	   if( cliquetable->djset != NULL )
3218 	      SCIPdisjointsetFree(&cliquetable->djset, blkmem);
3219 	
3220 	   /* we need to consider integer and implicit integer variables for which SCIPvarIsBinary() returns TRUE.
3221 	    * These may be scattered across the ninteger + nimplvars implicit integer variables.
3222 	    * For simplicity, we add all integer and implicit integer variables as nodes to the graph, and subtract
3223 	    * the amount of nonbinary integer and implicit integer variables afterwards.
3224 	    */
3225 	   SCIP_CALL( SCIPdisjointsetCreate(&cliquetable->djset, blkmem, ndiscvars) );
3226 	   djset = cliquetable->djset;
3227 	
3228 	   /* subtract all (implicit) integer for which SCIPvarIsBinary() returns FALSE */
3229 	   nnonbinvars = (nintvars + nimplvars) - nimplbinvars;
3230 	
3231 	   cliques = cliquetable->cliques;
3232 	
3233 	   /* for every clique, we connect clique variable components, treating a clique as a path
3234 	    *
3235 	    * if the graph turns out to be completely connected (except for the nonbinary variables), we terminate */
3236 	   for( c = 0; c < cliquetable->ncliques && SCIPdisjointsetGetComponentCount(djset) > 1 + nnonbinvars; ++c )
3237 	   {
3238 	      SCIP_CLIQUE* clique;
3239 	
3240 	      clique = cliques[c];
3241 	      cliquetableUpdateConnectednessClique(cliquetable, clique);
3242 	   }
3243 	
3244 	   /* subtract superfluous integer and implicit integer variables added to the auxiliary graph */
3245 	   cliquetable->ncliquecomponents = SCIPdisjointsetGetComponentCount(djset) - nnonbinvars;
3246 	   assert(cliquetable->ncliquecomponents >= 0);
3247 	   assert(cliquetable->ncliquecomponents <= nbinvarstotal);
3248 	
3249 	   SCIPsetDebugMsg(set, "connected components detection: %d comps (%d clqs, %d vars)", cliquetable->ncliquecomponents, cliquetable->ncliques, nbinvarstotal);
3250 	
3251 	   return SCIP_OKAY;
3252 	}
3253 	
3254 	/*
3255 	 * simple functions implemented as defines
3256 	 */
3257 	
3258 	/* In debug mode, the following methods are implemented as function calls to ensure
3259 	 * type validity.
3260 	 * In optimized mode, the methods are implemented as defines to improve performance.
3261 	 * However, we want to have them in the library anyways, so we have to undef the defines.
3262 	 */
3263 	
3264 	#undef SCIPvboundsGetNVbds
3265 	#undef SCIPvboundsGetVars
3266 	#undef SCIPvboundsGetCoefs
3267 	#undef SCIPvboundsGetConstants
3268 	#undef SCIPimplicsGetNImpls
3269 	#undef SCIPimplicsGetVars
3270 	#undef SCIPimplicsGetTypes
3271 	#undef SCIPimplicsGetBounds
3272 	#undef SCIPimplicsGetIds
3273 	#undef SCIPcliqueGetNVars
3274 	#undef SCIPcliqueGetVars
3275 	#undef SCIPcliqueGetValues
3276 	#undef SCIPcliqueGetId
3277 	#undef SCIPcliqueGetIndex
3278 	#undef SCIPcliqueIsCleanedUp
3279 	#undef SCIPcliqueIsEquation
3280 	#undef SCIPcliquelistGetNCliques
3281 	#undef SCIPcliquelistGetCliques
3282 	#undef SCIPcliquelistCheck
3283 	#undef SCIPcliquetableGetNCliques
3284 	#undef SCIPcliquetableGetCliques
3285 	#undef SCIPcliquetableGetNEntries
3286 	#undef SCIPcliquetableGetNCliqueComponents
3287 	#undef SCIPcliquetableNeedsComponentUpdate
3288 	
3289 	/** gets number of variable bounds contained in given variable bounds data structure */
3290 	int SCIPvboundsGetNVbds(
3291 	   SCIP_VBOUNDS*         vbounds             /**< variable bounds data structure */
3292 	   )
3293 	{
3294 	   return vbounds != NULL ? vbounds->len : 0;
3295 	}
3296 	
3297 	/** gets array of variables contained in given variable bounds data structure */
3298 	SCIP_VAR** SCIPvboundsGetVars(
3299 	   SCIP_VBOUNDS*         vbounds             /**< variable bounds data structure */
3300 	   )
3301 	{
3302 	   return vbounds != NULL ? vbounds->vars : NULL;
3303 	}
3304 	
3305 	/** gets array of coefficients contained in given variable bounds data structure */
3306 	SCIP_Real* SCIPvboundsGetCoefs(
3307 	   SCIP_VBOUNDS*         vbounds             /**< variable bounds data structure */
3308 	   )
3309 	{
3310 	   return vbounds != NULL ? vbounds->coefs : NULL;
3311 	}
3312 	
3313 	/** gets array of constants contained in given variable bounds data structure */
3314 	SCIP_Real* SCIPvboundsGetConstants(
3315 	   SCIP_VBOUNDS*         vbounds             /**< variable bounds data structure */
3316 	   )
3317 	{
3318 	   return vbounds != NULL ? vbounds->constants : NULL;
3319 	}
3320 	
3321 	/** gets number of implications for a given binary variable fixing */
3322 	int SCIPimplicsGetNImpls(
3323 	   SCIP_IMPLICS*         implics,            /**< implication data */
3324 	   SCIP_Bool             varfixing           /**< should the implications on var == FALSE or var == TRUE be returned? */
3325 	   )
3326 	{
3327 	   return implics != NULL ? implics->nimpls[varfixing] : 0;
3328 	}
3329 	
3330 	/** gets array with implied variables for a given binary variable fixing */
3331 	SCIP_VAR** SCIPimplicsGetVars(
3332 	   SCIP_IMPLICS*         implics,            /**< implication data */
3333 	   SCIP_Bool             varfixing           /**< should the implications on var == FALSE or var == TRUE be returned? */
3334 	   )
3335 	{
3336 	   return implics != NULL ? implics->vars[varfixing] : NULL;
3337 	}
3338 	
3339 	/** gets array with implication types for a given binary variable fixing */
3340 	SCIP_BOUNDTYPE* SCIPimplicsGetTypes(
3341 	   SCIP_IMPLICS*         implics,            /**< implication data */
3342 	   SCIP_Bool             varfixing           /**< should the implications on var == FALSE or var == TRUE be returned? */
3343 	   )
3344 	{
3345 	   return implics != NULL ? implics->types[varfixing] : NULL;
3346 	}
3347 	
3348 	/** gets array with implication bounds for a given binary variable fixing */
3349 	SCIP_Real* SCIPimplicsGetBounds(
3350 	   SCIP_IMPLICS*         implics,            /**< implication data */
3351 	   SCIP_Bool             varfixing           /**< should the implications on var == FALSE or var == TRUE be returned? */
3352 	   )
3353 	{
3354 	   return implics != NULL ? implics->bounds[varfixing] : NULL;
3355 	}
3356 	
3357 	/** Gets array with unique implication identifiers for a given binary variable fixing.
3358 	 *  If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
3359 	 *  its id is negative, otherwise it is nonnegative.
3360 	 */
3361 	int* SCIPimplicsGetIds(
3362 	   SCIP_IMPLICS*         implics,            /**< implication data */
3363 	   SCIP_Bool             varfixing           /**< should the implications on var == FALSE or var == TRUE be returned? */
3364 	   )
3365 	{
3366 	   return implics != NULL ? implics->ids[varfixing] : NULL;
3367 	}
3368 	
3369 	/** gets number of variables in the cliques */
3370 	int SCIPcliqueGetNVars(
3371 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3372 	   )
3373 	{
3374 	   assert(clique != NULL);
3375 	
3376 	   return clique->nvars;
3377 	}
3378 	
3379 	/** gets array of active problem variables in the cliques */
3380 	SCIP_VAR** SCIPcliqueGetVars(
3381 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3382 	   )
3383 	{
3384 	   assert(clique != NULL);
3385 	
3386 	   return clique->vars;
3387 	}
3388 	
3389 	/** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or
3390 	 *  to TRUE in the clique
3391 	 */
3392 	SCIP_Bool* SCIPcliqueGetValues(
3393 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3394 	   )
3395 	{
3396 	   assert(clique != NULL);
3397 	
3398 	   return clique->values;
3399 	}
3400 	
3401 	/** gets unique identifier of the clique */
3402 	unsigned int SCIPcliqueGetId(
3403 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3404 	   )
3405 	{
3406 	   unsigned int id;
3407 	
3408 	   assert(clique != NULL);
3409 	
3410 	   id = clique->id; /*lint !e732*/
3411 	
3412 	   return id;
3413 	}
3414 	
3415 	/** gets index of the clique in the clique table */
3416 	int SCIPcliqueGetIndex(
3417 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3418 	   )
3419 	{
3420 	   assert(clique != NULL);
3421 	
3422 	   return clique->index;
3423 	}
3424 	
3425 	/** gets unique identifier of the clique */
3426 	SCIP_Bool SCIPcliqueIsCleanedUp(
3427 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3428 	   )
3429 	{
3430 	   assert(clique != NULL);
3431 	
3432 	   return (clique->startcleanup == -1);
3433 	}
3434 	
3435 	/** return whether the given clique is an equation */
3436 	SCIP_Bool SCIPcliqueIsEquation(
3437 	   SCIP_CLIQUE*          clique              /**< clique data structure */
3438 	   )
3439 	{
3440 	   assert(clique != NULL);
3441 	
3442 	   return (SCIP_Bool)(clique->equation); /*lint !e571*/
3443 	}
3444 	
3445 	/** returns the number of cliques stored in the clique list */
3446 	int SCIPcliquelistGetNCliques(
3447 	   SCIP_CLIQUELIST*      cliquelist,         /**< clique list data structure */
3448 	   SCIP_Bool             value               /**< value of the variable for which the cliques should be returned */
3449 	   )
3450 	{
3451 	   return cliquelist != NULL ? cliquelist->ncliques[value] : 0;
3452 	}
3453 	
3454 	/** returns the cliques stored in the clique list, or NULL if the clique list is empty */
3455 	SCIP_CLIQUE** SCIPcliquelistGetCliques(
3456 	   SCIP_CLIQUELIST*      cliquelist,         /**< clique list data structure */
3457 	   SCIP_Bool             value               /**< value of the variable for which the cliques should be returned */
3458 	   )
3459 	{
3460 	   return cliquelist != NULL ? cliquelist->cliques[value] : NULL;
3461 	}
3462 	
3463 	/** checks whether variable is contained in all cliques of the cliquelist */
3464 	void SCIPcliquelistCheck(
3465 	   SCIP_CLIQUELIST*      cliquelist,         /**< clique list data structure */
3466 	   SCIP_VAR*             var                 /**< variable, the clique list belongs to */
3467 	   )
3468 	{
3469 	   /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MORE_DEBUG because it can take at lot of time to check for
3470 	    *       correctness
3471 	    */
3472 	#ifndef NDEBUG
3473 	   int value;
3474 	
3475 	   assert(SCIPvarGetNCliques(var, FALSE) == SCIPcliquelistGetNCliques(cliquelist, FALSE));
3476 	   assert(SCIPvarGetCliques(var, FALSE) == SCIPcliquelistGetCliques(cliquelist, FALSE));
3477 	   assert(SCIPvarGetNCliques(var, TRUE) == SCIPcliquelistGetNCliques(cliquelist, TRUE));
3478 	   assert(SCIPvarGetCliques(var, TRUE) == SCIPcliquelistGetCliques(cliquelist, TRUE));
3479 	
3480 	   for( value = 0; value < 2; ++value )
3481 	   {
3482 	      SCIP_CLIQUE** cliques;
3483 	      int ncliques;
3484 	      int i;
3485 	
3486 	      ncliques = SCIPcliquelistGetNCliques(cliquelist, (SCIP_Bool)value);
3487 	      cliques = SCIPcliquelistGetCliques(cliquelist, (SCIP_Bool)value);
3488 	      for( i = 0; i < ncliques; ++i )
3489 	      {
3490 	         SCIP_CLIQUE* clique;
3491 	         int pos;
3492 	
3493 	         clique = cliques[i];
3494 	         assert(clique != NULL);
3495 	
3496 	         pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value);
3497 	         assert(0 <= pos && pos < clique->nvars);
3498 	         assert(clique->vars[pos] == var);
3499 	         assert(clique->values[pos] == (SCIP_Bool)value);
3500 	      }
3501 	   }
3502 	#endif
3503 	}
3504 	
3505 	/** gets the number of cliques stored in the clique table */
3506 	int SCIPcliquetableGetNCliques(
3507 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
3508 	   )
3509 	{
3510 	   assert(cliquetable != NULL);
3511 	
3512 	   return cliquetable->ncliques;
3513 	}
3514 	
3515 	/** gets the number of cliques created so far by the clique table */
3516 	int SCIPcliquetableGetNCliquesCreated(
3517 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
3518 	   )
3519 	{
3520 	   assert(cliquetable != NULL);
3521 	
3522 	   return cliquetable->ncreatedcliques;
3523 	}
3524 	
3525 	/** gets the array of cliques stored in the clique table */
3526 	SCIP_CLIQUE** SCIPcliquetableGetCliques(
3527 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
3528 	   )
3529 	{
3530 	   assert(cliquetable != NULL);
3531 	
3532 	   return cliquetable->cliques;
3533 	}
3534 	
3535 	/** gets the number of entries in the whole clique table */
3536 	SCIP_Longint SCIPcliquetableGetNEntries(
3537 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
3538 	   )
3539 	{
3540 	   assert(cliquetable != NULL);
3541 	
3542 	   return cliquetable->nentries;
3543 	}
3544 	
3545 	/** returns the number of clique components, or -1 if update is necessary first */
3546 	int SCIPcliquetableGetNCliqueComponents(
3547 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
3548 	   )
3549 	{
3550 	   return cliquetable->compsfromscratch ? -1 : cliquetable->ncliquecomponents;
3551 	}
3552 	
3553 	/** returns TRUE iff the connected clique components need an update (because new cliques were added) */
3554 	SCIP_Bool SCIPcliquetableNeedsComponentUpdate(
3555 	   SCIP_CLIQUETABLE*     cliquetable         /**< clique table data structure */
3556 	   )
3557 	{
3558 	   return cliquetable->compsfromscratch || cliquetable->djset == NULL;
3559 	}
3560