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   sepa_clique.c
26   	 * @ingroup DEFPLUGINS_SEPA
27   	 * @brief  clique separator
28   	 * @author Kati Wolter
29   	 * @author Tobias Achterberg
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "blockmemshell/memory.h"
35   	#include "scip/pub_implics.h"
36   	#include "scip/pub_lp.h"
37   	#include "scip/pub_message.h"
38   	#include "scip/pub_misc.h"
39   	#include "scip/pub_sepa.h"
40   	#include "scip/pub_var.h"
41   	#include "scip/scip_branch.h"
42   	#include "scip/scip_cut.h"
43   	#include "scip/scip_general.h"
44   	#include "scip/scip_lp.h"
45   	#include "scip/scip_mem.h"
46   	#include "scip/scip_message.h"
47   	#include "scip/scip_numerics.h"
48   	#include "scip/scip_param.h"
49   	#include "scip/scip_prob.h"
50   	#include "scip/scip_sepa.h"
51   	#include "scip/scip_sol.h"
52   	#include "scip/scip_var.h"
53   	#include "scip/sepa_clique.h"
54   	#include "tclique/tclique.h"
55   	#include <string.h>
56   	#if defined(_WIN32) || defined(_WIN64)
57   	#else
58   	#include <strings.h> /*lint --e{766}*/
59   	#endif
60   	
61   	
62   	#define SEPA_NAME              "clique"
63   	#define SEPA_DESC              "clique separator of stable set relaxation"
64   	#define SEPA_PRIORITY             -5000
65   	#define SEPA_FREQ                     0
66   	#define SEPA_MAXBOUNDDIST           0.0
67   	#define SEPA_USESSUBSCIP          FALSE /**< does the separator use a secondary SCIP instance? */
68   	#define SEPA_DELAY                FALSE /**< should separation method be delayed, if other separators found cuts? */
69   	
70   	#define DEFAULT_SCALEVAL         1000.0 /**< factor for scaling weights */
71   	#define DEFAULT_MAXTREENODES      10000 /**< maximal number of nodes in branch and bound tree (-1: no limit) */
72   	#define DEFAULT_BACKTRACKFREQ      1000 /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
73   	#define DEFAULT_MAXSEPACUTS          10 /**< maximal number of clique cuts separated per separation round (-1: no limit) */
74   	#define DEFAULT_MAXZEROEXTENSIONS  1000 /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
75   	#define DEFAULT_CLIQUETABLEMEM  20000.0 /**< maximal memory size of dense clique table (in kb) */
76   	#define DEFAULT_CLIQUEDENSITY      0.00 /**< minimal density of cliques to use a dense clique table */
77   	
78   	
79   	/*
80   	 * Data structures
81   	 */
82   	
83   	/** separator data */
84   	struct SCIP_SepaData
85   	{
86   	   TCLIQUE_GRAPH*        tcliquegraph;       /**< tclique graph data structure */
87   	   SCIP*                 scip;               /**< SCIP data structure */
88   	   SCIP_SEPA*            sepa;               /**< separator */
89   	   SCIP_SOL*             sol;                /**< primal solution that is currently separated */
90   	   SCIP_Real*            varsolvals;         /**< LP solution of binary variables (contained in a 3-clique in implgraph) */
91   	   SCIP_Real             scaleval;           /**< factor for scaling weights */
92   	   SCIP_Longint          ncalls;             /**< number of calls to the clique separator */
93   	   int                   maxtreenodes;       /**< maximal number of nodes in branch and bound tree (-1: no limit) */
94   	   int                   backtrackfreq;      /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
95   	   int                   maxsepacuts;        /**< maximal number of clique cuts separated per separation round (-1: no limit) */
96   	   int                   maxzeroextensions;  /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
97   	   SCIP_Real             cliquetablemem;     /**< maximal memory size of dense clique table (in kb) */
98   	   SCIP_Real             cliquedensity;      /**< minimal density of cliques to use a dense clique table */
99   	   int                   ncuts;              /**< number of cuts found */
100  	   SCIP_Bool             tcliquegraphloaded; /**< TRUE if tcliquegraph is already loaded (tcliquegraph can be NULL),
101  	                                              *   FALSE otherwise */
102  	   SCIP_Bool             cutoff;             /**< whether the clique algorithm detected a cutoff */
103  	   SCIP_RETCODE          retcode;            /**< error code which might occur during the maximal clique algorithm */
104  	};
105  	
106  	/** tclique graph data */
107  	struct TCLIQUE_Graph
108  	{
109  	   SCIP_VAR**            vars;               /**< active problem variables (or negated variables) the nodes belong to */
110  	   TCLIQUE_WEIGHT*       weights;            /**< weight of nodes */
111  	   int*                  adjnodesidxs;       /**< indices in adjnodes array of first adjacent nodes for each node */
112  	   int*                  cliqueidsidxs;      /**< indices in cliqueids array of first clique the node is contained in */
113  	   int*                  adjnodes;           /**< adjacent nodes of edges */
114  	   unsigned int*         cliqueids;          /**< unique ids of cliques */
115  	   unsigned int*         cliquetable;        /**< dense bitvector clique table (array stored as a vector) */
116  	   int                   adjnodessize;       /**< size of adjnodes array */
117  	   int                   cliqueidssize;      /**< size of cliqueids array */
118  	   int                   nnodes;             /**< number of nodes in graph */
119  	   int                   tablewidth;         /**< number of unsigned ints per row in the table */
120  	
121  	   int                   maxnnodes;           /**< allocated memory for some arrays */
122  	};
123  	
124  	
125  	/*
126  	 * Methods for tclique graph
127  	 */
128  	
129  	/** creates an empty tclique graph data structure */
130  	static
131  	SCIP_RETCODE tcliquegraphCreate(
132  	   SCIP*                 scip,               /**< SCIP data structure */
133  	   TCLIQUE_GRAPH**       tcliquegraph        /**< pointer to tclique graph data */
134  	   )
135  	{
136  	   int maxnnodes;
137  	
138  	   assert(tcliquegraph != NULL);
139  	
140  	   SCIP_CALL( SCIPallocBlockMemory(scip, tcliquegraph) );
141  	
142  	   /* there are at most 2*nbinvars nodes in the graph */
143  	   maxnnodes = 2*SCIPgetNBinVars(scip);
144  	   assert(maxnnodes > 0);
145  	
146  	   /* allocate memory for tclique graph arrays */
147  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->vars, maxnnodes) );
148  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->weights, maxnnodes) );
149  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, maxnnodes+1) );
150  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, maxnnodes+1) );
151  	   (*tcliquegraph)->adjnodesidxs[0] = 0;  /* the last slot defines the end of the last node */
152  	   (*tcliquegraph)->cliqueidsidxs[0] = 0; /* the last slot defines the end of the last node */
153  	   (*tcliquegraph)->adjnodes = NULL;
154  	   (*tcliquegraph)->cliqueids = NULL;
155  	   (*tcliquegraph)->cliquetable = NULL;
156  	   (*tcliquegraph)->adjnodessize = 0;
157  	   (*tcliquegraph)->cliqueidssize = 0;
158  	   (*tcliquegraph)->nnodes = 0;
159  	   (*tcliquegraph)->tablewidth = 0;
160  	   (*tcliquegraph)->maxnnodes = maxnnodes;  /* remember allocated memory */
161  	
162  	   return SCIP_OKAY;
163  	}
164  	
165  	/** frees the tclique graph data structure and releases all captured variables */
166  	static
167  	SCIP_RETCODE tcliquegraphFree(
168  	   SCIP*                 scip,               /**< SCIP data structure */
169  	   TCLIQUE_GRAPH**       tcliquegraph        /**< pointer to tclique graph data */
170  	   )
171  	{
172  	   int v;
173  	
174  	   assert(tcliquegraph != NULL);
175  	   assert(*tcliquegraph != NULL);
176  	
177  	   /* release variables */
178  	   for( v = 0; v < (*tcliquegraph)->nnodes; ++v )
179  	   {
180  	      SCIP_CALL( SCIPreleaseVar(scip, &(*tcliquegraph)->vars[v]) );
181  	   }
182  	
183  	   /* free memory */
184  	   SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->vars, (*tcliquegraph)->maxnnodes);
185  	   SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->weights, (*tcliquegraph)->maxnnodes);
186  	   SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, (*tcliquegraph)->maxnnodes + 1);
187  	   SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, (*tcliquegraph)->maxnnodes + 1);
188  	   SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->adjnodes);
189  	   SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliqueids);
190  	   SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliquetable);
191  	   SCIPfreeBlockMemory(scip, tcliquegraph);
192  	
193  	   return SCIP_OKAY;
194  	}
195  	
196  	
197  	/** ensures that the cliqueids array can store at least num entries */
198  	static
199  	SCIP_RETCODE tcliquegraphEnsureCliqueidsSize(
200  	   SCIP*                 scip,               /**< SCIP data structure */
201  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< tclique graph data */
202  	   int                   num                 /**< minimal number of adjacent nodes to be able to store in the array */
203  	   )
204  	{
205  	   assert(tcliquegraph != NULL);
206  	
207  	   if( num > tcliquegraph->cliqueidssize )
208  	   {
209  	      tcliquegraph->cliqueidssize = SCIPcalcMemGrowSize(scip, num);
210  	      SCIP_CALL( SCIPreallocMemoryArray(scip, &tcliquegraph->cliqueids, tcliquegraph->cliqueidssize) );
211  	   }
212  	   assert(num <= tcliquegraph->cliqueidssize);
213  	
214  	   return SCIP_OKAY;
215  	}
216  	
217  	/** adds a node to the tclique graph defined as a variable-value pair; adds all cliques to the cliqueids array the
218  	 *  variable is contained in with the given value
219  	 */
220  	static
221  	SCIP_RETCODE tcliquegraphAddNode(
222  	   SCIP*                 scip,               /**< SCIP data structure */
223  	   TCLIQUE_GRAPH**       tcliquegraph,       /**< pointer to tclique graph data */
224  	   SCIP_VAR*             var,                /**< active binary problem variable */
225  	   SCIP_Bool             value,              /**< value of the variable in the node */
226  	   int*                  nodeidx             /**< pointer to store the index of the new node */
227  	   )
228  	{
229  	   SCIP_VAR* nodevar;
230  	   unsigned int* cliqueids;
231  	   SCIP_CLIQUE** cliques;
232  	   int ncliques;
233  	   int nadjnodes;
234  	   int ncliqueids;
235  	   int i;
236  	
237  	   assert(tcliquegraph != NULL);
238  	   assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
239  	   assert(SCIPvarIsActive(var));
240  	   assert(nodeidx != NULL);
241  	
242  	   /* create tclique graph data if not yet existing */
243  	   if( *tcliquegraph == NULL )
244  	   {
245  	      SCIP_CALL( tcliquegraphCreate(scip, tcliquegraph) );
246  	   }
247  	   assert(*tcliquegraph != NULL);
248  	   assert((*tcliquegraph)->nnodes < 2*SCIPgetNBinVars(scip));
249  	
250  	   /* if the value is FALSE, use the negated variable for the node */
251  	   if( !value )
252  	   {
253  	      SCIP_CALL( SCIPgetNegatedVar(scip, var, &nodevar) );
254  	   }
255  	   else
256  	      nodevar = var;
257  	
258  	   /* get the current number of used entries in adjnodes and cliqueids arrays */
259  	   nadjnodes = (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes];
260  	   ncliqueids = (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes];
261  	
262  	   /* insert the variable into the tclique graph */
263  	   *nodeidx = (*tcliquegraph)->nnodes;
264  	   SCIP_CALL( SCIPcaptureVar(scip, nodevar) );
265  	   (*tcliquegraph)->vars[*nodeidx] = nodevar;
266  	   (*tcliquegraph)->weights[*nodeidx] = 0;
267  	   (*tcliquegraph)->nnodes++;
268  	
269  	   /* store the ids of the variable's cliques in the cliqueids array */
270  	   ncliques = SCIPvarGetNCliques(var, value);
271  	   cliques = SCIPvarGetCliques(var, value);
272  	   SCIP_CALL( tcliquegraphEnsureCliqueidsSize(scip, *tcliquegraph, ncliqueids + ncliques) );
273  	   cliqueids = (*tcliquegraph)->cliqueids;
274  	   for( i = 0; i < ncliques; ++i )
275  	   {
276  	      assert(ncliqueids < (*tcliquegraph)->cliqueidssize);
277  	      cliqueids[ncliqueids] = SCIPcliqueGetId(cliques[i]);
278  	      assert(i == 0 || cliqueids[ncliqueids-1] <= cliqueids[ncliqueids]);
279  	      ncliqueids++;
280  	   }
281  	
282  	   /* store the new number of used entries in adjnodes and cliqueids arrays */
283  	   (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] = nadjnodes;
284  	   (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] = ncliqueids;
285  	
286  	   return SCIP_OKAY;
287  	}
288  	
289  	/** adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique */
290  	static
291  	SCIP_RETCODE tcliquegraphAddCliqueVars(
292  	   SCIP*                 scip,               /**< SCIP data structure */
293  	   TCLIQUE_GRAPH**       tcliquegraph,       /**< pointer to tclique graph data */
294  	   int**                 cliquegraphidx      /**< array to store tclique graph node index of variable/value pairs */
295  	   )
296  	{
297  	   SCIP_VAR** vars;
298  	   int nvars;
299  	   int i;
300  	
301  	   assert(tcliquegraph != NULL);
302  	   assert(cliquegraphidx != NULL);
303  	   assert(cliquegraphidx[0] != NULL);
304  	   assert(cliquegraphidx[1] != NULL);
305  	
306  	   /* get binary problem variables */
307  	   vars = SCIPgetVars(scip);
308  	   nvars = SCIPgetNBinVars(scip);
309  	
310  	   for( i = 0; i < nvars; ++i )
311  	   {
312  	      SCIP_VAR* var;
313  	      int value;
314  	
315  	      var = vars[i];
316  	
317  	      for( value = 0; value < 2; ++value )
318  	      {
319  	         assert(cliquegraphidx[value][i] == -1);
320  	
321  	         if( SCIPvarGetNCliques(var, (SCIP_Bool)value) >= 1 )
322  	         {
323  	            /* all cliques stored in the clique table are at least 3-cliques */
324  	            SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, var, (SCIP_Bool)value, &cliquegraphidx[value][i]) );
325  	         }
326  	      }
327  	   }
328  	
329  	   return SCIP_OKAY;
330  	}
331  	
332  	/** constructs dense clique incidence matrix
333  	 *
334  	 * @todo add implicit and integer variables appearing in cliques also to the clique table
335  	 */
336  	static
337  	SCIP_RETCODE tcliquegraphConstructCliqueTable(
338  	   SCIP*                 scip,               /**< SCIP data structure */
339  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< tclique graph data */
340  	   SCIP_Real             cliquetablemem,     /**< maximal memory size of dense clique table (in kb) */
341  	   SCIP_Real             cliquedensity       /**< minimal density of cliques to store as dense table */
342  	   )
343  	{
344  	   SCIP_CLIQUE** cliques;
345  	   int* varids;
346  	   unsigned int* cliquetable;
347  	   SCIP_Real density;
348  	   int nbits;
349  	   int tablesize;
350  	   int tablewidth;
351  	   int ncliques;
352  	   int nelems;
353  	   int i;
354  	
355  	   cliques = SCIPgetCliques(scip);
356  	   ncliques = SCIPgetNCliques(scip);
357  	   if( ncliques == 0 )
358  	      return SCIP_OKAY;
359  	
360  	   assert(tcliquegraph != NULL);
361  	
362  	   /* calculate size of dense clique table */
363  	   nbits = 8*sizeof(unsigned int);
364  	   tcliquegraph->tablewidth = (tcliquegraph->nnodes + nbits-1) / nbits; /* number of ints needed */
365  	
366  	   /* check if dense clique table is too large (calculate as Reals to avoid overflow) */
367  	   if( (SCIP_Real)tcliquegraph->nnodes * (SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem )
368  	      return SCIP_OKAY;
369  	
370  	   /* calculate clique entry density */
371  	   nelems = 0;
372  	   for( i = 0; i < ncliques; ++i )
373  	      nelems += SCIPcliqueGetNVars(cliques[i]);
374  	   density = (SCIP_Real)nelems / ((SCIP_Real)ncliques * (SCIP_Real)tcliquegraph->nnodes);
375  	   if( density < cliquedensity )
376  	      return SCIP_OKAY;
377  	
378  	   /* allocate memory */
379  	   tablesize = tcliquegraph->nnodes * tcliquegraph->tablewidth;
380  	   SCIPdebugMsg(scip, "clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n",
381  	      tablesize/1024, SCIPgetNCliques(scip), tcliquegraph->nnodes, density);
382  	
383  	   SCIP_CALL( SCIPallocMemoryArray(scip, &tcliquegraph->cliquetable, tablesize) );
384  	   BMSclearMemoryArray(tcliquegraph->cliquetable, tablesize);
385  	
386  	   /* insert the cliques as complete graphs to the incidence matrix */
387  	   SCIP_CALL( SCIPallocBufferArray(scip, &varids, tcliquegraph->nnodes) );
388  	   cliquetable = tcliquegraph->cliquetable;
389  	   tablewidth = tcliquegraph->tablewidth;
390  	   for( i = 0; i < ncliques && !SCIPisStopped(scip); ++i )
391  	   {
392  	      SCIP_VAR** vars;
393  	      SCIP_Bool* vals;
394  	      int nvars;
395  	      int u;
396  	      int v;
397  	
398  	      vars = SCIPcliqueGetVars(cliques[i]);
399  	      vals = SCIPcliqueGetValues(cliques[i]);
400  	      nvars = SCIPcliqueGetNVars(cliques[i]);
401  	
402  	      /* get the node numbers of the variables */
403  	      for( u = 0; u < nvars && !SCIPisStopped(scip); ++u )
404  	      {
405  	         SCIP_VAR* var;
406  	
407  	         /* implicit integer and integer variables are currently not present in the constructed tclique graph */
408  	         if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY )
409  	            continue;
410  	
411  	         var = (vals[u] ? vars[u] : SCIPvarGetNegatedVar(vars[u]));
412  	         assert(var != NULL); /* var must exist even if negated, since it is stored in the tcliquegraph */
413  	         for( v = 0; v < tcliquegraph->nnodes && var != tcliquegraph->vars[v]; ++v )
414  	         {}
415  	         assert(v < tcliquegraph->nnodes);
416  	         varids[u] = v;
417  	      }
418  	
419  	      /* flag the edges in the incidence matrix (excluding diagonal entries) */
420  	      for( u = 0; u < nvars-1 && !SCIPisStopped(scip); ++u )
421  	      {
422  	         int nu;
423  	         int rowstart;
424  	         int colofs;
425  	         unsigned int colmask;
426  	
427  	         /* implicit integer and integer variables are currently not present in the constructed tclique graph */
428  	         if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY )
429  	            continue;
430  	
431  	         nu = varids[u];
432  	         rowstart = nu*tablewidth;
433  	         colofs = nu/nbits;
434  	         colmask = 1U << (nu % nbits); /*lint !e701*/
435  	         for( v = u+1; v < nvars; ++v )
436  	         {
437  	            int nv;
438  	            unsigned int mask;
439  	
440  	            /* implicit integer and integer variables are currently not present in the constructed tclique graph */
441  	            if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_BINARY )
442  	               continue;
443  	
444  	            nv = varids[v];
445  	            mask = 1U << (nv % nbits); /*lint !e701*/
446  	            cliquetable[rowstart+nv/nbits] |= mask;
447  	            cliquetable[nv*tablewidth+colofs] |= colmask;
448  	         }
449  	      }
450  	   }
451  	   SCIPfreeBufferArray(scip, &varids);
452  	
453  	   SCIPdebugMsg(scip, "clique separator: finished constructing dense clique table\n");
454  	
455  	   return SCIP_OKAY;
456  	}
457  	
458  	/** creates tclique data structure using the implication graph;
459  	 *  only variables that are contained in a 3-clique are added as nodes to the clique graph
460  	 */
461  	static
462  	SCIP_RETCODE loadTcliquegraph(
463  	   SCIP*                 scip,               /**< SCIP data structure */
464  	   SCIP_SEPADATA*        sepadata            /**< separator data */
465  	   )
466  	{
467  	   int* cliquegraphidx[2];
468  	   int nvars;
469  	   int i;
470  	
471  	   assert(sepadata != NULL);
472  	   assert(sepadata->tcliquegraph == NULL);
473  	
474  	   /* there is nothing to do, if no binary variables are present in the problem */
475  	   nvars = SCIPgetNBinVars(scip);
476  	   if( nvars == 0 )
477  	      return SCIP_OKAY;
478  	
479  	   /* get temporary memory for mapping variable/value pairs to clique graph nodes */
480  	   SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[0], nvars) );
481  	   SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[1], nvars) );
482  	   for( i = 0; i < nvars; ++i )
483  	   {
484  	      cliquegraphidx[0][i] = -1;
485  	      cliquegraphidx[1][i] = -1;
486  	   }
487  	
488  	   /* insert all variable/value pairs that are contained in an existing 3-clique */
489  	   SCIP_CALL( tcliquegraphAddCliqueVars(scip, &sepadata->tcliquegraph, cliquegraphidx) );
490  	
491  	   /* it occurs that it might be that some cliques were not yet removed from the global clique array, so SCIPgetNClique
492  	    * can be greater than 0, even if there is no clique with some variables left */
493  	   /** @todo clean up empty cliques */
494  	   if( sepadata->tcliquegraph != NULL )
495  	   {
496  	      /* construct the dense clique table */
497  	      SCIP_CALL( tcliquegraphConstructCliqueTable(scip, sepadata->tcliquegraph, sepadata->cliquetablemem, sepadata->cliquedensity) );
498  	   }
499  	
500  	   /* free temporary memory */
501  	   SCIPfreeBufferArray(scip, &cliquegraphidx[1]);
502  	   SCIPfreeBufferArray(scip, &cliquegraphidx[0]);
503  	   if( SCIPisStopped(scip) && sepadata->tcliquegraph != NULL )
504  	      SCIP_CALL( tcliquegraphFree(scip,&sepadata->tcliquegraph) );
505  	   return SCIP_OKAY;
506  	}
507  	
508  	/** updates the weights in the tclique graph data structure */
509  	static
510  	void updateTcliquegraph(
511  	   SCIP*                 scip,               /**< SCIP data structure */
512  	   SCIP_SEPADATA*        sepadata            /**< separator data */
513  	   )
514  	{
515  	   TCLIQUE_GRAPH* tcliquegraph;
516  	   int i;
517  	
518  	   assert(sepadata != NULL);
519  	   assert(sepadata->varsolvals != NULL);
520  	
521  	   tcliquegraph = sepadata->tcliquegraph;
522  	   assert(tcliquegraph != NULL);
523  	
524  	   /* updates weight of all nodes in tclique data structure */
525  	   for( i = 0; i < tcliquegraph->nnodes; i++ )
526  	   {
527  	      int weight;
528  	
529  	      weight = (TCLIQUE_WEIGHT)SCIPfeasFloor(scip, sepadata->varsolvals[i] * sepadata->scaleval);
530  	      tcliquegraph->weights[i] = MAX(weight, 0);
531  	   }
532  	}
533  	
534  	
535  	/*
536  	 * TClique Graph Callbacks
537  	 */
538  	
539  	/** gets number of nodes in the graph */
540  	static
541  	TCLIQUE_GETNNODES(tcliqueGetnnodesClique)
542  	{
543  	   assert(tcliquegraph != NULL);
544  	
545  	   return tcliquegraph->nnodes;
546  	}
547  	
548  	/** gets weight of nodes in the graph */
549  	static
550  	TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique)
551  	{
552  	   assert(tcliquegraph != NULL);
553  	
554  	   return tcliquegraph->weights;
555  	}
556  	
557  	/** returns whether the nodes are member of a common clique */
558  	static
559  	SCIP_Bool nodesHaveCommonClique(
560  	   TCLIQUE_GRAPH*        tcliquegraph,       /**< tclique graph data */
561  	   int                   node1,              /**< first node */
562  	   int                   node2               /**< second node */
563  	   )
564  	{
565  	   assert(tcliquegraph != NULL);
566  	
567  	   /* return TRUE for equal nodes */
568  	   if( node1 == node2 )
569  	      return TRUE;
570  	
571  	   /* check whether the dense clique table was constructed */
572  	   if( tcliquegraph->cliquetable != NULL )
573  	   {
574  	      int nbits;
575  	      unsigned int mask;
576  	      int colofs;
577  	
578  	      /* check entry in the table */
579  	      nbits = 8*sizeof(unsigned int);
580  	      mask = (1U << (node2 % nbits)); /*lint !e701*/
581  	      colofs = node2 / nbits;
582  	      assert(((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0)
583  	         == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/nbits] & (1U << (node1 % nbits))) != 0)); /*lint !e701*/
584  	      return ((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0);
585  	   }
586  	   else
587  	   {
588  	      unsigned int* cliqueids;
589  	      int i1;
590  	      int i2;
591  	      int endi1;
592  	      int endi2;
593  	
594  	      cliqueids = tcliquegraph->cliqueids;
595  	      i1 = tcliquegraph->cliqueidsidxs[node1];
596  	      endi1 = tcliquegraph->cliqueidsidxs[node1+1];
597  	      i2 = tcliquegraph->cliqueidsidxs[node2];
598  	      endi2 = tcliquegraph->cliqueidsidxs[node2+1];
599  	      while( i1 < endi1 && i2 < endi2 )
600  	      {
601  	         while( i1 < endi1 && cliqueids[i1] < cliqueids[i2] )
602  	            i1++;
603  	         if( i1 == endi1 )
604  	            break;
605  	
606  	         while( i2 < endi2 && cliqueids[i2] < cliqueids[i1] )
607  	            i2++;
608  	         if( i2 == endi2 )
609  	            break;
610  	
611  	         if( cliqueids[i1] == cliqueids[i2] )
612  	            return TRUE;
613  	      }
614  	
615  	      return FALSE;
616  	   }
617  	}
618  	
619  	/** returns, whether the edge (node1, node2) is in the graph */
620  	static
621  	TCLIQUE_ISEDGE(tcliqueIsedgeClique)
622  	{
623  	   int left;
624  	   int right;
625  	
626  	   assert(tcliquegraph != NULL);
627  	   assert(0 <= node1 && node1 < tcliquegraph->nnodes);
628  	   assert(0 <= node2 && node2 < tcliquegraph->nnodes);
629  	
630  	   /* check if node2 is contained in adjacency list of node1 (list is ordered by adjacent nodes) */
631  	   left = tcliquegraph->adjnodesidxs[node1];
632  	   right = tcliquegraph->adjnodesidxs[node1+1]-1;
633  	   while( left <= right )
634  	   {
635  	      int middle;
636  	      int node;
637  	
638  	      middle = (left+right)/2;
639  	      node = tcliquegraph->adjnodes[middle];
640  	      if( node < node2 )
641  	         left = middle+1;
642  	      else if( node > node2 )
643  	         right = middle-1;
644  	      else
645  	         return TRUE;
646  	   }
647  	
648  	   /* check if the nodes are member of a common clique */
649  	   return nodesHaveCommonClique(tcliquegraph, node1, node2);
650  	}
651  	
652  	/** selects all nodes from a given set of nodes which are adjacent to a given node
653  	 *  and returns the number of selected nodes
654  	 */
655  	static
656  	TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
657  	{
658  	   int* graphadjnodes;
659  	   int nadjnodes;
660  	   int nodeadjindex;
661  	   int nodeadjend;
662  	   int i;
663  	
664  	   assert(tcliquegraph != NULL);
665  	   assert(0 <= node && node < tcliquegraph->nnodes);
666  	   assert(nnodes == 0 || nodes != NULL);
667  	   assert(adjnodes != NULL);
668  	
669  	   nadjnodes = 0;
670  	
671  	   /* check for each node in given nodes set, if it is adjacent to the given node or shares a common clique */
672  	   graphadjnodes = tcliquegraph->adjnodes;
673  	   nodeadjindex = tcliquegraph->adjnodesidxs[node];
674  	   nodeadjend = tcliquegraph->adjnodesidxs[node+1];
675  	   for( i = 0; i < nnodes; i++ )
676  	   {
677  	      /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */
678  	      assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
679  	      assert(i == 0 || nodes[i-1] < nodes[i]);
680  	      while( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] < nodes[i] )
681  	         nodeadjindex++;
682  	      if( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] == nodes[i] )
683  	      {
684  	         /* current node is adjacent to given node */
685  	         adjnodes[nadjnodes] = nodes[i];
686  	         nadjnodes++;
687  	      }
688  	      else
689  	      {
690  	         /* current node is not adjacent to given node: check if they share a common clique */
691  	         if( nodesHaveCommonClique(tcliquegraph, node, nodes[i]) )
692  	         {
693  	            adjnodes[nadjnodes] = nodes[i];
694  	            nadjnodes++;
695  	         }
696  	      }
697  	   }
698  	
699  	   return nadjnodes;
700  	}
701  	
702  	/** basic code for new cliques (needed because of error handling) */
703  	static
704  	SCIP_RETCODE newsolCliqueAddRow(
705  	   SCIP*                 scip,               /**< SCIP data structure */
706  	   SCIP_SEPA*            sepa,               /**< the cut separator itself */
707  	   SCIP_SEPADATA*        sepadata,           /**< data of separator */
708  	   int                   ncliquenodes,       /**< number of nodes in clique */
709  	   int*                  cliquenodes         /**< nodes in clique */
710  	   )
711  	{
712  	   SCIP_VAR** vars;
713  	   SCIP_ROW* cut;
714  	   char cutname[SCIP_MAXSTRLEN];
715  	   int i;
716  	
717  	   vars = sepadata->tcliquegraph->vars;
718  	   assert(sepadata->tcliquegraph->nnodes > 0);
719  	   assert(vars != NULL);
720  	
721  	   /* create the cut (handle retcode since we do not have a backtrace) */
722  	   (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "clique%" SCIP_LONGINT_FORMAT "_%d", sepadata->ncalls, sepadata->ncuts);
723  	   SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
724  	
725  	   SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
726  	
727  	   assert(ncliquenodes <= sepadata->tcliquegraph->nnodes);
728  	   /*SCIPdebugMsg(scip, " -> clique in graph:");*/
729  	   for( i = 0; i < ncliquenodes; ++i )
730  	   {
731  	      assert(cliquenodes[i] < sepadata->tcliquegraph->nnodes);
732  	      SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cliquenodes[i]], 1.0) );
733  	      /*SCIPdebugMsgPrint(scip, " [%d]<%s>", cliquenodes[i], SCIPvarGetName(vars[cliquenodes[i]]));*/
734  	   }
735  	   /*SCIPdebugMsgPrint(scip, "\n");*/
736  	   SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
737  	
738  	   /* set cut rank: for clique cuts we always set to 1 */
739  	   SCIProwChgRank(cut, 1);
740  	
741  	   /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
742  	
743  	   SCIP_CALL( SCIPaddPoolCut(scip, cut) );
744  	
745  	   /* release the row */
746  	   SCIP_CALL( SCIPreleaseRow(scip, &cut) );
747  	
748  	   return SCIP_OKAY;
749  	}
750  	
751  	/** generates cuts using a clique found by algorithm for maximum weight clique
752  	 *  and decides whether to stop generating cliques with the algorithm for maximum weight clique
753  	 */
754  	static
755  	TCLIQUE_NEWSOL(tcliqueNewsolClique)
756  	{
757  	   SCIP_SEPADATA* sepadata;
758  	   TCLIQUE_WEIGHT minweightinc;
759  	
760  	   assert(acceptsol != NULL);
761  	   assert(stopsolving != NULL);
762  	
763  	   sepadata = (SCIP_SEPADATA*)tcliquedata;
764  	   assert(sepadata != NULL);
765  	   assert(sepadata->scip != NULL);
766  	   assert(sepadata->sepa != NULL);
767  	   assert(sepadata->tcliquegraph != NULL);
768  	   assert(sepadata->ncuts >= 0);
769  	
770  	   /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */
771  	   *acceptsol = FALSE;
772  	   *stopsolving = FALSE;
773  	
774  	   /* slightly increase the minimal weight for additional cliques */
775  	   minweightinc = (cliqueweight - *minweight)/10;
776  	   minweightinc = MAX(minweightinc, 1);
777  	   *minweight += minweightinc;
778  	
779  	   /* adds cut if weight of the clique is greater than 1 */
780  	   if( cliqueweight > sepadata->scaleval )
781  	   {
782  	      SCIP* scip;
783  	      SCIP_SEPA* sepa;
784  	      SCIP_Real* varsolvals;
785  	      SCIP_Real unscaledweight;
786  	      int i;
787  	
788  	      scip = sepadata->scip;
789  	      sepa = sepadata->sepa;
790  	      varsolvals = sepadata->varsolvals;
791  	      assert(varsolvals != NULL);
792  	
793  	      /* calculate the weight of the clique in unscaled fractional variable space */
794  	      unscaledweight = 0.0;
795  	      for( i = 0; i < ncliquenodes; i++ )
796  	         unscaledweight += varsolvals[cliquenodes[i]];
797  	
798  	      if( SCIPisEfficacious(scip, unscaledweight - 1.0) )
799  	      {
800  	         SCIP_RETCODE retcode;
801  	
802  	         /* explicitly handle return code */
803  	         retcode = newsolCliqueAddRow(scip, sepa, sepadata, ncliquenodes, cliquenodes);
804  	         if ( retcode == SCIP_OKAY )
805  	         {
806  	            SCIPdebugMsg(scip, " -> found clique cut (act=%g)\n", unscaledweight);
807  	            sepadata->ncuts++;
808  	
809  	            /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent,
810  	             * such that only more violated cuts are generated afterwards */
811  	            if( sepadata->maxsepacuts >= 0 )
812  	            {
813  	               if( sepadata->ncuts > sepadata->maxsepacuts/2 )
814  	                  *acceptsol = TRUE;
815  	               if( sepadata->ncuts >= sepadata->maxsepacuts )
816  	                  *stopsolving = TRUE;
817  	            }
818  	         }
819  	         else
820  	         {
821  	            /* in case an internal SCIP error occurred we stop the algorithm and store the error code for later
822  	             * evaluation
823  	             */
824  	            sepadata->retcode = retcode;
825  	            *stopsolving = TRUE;
826  	         }
827  	      }
828  	   }
829  	}
830  	
831  	
832  	/*
833  	 * main separation method
834  	 */
835  	
836  	/** searches and adds clique cuts that separate the given primal solution
837  	 *
838  	 *  @todo Should the existing cliques in the table be separated before starting the tclique algorithm?
839  	 *        Is this done somewhere else?
840  	 */
841  	static
842  	SCIP_RETCODE separateCuts(
843  	   SCIP*                 scip,               /**< SCIP data structure */
844  	   SCIP_SEPA*            sepa,               /**< the cut separator itself */
845  	   SCIP_SOL*             sol,                /**< primal solution that should be separated, or NULL for LP solution */
846  	   SCIP_RESULT*          result              /**< pointer to store the result of the separation call */
847  	   )
848  	{  /*lint --e{715}*/
849  	   SCIP_SEPADATA* sepadata;
850  	   TCLIQUE_GRAPH* tcliquegraph;
851  	   int* cliquenodes;
852  	   TCLIQUE_WEIGHT cliqueweight;
853  	   TCLIQUE_STATUS tcliquestatus;
854  	   int ncliquenodes;
855  	   int maxtreenodes;
856  	   int maxzeroextensions;
857  	   SCIP_Bool infeasible;
858  	
859  	   assert(scip != NULL);
860  	   assert(*result == SCIP_DIDNOTRUN);
861  	
862  	   infeasible = FALSE;
863  	   /* get clique table */
864  	   SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
865  	   if( infeasible )
866  	      return SCIP_OKAY;
867  	
868  	   /* get separator data */
869  	   sepadata = SCIPsepaGetData(sepa);
870  	   assert(sepadata != NULL);
871  	
872  	   sepadata->sol = sol;
873  	   sepadata->ncalls = SCIPsepaGetNCalls(sepa);
874  	   sepadata->cutoff = FALSE;
875  	   sepadata->ncuts = 0;
876  	
877  	   /* if we already detected that no implications between binary variables exist, nothing has to be done */
878  	   if( sepadata->tcliquegraph == NULL && sepadata->tcliquegraphloaded )
879  	      return SCIP_OKAY;
880  	
881  	   *result = SCIP_DIDNOTFIND;
882  	
883  	   /* load tclique data structure */
884  	   if( !sepadata->tcliquegraphloaded )
885  	   {
886  	      assert(sepadata->tcliquegraph == NULL);
887  	
888  	      SCIPdebugMsg(scip, "loading implication and clique graph\n");
889  	      SCIP_CALL( loadTcliquegraph(scip, sepadata) );
890  	      sepadata->tcliquegraphloaded = TRUE;
891  	
892  	      if( sepadata->tcliquegraph == NULL )
893  	      {
894  	         if( SCIPisStopped(scip) )
895  	            sepadata->tcliquegraphloaded = FALSE;
896  	         /* we did not find any variables that are contained in a clique with at least 3 variables in the
897  	          * implication graph or in the clique table -> nothing has to be done
898  	          */
899  	         else
900  		 {
901  	            SCIPdebugMsg(scip, "no 3-cliques found in implication graph\n");
902  	         }
903  	
904  	         return SCIP_OKAY;
905  	      }
906  	   }
907  	   tcliquegraph = sepadata->tcliquegraph;
908  	   assert(tcliquegraph != NULL);
909  	
910  	   /* store LP-solution in sepadata and update weights in tclique data structure */
911  	   SCIP_CALL( SCIPallocBufferArray(scip, &sepadata->varsolvals, tcliquegraph->nnodes) );
912  	   SCIP_CALL( SCIPgetSolVals(scip, sol, tcliquegraph->nnodes, tcliquegraph->vars, sepadata->varsolvals) );
913  	   updateTcliquegraph(scip, sepadata);
914  	
915  	   /* get maximal number of tree nodes and maximal zero-extensions */
916  	   maxtreenodes = (sepadata->maxtreenodes == -1 ? INT_MAX : sepadata->maxtreenodes);
917  	   maxzeroextensions = (sepadata->maxzeroextensions == -1 ? INT_MAX : sepadata->maxzeroextensions);
918  	
919  	   SCIPdebugMsg(scip, "searching for violated clique cuts\n");
920  	
921  	   sepadata->retcode = SCIP_OKAY;
922  	
923  	   /* finds maximum weight clique in tclique */
924  	   SCIP_CALL( SCIPallocBufferArray(scip, &cliquenodes, tcliquegraph->nnodes) );
925  	   tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
926  	      tcliquegraph, tcliqueNewsolClique, (TCLIQUE_DATA*)sepadata,
927  	      cliquenodes, &ncliquenodes, &cliqueweight, (int)sepadata->scaleval-1, (int)sepadata->scaleval+1,
928  	      maxtreenodes, sepadata->backtrackfreq, maxzeroextensions, -1, NULL, &tcliquestatus);
929  	
930  	   /* in case an internal error occurred during the maximal clique computation, evaluate that one */
931  	   SCIP_CALL( sepadata->retcode );
932  	
933  	   SCIPdebugMsg(scip, "finished searching clique cuts: found %d cuts\n", sepadata->ncuts);
934  	
935  	   /* frees data structures */
936  	   SCIPfreeBufferArray(scip, &cliquenodes);
937  	   SCIPfreeBufferArray(scip, &sepadata->varsolvals);
938  	
939  	   /* adjust result code */
940  	   if ( sepadata->cutoff )
941  	      *result = SCIP_CUTOFF;
942  	   else if( sepadata->ncuts > 0 )
943  	      *result = SCIP_SEPARATED;
944  	
945  	   /* better reset the sol pointer in sepadata to avoid having an invalid pointer */
946  	   sepadata->sol = NULL;
947  	
948  	   return SCIP_OKAY;
949  	}
950  	
951  	
952  	/*
953  	 * Callback methods of separator
954  	 */
955  	
956  	/** copy method for separator plugins (called when SCIP copies plugins) */
957  	static
958  	SCIP_DECL_SEPACOPY(sepaCopyClique)
959  	{  /*lint --e{715}*/
960  	   assert(scip != NULL);
961  	   assert(sepa != NULL);
962  	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
963  	
964  	   /* call inclusion method of constraint handler */
965  	   SCIP_CALL( SCIPincludeSepaClique(scip) );
966  	
967  	   return SCIP_OKAY;
968  	}
969  	
970  	
971  	/** destructor of separator to free user data (called when SCIP is exiting) */
972  	static
973  	SCIP_DECL_SEPAFREE(sepaFreeClique)
974  	{  /*lint --e{715}*/
975  	   SCIP_SEPADATA* sepadata;
976  	
977  	   sepadata = SCIPsepaGetData(sepa);
978  	   assert(sepadata != NULL);
979  	   assert(sepadata->tcliquegraph == NULL);
980  	
981  	   SCIPfreeBlockMemory(scip, &sepadata);
982  	   SCIPsepaSetData(sepa, NULL);
983  	
984  	   return SCIP_OKAY;
985  	}
986  	
987  	
988  	/** solving process deinitialization method of separator (called before branch and bound process data is freed) */
989  	static
990  	SCIP_DECL_SEPAEXITSOL(sepaExitsolClique)
991  	{  /*lint --e{715}*/
992  	   SCIP_SEPADATA* sepadata;
993  	
994  	   sepadata = SCIPsepaGetData(sepa);
995  	   assert(sepadata != NULL);
996  	
997  	   /* free tclique data */
998  	   if( sepadata->tcliquegraph != NULL )
999  	   {
1000 	      SCIP_CALL( tcliquegraphFree(scip, &sepadata->tcliquegraph) );
1001 	   }
1002 	   assert(sepadata->tcliquegraph == NULL);
1003 	   sepadata->tcliquegraphloaded = FALSE;
1004 	
1005 	   return SCIP_OKAY;
1006 	}
1007 	
1008 	
1009 	/** LP solution separation method of separator */
1010 	static
1011 	SCIP_DECL_SEPAEXECLP(sepaExeclpClique)
1012 	{
1013 	   /*lint --e{715}*/
1014 	
1015 	   *result = SCIP_DIDNOTRUN;
1016 	
1017 	   /* only call separator, if we are not close to terminating */
1018 	   if( SCIPisStopped(scip) )
1019 	      return SCIP_OKAY;
1020 	
1021 	   /* only call separator, if an optimal LP solution is at hand */
1022 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1023 	      return SCIP_OKAY;
1024 	
1025 	   /* only call separator, if there are fractional variables */
1026 	   if( SCIPgetNLPBranchCands(scip) == 0 )
1027 	      return SCIP_OKAY;
1028 	
1029 	   /* separate cuts on the LP solution */
1030 	   SCIP_CALL( separateCuts(scip, sepa, NULL, result) );
1031 	
1032 	   return SCIP_OKAY;
1033 	}
1034 	
1035 	
1036 	/** arbitrary primal solution separation method of separator */
1037 	static
1038 	SCIP_DECL_SEPAEXECSOL(sepaExecsolClique)
1039 	{
1040 	   /*lint --e{715}*/
1041 	
1042 	   *result = SCIP_DIDNOTRUN;
1043 	
1044 	   /* separate cuts on the given primal solution */
1045 	   SCIP_CALL( separateCuts(scip, sepa, sol, result) );
1046 	
1047 	   return SCIP_OKAY;
1048 	}
1049 	
1050 	
1051 	/*
1052 	 * separator specific interface methods
1053 	 */
1054 	
1055 	/** creates the clique separator and includes it in SCIP */
1056 	SCIP_RETCODE SCIPincludeSepaClique(
1057 	   SCIP*                 scip                /**< SCIP data structure */
1058 	   )
1059 	{
1060 	   SCIP_SEPADATA* sepadata;
1061 	   SCIP_SEPA* sepa;
1062 	
1063 	   /* create clique separator data */
1064 	   SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
1065 	   sepadata->tcliquegraph = NULL;
1066 	   sepadata->scip = scip;
1067 	   sepadata->sol = NULL;
1068 	   sepadata->varsolvals = NULL;
1069 	   sepadata->ncalls = 0;
1070 	   sepadata->ncuts = 0;
1071 	   sepadata->tcliquegraphloaded = FALSE;
1072 	
1073 	   /* include separator */
1074 	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
1075 	         SEPA_USESSUBSCIP, SEPA_DELAY,
1076 	         sepaExeclpClique, sepaExecsolClique,
1077 	         sepadata) );
1078 	
1079 	   assert(sepa != NULL);
1080 	   sepadata->sepa = sepa;
1081 	
1082 	   /* set non-NULL pointers to callback methods */
1083 	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyClique) );
1084 	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeClique) );
1085 	   SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolClique) );
1086 	
1087 	   /* add clique separator parameters */
1088 	   SCIP_CALL( SCIPaddRealParam(scip,
1089 	         "separating/clique/scaleval",
1090 	         "factor for scaling weights",
1091 	         &sepadata->scaleval, TRUE, DEFAULT_SCALEVAL, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1092 	   SCIP_CALL( SCIPaddIntParam(scip,
1093 	         "separating/clique/maxtreenodes",
1094 	         "maximal number of nodes in branch and bound tree (-1: no limit)",
1095 	         &sepadata->maxtreenodes, TRUE, DEFAULT_MAXTREENODES, -1, INT_MAX, NULL, NULL) );
1096 	   SCIP_CALL( SCIPaddIntParam(scip,
1097 	         "separating/clique/backtrackfreq",
1098 	         "frequency for premature backtracking up to tree level 1 (0: no backtracking)",
1099 	         &sepadata->backtrackfreq, TRUE, DEFAULT_BACKTRACKFREQ, 0, INT_MAX, NULL, NULL) );
1100 	   SCIP_CALL( SCIPaddIntParam(scip,
1101 	         "separating/clique/maxsepacuts",
1102 	         "maximal number of clique cuts separated per separation round (-1: no limit)",
1103 	         &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) );
1104 	   SCIP_CALL( SCIPaddIntParam(scip,
1105 	         "separating/clique/maxzeroextensions",
1106 	         "maximal number of zero-valued variables extending the clique (-1: no limit)",
1107 	         &sepadata->maxzeroextensions, TRUE, DEFAULT_MAXZEROEXTENSIONS, -1, INT_MAX, NULL, NULL) );
1108 	   SCIP_CALL( SCIPaddRealParam(scip,
1109 	         "separating/clique/cliquetablemem",
1110 	         "maximal memory size of dense clique table (in kb)",
1111 	         &sepadata->cliquetablemem, TRUE, DEFAULT_CLIQUETABLEMEM, 0.0, (SCIP_Real)INT_MAX/1024.0, NULL, NULL) );
1112 	   SCIP_CALL( SCIPaddRealParam(scip,
1113 	         "separating/clique/cliquedensity",
1114 	         "minimal density of cliques to use a dense clique table",
1115 	         &sepadata->cliquedensity, TRUE, DEFAULT_CLIQUEDENSITY, 0.0, 1.0, NULL, NULL) );
1116 	
1117 	   return SCIP_OKAY;
1118 	}
1119