Scippy

SCIP

Solving Constraint Integer Programs

sepa_clique.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_clique.c
17  * @brief clique separator
18  * @author Kati Wolter
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/sepa_clique.h"
28 #include "tclique/tclique.h"
29 #include "scip/pub_misc.h"
30 
31 
32 #define SEPA_NAME "clique"
33 #define SEPA_DESC "clique separator of stable set relaxation"
34 #define SEPA_PRIORITY -5000
35 #define SEPA_FREQ 0
36 #define SEPA_MAXBOUNDDIST 0.0
37 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
38 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
39 
40 #define DEFAULT_SCALEVAL 1000.0 /**< factor for scaling weights */
41 #define DEFAULT_MAXTREENODES 10000 /**< maximal number of nodes in branch and bound tree (-1: no limit) */
42 #define DEFAULT_BACKTRACKFREQ 1000 /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
43 #define DEFAULT_MAXSEPACUTS 10 /**< maximal number of clique cuts separated per separation round (-1: no limit) */
44 #define DEFAULT_MAXZEROEXTENSIONS 1000 /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
45 #define DEFAULT_CLIQUETABLEMEM 20000.0 /**< maximal memory size of dense clique table (in kb) */
46 #define DEFAULT_CLIQUEDENSITY 0.05 /**< minimal density of cliques to use a dense clique table */
47 
48 
49 /*
50  * Data structures
51  */
52 
53 /** separator data */
54 struct SCIP_SepaData
55 {
56  TCLIQUE_GRAPH* tcliquegraph; /**< tclique graph data structure */
57  SCIP* scip; /**< SCIP data structure */
58  SCIP_SEPA* sepa; /**< separator */
59  SCIP_SOL* sol; /**< primal solution that is currently separated */
60  SCIP_Real* varsolvals; /**< LP solution of binary variables (contained in a 3-clique in implgraph) */
61  SCIP_Real scaleval; /**< factor for scaling weights */
62  SCIP_Longint ncalls; /**< number of calls to the clique separator */
63  int maxtreenodes; /**< maximal number of nodes in branch and bound tree (-1: no limit) */
64  int backtrackfreq; /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
65  int maxsepacuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */
66  int maxzeroextensions; /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
67  SCIP_Real cliquetablemem; /**< maximal memory size of dense clique table (in kb) */
68  SCIP_Real cliquedensity; /**< minimal density of cliques to use a dense clique table */
69  int ncuts; /**< number of cuts found */
70  SCIP_Bool tcliquegraphloaded; /**< TRUE if tcliquegraph is already loaded (tcliquegraph can be NULL),
71  * FALSE otherwise */
72  SCIP_Bool cutoff; /**< whether the clique algorithm detected a cutoff */
73  SCIP_RETCODE retcode; /**< error code which might occur during the maximal clique algorithm */
74 };
75 
76 /** tclique graph data */
77 struct TCLIQUE_Graph
78 {
79  SCIP_VAR** vars; /**< active problem variables (or negated variables) the nodes belong to */
80  TCLIQUE_WEIGHT* weights; /**< weight of nodes */
81  int* adjnodesidxs; /**< indices in adjnodes array of first adjacent nodes for each node */
82  int* cliqueidsidxs; /**< indices in cliqueids array of first clique the node is contained in */
83  int* adjnodes; /**< adjacent nodes of edges */
84  int* cliqueids; /**< unique ids of cliques */
85  unsigned int* cliquetable; /**< dense bitvector clique table (array stored as a vector) */
86  int adjnodessize; /**< size of adjnodes array */
87  int cliqueidssize; /**< size of cliqueids array */
88  int nnodes; /**< number of nodes in graph */
89  int tablewidth; /**< number of unsigned ints per row in the table */
90 };
91 
92 
93 /*
94  * Methods for tclique graph
95  */
96 
97 /** creates an empty tclique graph data structure */
98 static
99 SCIP_RETCODE tcliquegraphCreate(
100  SCIP* scip, /**< SCIP data structure */
101  TCLIQUE_GRAPH** tcliquegraph /**< pointer to tclique graph data */
102  )
103 {
104  int maxnnodes;
105 
106  assert(tcliquegraph != NULL);
107 
108  SCIP_CALL( SCIPallocMemory(scip, tcliquegraph) );
109 
110  /* there are at most 2*nbinvars nodes in the graph */
111  maxnnodes = 2*SCIPgetNBinVars(scip);
112  assert(maxnnodes > 0);
113 
114  /* allocate memory for tclique graph arrays */
115  SCIP_CALL( SCIPallocMemoryArray(scip, &(*tcliquegraph)->vars, maxnnodes) );
116  SCIP_CALL( SCIPallocMemoryArray(scip, &(*tcliquegraph)->weights, maxnnodes) );
117  SCIP_CALL( SCIPallocMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, maxnnodes+1) );
118  SCIP_CALL( SCIPallocMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, maxnnodes+1) );
119  (*tcliquegraph)->adjnodesidxs[0] = 0; /* the last slot defines the end of the last node */
120  (*tcliquegraph)->cliqueidsidxs[0] = 0; /* the last slot defines the end of the last node */
121  (*tcliquegraph)->adjnodes = NULL;
122  (*tcliquegraph)->cliqueids = NULL;
123  (*tcliquegraph)->cliquetable = NULL;
124  (*tcliquegraph)->adjnodessize = 0;
125  (*tcliquegraph)->cliqueidssize = 0;
126  (*tcliquegraph)->nnodes = 0;
127  (*tcliquegraph)->tablewidth = 0;
128 
129  return SCIP_OKAY;
130 }
131 
132 /** frees the tclique graph data structure and releases all captured variables */
133 static
134 SCIP_RETCODE tcliquegraphFree(
135  SCIP* scip, /**< SCIP data structure */
136  TCLIQUE_GRAPH** tcliquegraph /**< pointer to tclique graph data */
137  )
138 {
139  int v;
140 
141  assert(tcliquegraph != NULL);
142  assert(*tcliquegraph != NULL);
143 
144  /* release variables */
145  for( v = 0; v < (*tcliquegraph)->nnodes; ++v )
146  {
147  SCIP_CALL( SCIPreleaseVar(scip, &(*tcliquegraph)->vars[v]) );
148  }
149 
150  /* free memory */
151  SCIPfreeMemoryArray(scip, &(*tcliquegraph)->vars);
152  SCIPfreeMemoryArray(scip, &(*tcliquegraph)->weights);
153  SCIPfreeMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs);
154  SCIPfreeMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs);
155  SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->adjnodes);
156  SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliqueids);
157  SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliquetable);
158  SCIPfreeMemory(scip, tcliquegraph);
159 
160  return SCIP_OKAY;
161 }
162 
163 /** ensures that the adjnodes array can store at least num entries */
164 static
165 SCIP_RETCODE tcliquegraphEnsureAdjnodesSize(
166  SCIP* scip, /**< SCIP data structure */
167  TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
168  int num /**< minimal number of adjacent nodes to be able to store in the array */
169  )
170 {
171  assert(tcliquegraph != NULL);
172 
173  if( num > tcliquegraph->adjnodessize )
174  {
175  tcliquegraph->adjnodessize = SCIPcalcMemGrowSize(scip, num);
176  SCIP_CALL( SCIPreallocMemoryArray(scip, &tcliquegraph->adjnodes, tcliquegraph->adjnodessize) );
177  }
178  assert(num <= tcliquegraph->adjnodessize);
179 
180  return SCIP_OKAY;
181 }
182 
183 /** ensures that the cliqueids array can store at least num entries */
184 static
185 SCIP_RETCODE tcliquegraphEnsureCliqueidsSize(
186  SCIP* scip, /**< SCIP data structure */
187  TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
188  int num /**< minimal number of adjacent nodes to be able to store in the array */
189  )
190 {
191  assert(tcliquegraph != NULL);
192 
193  if( num > tcliquegraph->cliqueidssize )
194  {
195  tcliquegraph->cliqueidssize = SCIPcalcMemGrowSize(scip, num);
196  SCIP_CALL( SCIPreallocMemoryArray(scip, &tcliquegraph->cliqueids, tcliquegraph->cliqueidssize) );
197  }
198  assert(num <= tcliquegraph->cliqueidssize);
199 
200  return SCIP_OKAY;
201 }
202 
203 /** adds a node to the tclique graph defined as a variable-value pair; adds all cliques to the cliqueids array the
204  * variable is contained in with the given value
205  */
206 static
207 SCIP_RETCODE tcliquegraphAddNode(
208  SCIP* scip, /**< SCIP data structure */
209  TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */
210  SCIP_VAR* var, /**< active binary problem variable */
211  SCIP_Bool value, /**< value of the variable in the node */
212  int* nodeidx /**< pointer to store the index of the new node */
213  )
214 {
215  SCIP_VAR* nodevar;
216  int* cliqueids;
217  SCIP_CLIQUE** cliques;
218  int ncliques;
219  int nadjnodes;
220  int ncliqueids;
221  int i;
222 
223  assert(tcliquegraph != NULL);
224  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
225  assert(SCIPvarIsActive(var));
226  assert(nodeidx != NULL);
227 
228  /* create tclique graph data if not yet existing */
229  if( *tcliquegraph == NULL )
230  {
231  SCIP_CALL( tcliquegraphCreate(scip, tcliquegraph) );
232  }
233  assert(*tcliquegraph != NULL);
234  assert((*tcliquegraph)->nnodes < 2*SCIPgetNBinVars(scip));
235 
236  /* if the value is FALSE, use the negated variable for the node */
237  if( !value )
238  {
239  SCIP_CALL( SCIPgetNegatedVar(scip, var, &nodevar) );
240  }
241  else
242  nodevar = var;
243 
244  /* get the current number of used entries in adjnodes and cliqueids arrays */
245  nadjnodes = (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes];
246  ncliqueids = (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes];
247 
248  /* insert the variable into the tclique graph */
249  *nodeidx = (*tcliquegraph)->nnodes;
250  SCIP_CALL( SCIPcaptureVar(scip, nodevar) );
251  (*tcliquegraph)->vars[*nodeidx] = nodevar;
252  (*tcliquegraph)->weights[*nodeidx] = 0;
253  (*tcliquegraph)->nnodes++;
254 
255  /* store the ids of the variable's cliques in the cliqueids array */
256  ncliques = SCIPvarGetNCliques(var, value);
257  cliques = SCIPvarGetCliques(var, value);
258  SCIP_CALL( tcliquegraphEnsureCliqueidsSize(scip, *tcliquegraph, ncliqueids + ncliques) );
259  cliqueids = (*tcliquegraph)->cliqueids;
260  for( i = 0; i < ncliques; ++i )
261  {
262  assert(ncliqueids < (*tcliquegraph)->cliqueidssize);
263  cliqueids[ncliqueids] = SCIPcliqueGetId(cliques[i]);
264  assert(i == 0 || cliqueids[ncliqueids-1] <= cliqueids[ncliqueids]);
265  ncliqueids++;
266  }
267 
268  /* store the new number of used entries in adjnodes and cliqueids arrays */
269  (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] = nadjnodes;
270  (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] = ncliqueids;
271 
272  return SCIP_OKAY;
273 }
274 
275 /** adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique */
276 static
277 SCIP_RETCODE tcliquegraphAddCliqueVars(
278  SCIP* scip, /**< SCIP data structure */
279  TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */
280  int** cliquegraphidx /**< array to store tclique graph node index of variable/value pairs */
281  )
282 {
283  SCIP_VAR** vars;
284  int nvars;
285  int i;
286 
287  assert(tcliquegraph != NULL);
288  assert(cliquegraphidx != NULL);
289  assert(cliquegraphidx[0] != NULL);
290  assert(cliquegraphidx[1] != NULL);
291 
292  /* get binary problem variables */
293  vars = SCIPgetVars(scip);
294  nvars = SCIPgetNBinVars(scip);
295 
296  for( i = 0; i < nvars; ++i )
297  {
298  SCIP_VAR* var;
299  int value;
300 
301  var = vars[i];
302 
303  for( value = 0; value < 2; ++value )
304  {
305  assert(cliquegraphidx[value][i] == -1);
306 
307  if( SCIPvarGetNCliques(var, (SCIP_Bool)value) >= 1 )
308  {
309  /* all cliques stored in the clique table are at least 3-cliques */
310  SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, var, (SCIP_Bool)value, &cliquegraphidx[value][i]) );
311  }
312  }
313  }
314 
315  return SCIP_OKAY;
316 }
317 
318 /** adds all variable/value pairs to the tclique graph that are contained in a 3-clique in the implication graph */
319 static
320 SCIP_RETCODE tcliquegraphAddImplicsVars(
321  SCIP* scip, /**< SCIP data structure */
322  TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */
323  int** cliquegraphidx /**< array to store tclique graph node index of variable/value pairs */
324  )
325 {
326  SCIP_VAR** vars;
327  int nvars;
328  int xi;
329 
330  assert(tcliquegraph != NULL);
331  assert(cliquegraphidx != NULL);
332  assert(cliquegraphidx[0] != NULL);
333  assert(cliquegraphidx[1] != NULL);
334 
335  /**@todo search for 3-clique in the implication graph w.r.t. to implicit binary variable (SCIPvarIsBinary()) */
336  /* get binary variables */
337  vars = SCIPgetVars(scip);
338  nvars = SCIPgetNBinVars(scip);
339 
340  if( nvars == 0 )
341  return SCIP_OKAY;
342 
343  assert(nvars > 0);
344 
345  /* detect 3-cliques in the clique graph: triples (x,y,z) in the implication graph with x -> y', x -> z', and y -> z';
346  * in order to avoid double checks, we only check triplets with variable indices xindex < yindex < zindex;
347  * we don't have to check triples with x == y, x == z, or y == z, because cliques with the same variable occuring
348  * twice lead to fixings of this or all other variables which should already have been detected in presolving
349  */
350  for( xi = 0; xi < nvars-2 && !SCIPisStopped(scip); ++xi ) /* at least two variables must be left over for y and z */
351  {
352  SCIP_VAR* x;
353  int xvalue;
354 #ifndef NDEBUG
355  int xindex;
356 #endif
357 
358  x = vars[xi];
359 #ifndef NDEBUG
360  xindex = SCIPvarGetIndex(x);
361 #endif
362  assert(SCIPvarGetType(x) == SCIP_VARTYPE_BINARY);
363 
364  for( xvalue = 0; xvalue < 2; xvalue++ )
365  {
366  SCIP_VAR** ximplvars;
367  SCIP_BOUNDTYPE* ximpltypes;
368  int xnbinimpls;
369  int i;
370 
371  /**@todo search for 3-clique in the implication graph w.r.t. to implicit binary variable (SCIPvarIsBinary()) */
372  /* scan the implications of x == xvalue for potential y candidates */
373  xnbinimpls = SCIPvarGetNBinImpls(x, (SCIP_Bool)xvalue);
374  ximplvars = SCIPvarGetImplVars(x, (SCIP_Bool)xvalue);
375  ximpltypes = SCIPvarGetImplTypes(x, (SCIP_Bool)xvalue);
376 
377  assert(xnbinimpls >= 0);
378  if( xnbinimpls > 0 )
379  {
380 #ifndef NDEBUG
381  SCIP_Bool found;
382 
383  /* search for the position in the sorted array (via binary search) */
384  found = SCIPsortedvecFindPtr((void**)ximplvars, SCIPvarComp, (void*)x, xnbinimpls, &i);
385  assert(!found); /* no implication to itself */
386  assert(i >= 0 && i <= xnbinimpls);
387 #else
388  /* search for the position in the sorted array (via binary search) */
389  (void) SCIPsortedvecFindPtr((void**)ximplvars, SCIPvarComp, (void*)x, xnbinimpls, &i);
390 #endif
391  }
392  else
393  i = 0;
394 
395  /* loop over all y > x */
396  for( ; i < xnbinimpls-1 && !SCIPisStopped(scip); ++i ) /* at least one variable must be left over for z */
397  {
398  SCIP_VAR* y;
399  int yvalue;
400  int yi;
401  SCIP_VAR** yimplvars;
402  SCIP_BOUNDTYPE* yimpltypes;
403  int ynbinimpls;
404  int xk;
405  int yk;
406 #ifndef NDEBUG
407  int yindex;
408 #endif
409 
410  y = ximplvars[i];
411  yi = SCIPvarGetProbindex(y);
412 #ifndef NDEBUG
413  yindex = SCIPvarGetIndex(y);
414 #endif
415  assert(yi < nvars);
416 
417  /* consider only implications with active implvar y */
418  if( yi < 0 )
419  continue;
420 
421  assert(xindex < yindex); /* the implied variables are sorted by increasing variable index */
422  assert(yindex < SCIPvarGetIndex(ximplvars[i+1]));
423 
424  /* check, whether the implicant is y == 0 or y == 1 (yi conflicts with x == xvalue) */
425  yvalue = (int)(ximpltypes[i] == SCIP_BOUNDTYPE_UPPER);
426  assert(0 <= yvalue && yvalue <= 1);
427 
428  /**@todo search for 3-clique in the implication graph w.r.t. to implicit binary variable (SCIPvarIsBinary()) */
429  /* scan the remaining implications of x == xvalue and the implications of y == yvalue for equal entries */
430  ynbinimpls = SCIPvarGetNBinImpls(y, (SCIP_Bool)yvalue);
431  yimplvars = SCIPvarGetImplVars(y, (SCIP_Bool)yvalue);
432  yimpltypes = SCIPvarGetImplTypes(y, (SCIP_Bool)yvalue);
433 
434  /* we simultaneously scan both implication arrays for candidates z with x < y < z */
435  xk = i+1;
436 
437  assert(ynbinimpls >= 0);
438  if( ynbinimpls > 0 )
439  {
440 #ifndef NDEBUG
441  SCIP_Bool found;
442 
443  /* search for the position in the sorted array (via binary search) */
444  found = SCIPsortedvecFindPtr((void**)yimplvars, SCIPvarComp, (void*)y, ynbinimpls, &yk);
445  assert(!found); /* no implication to itself */
446  assert(yk >= 0 && yk <= ynbinimpls);
447 #else
448  (void) SCIPsortedvecFindPtr((void**)yimplvars, SCIPvarComp, (void*)y, ynbinimpls, &yk);
449 #endif
450  }
451  else
452  yk = 0;
453 
454  while( xk < xnbinimpls && yk < ynbinimpls )
455  {
456  int zindex;
457 
458  assert(yindex < SCIPvarGetIndex(ximplvars[xk]));
459  assert(yindex < SCIPvarGetIndex(yimplvars[yk]));
460 
461  /* scan the implications of x */
462  zindex = SCIPvarGetIndex(yimplvars[yk]);
463 
464  while ( xk < xnbinimpls && SCIPvarGetIndex(ximplvars[xk]) < zindex )
465  ++xk;
466 
467  if( xk >= xnbinimpls )
468  break;
469 
470  /* scan the implications of y */
471  zindex = SCIPvarGetIndex(ximplvars[xk]);
472 
473  while ( yk < ynbinimpls && SCIPvarGetIndex(yimplvars[yk]) < zindex )
474  ++yk;
475 
476  if( yk >= ynbinimpls )
477  break;
478 
479  /* check, whether we reached a common implied variable */
480  if( ximplvars[xk] != yimplvars[yk] )
481  continue;
482 
483  assert(SCIPvarGetIndex(ximplvars[xk]) == zindex);
484  assert(SCIPvarGetIndex(yimplvars[yk]) == zindex);
485 
486  /* check, whether both implications are of the same type */
487  if( ximpltypes[xk] == yimpltypes[yk] )
488  {
489  SCIP_VAR* z;
490  int zi;
491  int zvalue;
492 
493  /* we found z with xindex < yindex < zindex and x + y + z <= 1 */
494  z = ximplvars[xk];
495  zi = SCIPvarGetProbindex(z);
496  assert(zi < nvars);
497 
498  /* consider only implications with active implvar z */
499  if( zi < 0 )
500  continue;
501 
502  assert(SCIPvarGetIndex(z) == zindex);
503  assert(xindex < yindex && yindex < zindex);
504 
505  /* check, whether the implicant is z == 0 or z == 1 (z conflicts with x == xvalue) */
506  zvalue = (int)(ximpltypes[xk] == SCIP_BOUNDTYPE_UPPER);
507  assert(0 <= zvalue && zvalue <= 1);
508 
509  /* add nodes x == xvalue, y == yvalue, and z == zvalue to clique graph (if not yet existing) */
510  if( cliquegraphidx[xvalue][xi] == -1 )
511  {
512  SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, x, (SCIP_Bool)xvalue, &cliquegraphidx[xvalue][xi]) );
513  }
514  if( cliquegraphidx[yvalue][yi] == -1 )
515  {
516  SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, y, (SCIP_Bool)yvalue, &cliquegraphidx[yvalue][yi]) );
517  }
518  if( cliquegraphidx[zvalue][zi] == -1 )
519  {
520  SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, z, (SCIP_Bool)zvalue, &cliquegraphidx[zvalue][zi]) );
521  }
522  }
523 
524  /* proceed with the next pair of implications */
525  xk++;
526  yk++;
527  }
528  }
529  }
530  }
531 
532  return SCIP_OKAY;
533 }
534 
535 /** adds all variable/value pairs to the tclique graph that have implications to two variables of the same existing clique */
536 static
537 SCIP_RETCODE tcliquegraphAddImplicsCliqueVars(
538  SCIP* scip, /**< SCIP data structure */
539  TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */
540  int** cliquegraphidx /**< array to store tclique graph node index of variable/value pairs */
541  )
542 {
543  SCIP_VAR** vars;
544  int nvars;
545  int xi;
546 
547  assert(tcliquegraph != NULL);
548  assert(cliquegraphidx != NULL);
549  assert(cliquegraphidx[0] != NULL);
550  assert(cliquegraphidx[1] != NULL);
551 
552  /**@todo search for 3-clique in the implication graph w.r.t. to implicit binary variable (SCIPvarIsBinary()) */
553  /* get binary variables */
554  vars = SCIPgetVars(scip);
555  nvars = SCIPgetNBinVars(scip);
556  assert(nvars > 0);
557 
558  /* detect triples (x,y,z) with implications x -> y' and x -> z' and a clique that contains y and z;
559  * because all cliques stored in the clique table are at least 3-cliques, y and z are already member of the
560  * tclique graph due to tcliquegraphAddCliqueVars(); therefore, we only have to process pairs x == xvalue
561  * that are currently not member of the tclique graph
562  */
563  for( xi = 0; xi < nvars && !SCIPisStopped(scip); ++xi )
564  {
565  SCIP_VAR* x;
566  SCIP_Bool xvalue;
567 
568  x = vars[xi];
569 
570  for( xvalue = 0; xvalue < 2; xvalue++ )
571  {
572  SCIP_VAR** ximplvars;
573  SCIP_BOUNDTYPE* ximpltypes;
574  int xnbinimpls;
575  int yk;
576 
577  /* we only need to process pairs x == xvalue that are not yet member of the tclique graph */
578  if( cliquegraphidx[xvalue][xi] >= 0 )
579  continue;
580 
581  /**@todo search for 3-clique in the implication graph w.r.t. to implicit binary variable (SCIPvarIsBinary()) */
582  /* scan the implications of x == xvalue for potential y and z candidates */
583  xnbinimpls = SCIPvarGetNBinImpls(x, (SCIP_Bool)xvalue);
584  ximplvars = SCIPvarGetImplVars(x, (SCIP_Bool)xvalue);
585  ximpltypes = SCIPvarGetImplTypes(x, (SCIP_Bool)xvalue);
586 
587  /* loop over all y, at least one variable must be left over for z */
588  for( yk = 0; yk < xnbinimpls-1 && !SCIPisStopped(scip); ++yk )
589  {
590  SCIP_VAR* y;
591  SCIP_Bool yvalue;
592  int yi;
593  int zk;
594 
595  y = ximplvars[yk];
596  yi = SCIPvarGetProbindex(y);
597  assert(yi < nvars);
598 
599  /* consider only implications with active implvar y */
600  if( yi < 0 )
601  continue;
602 
603  assert(SCIPvarGetType(y) == SCIP_VARTYPE_BINARY);
604 
605  /* check, whether the implicant is y == 0 or y == 1 (y conflicts with x == xvalue) */
606  yvalue = (ximpltypes[yk] == SCIP_BOUNDTYPE_UPPER);
607  if( SCIPvarGetNCliques(y, yvalue) == 0 )
608  continue;
609 
610  /* loop over all z > y */
611  for( zk = yk+1; zk < xnbinimpls; ++zk )
612  {
613  SCIP_VAR* z;
614  SCIP_Bool zvalue;
615  int zi;
616 
617  z = ximplvars[zk];
618  zi = SCIPvarGetProbindex(z);
619  assert(zi < nvars);
620 
621  /* consider only implications with active implvar z */
622  if( zi < 0 )
623  continue;
624 
625  assert(SCIPvarGetType(z) == SCIP_VARTYPE_BINARY);
626 
627  /* check, whether the implicant is z == 0 or z == 1 (z conflicts with x == xvalue) */
628  zvalue = (ximpltypes[zk] == SCIP_BOUNDTYPE_UPPER);
629 
630  /* check whether y and z have a common clique stored in the clique table
631  * (the ones in the implication graph have already been processed by tcliquegraphAddImplicsVars())
632  */
633  if( SCIPvarsHaveCommonClique(y, yvalue, z, zvalue, FALSE) )
634  {
635  /* add nodes x == xvalue to clique graph */
636  assert(cliquegraphidx[xvalue][xi] == -1);
637  assert(cliquegraphidx[yvalue][yi] >= 0);
638  assert(cliquegraphidx[zvalue][zi] >= 0);
639  SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, x, (SCIP_Bool)xvalue, &cliquegraphidx[xvalue][xi]) );
640  assert(cliquegraphidx[xvalue][xi] >= 0);
641  break;
642  }
643  }
644  if( cliquegraphidx[xvalue][xi] >= 0 )
645  break;
646  }
647  }
648  }
649 
650  return SCIP_OKAY;
651 }
652 
653 /** adds all implications between nodes in the tclique graph to the tclique graph */
654 static
655 SCIP_RETCODE tcliquegraphAddImplics(
656  SCIP* scip, /**< SCIP data structure */
657  TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
658  int** cliquegraphidx /**< array to store tclique graph node index of variable/value pairs */
659  )
660 {
661  int nadjnodes;
662  int i;
663 
664  assert(cliquegraphidx != NULL);
665  assert(cliquegraphidx[0] != NULL);
666  assert(cliquegraphidx[1] != NULL);
667 
668  /* there is nothing to do, if the graph is empty */
669  if( tcliquegraph == NULL )
670  return SCIP_OKAY;
671 
672  /* the tclique graph should currently contain no implications */
673  assert(tcliquegraph->adjnodes == NULL);
674  assert(tcliquegraph->adjnodessize == 0);
675 
676  nadjnodes = 0;
677  for( i = 0; i < tcliquegraph->nnodes; ++i )
678  {
679  SCIP_VAR* var;
680  SCIP_Bool value;
681  SCIP_VAR** implvars;
682  SCIP_BOUNDTYPE* impltypes;
683  int nbinimpls;
684  int adjnodesidx;
685  int j;
686 
687  /* store start adjnodes index of the node */
688  adjnodesidx = nadjnodes;
689  tcliquegraph->adjnodesidxs[i] = adjnodesidx;
690 
691  /* get active problem variable */
692  var = tcliquegraph->vars[i];
693  value = TRUE;
694  SCIP_CALL( SCIPvarGetProbvarBinary(&var, &value) );
695  assert(0 <= SCIPvarGetProbindex(var) && SCIPvarGetProbindex(var) < SCIPgetNBinVars(scip));
696  assert(cliquegraphidx[value][SCIPvarGetProbindex(var)] == i);
697 
698  /**@todo search for 3-clique in the implication graph w.r.t. to implicit binary variable (SCIPvarIsBinary()) */
699  /* get implications on binary variables */
700  nbinimpls = SCIPvarGetNBinImpls(var, value);
701  implvars = SCIPvarGetImplVars(var, value);
702  impltypes = SCIPvarGetImplTypes(var, value);
703  for( j = 0; j < nbinimpls; ++j )
704  {
705  int probidx;
706  int graphidx;
707  SCIP_Bool implvalue;
708 
709  probidx = SCIPvarGetProbindex(implvars[j]);
710  implvalue = (impltypes[j] == SCIP_BOUNDTYPE_UPPER);
711  assert(probidx < SCIPgetNVars(scip));
712 
713  /* consider only implications with active implvar */
714  if( probidx < 0 )
715  continue;
716 
717  graphidx = cliquegraphidx[implvalue][probidx];
718  if( graphidx >= 0 )
719  {
720  int pos;
721 
722  assert(graphidx < tcliquegraph->nnodes);
723  assert((implvalue == TRUE && tcliquegraph->vars[graphidx] == implvars[j])
724  || (implvalue == FALSE && SCIPvarGetNegationVar(tcliquegraph->vars[graphidx]) == implvars[j]));
725 
726  /* allocate memory for additional arc */
727  SCIP_CALL( tcliquegraphEnsureAdjnodesSize(scip, tcliquegraph, nadjnodes+1) );
728 
729  /* store the adjacent node in the tclique graph data structure, sorted by index */
730  for( pos = nadjnodes; pos > adjnodesidx && tcliquegraph->adjnodes[pos-1] > graphidx; --pos )
731  tcliquegraph->adjnodes[pos] = tcliquegraph->adjnodes[pos-1];
732  tcliquegraph->adjnodes[pos] = graphidx;
733  nadjnodes++;
734  }
735  }
736  }
737  assert(nadjnodes/2 == (nadjnodes+1)/2); /* we must have an even number of arcs */
738 
739  /* store final adjnodes index */
740  tcliquegraph->adjnodesidxs[tcliquegraph->nnodes] = nadjnodes;
741 
742  return SCIP_OKAY;
743 }
744 
745 /** constructs dense clique incidence matrix */
746 static
747 SCIP_RETCODE tcliquegraphConstructCliqueTable(
748  SCIP* scip, /**< SCIP data structure */
749  TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
750  SCIP_Real cliquetablemem, /**< maximal memory size of dense clique table (in kb) */
751  SCIP_Real cliquedensity /**< minimal density of cliques to store as dense table */
752  )
753 {
754  SCIP_CLIQUE** cliques;
755  int* varids;
756  unsigned int* cliquetable;
757  SCIP_Real density;
758  int nbits;
759  int tablesize;
760  int tablewidth;
761  int ncliques;
762  int nelems;
763  int i;
764 
765  /* get clique table */
766  cliques = SCIPgetCliques(scip);
767  ncliques = SCIPgetNCliques(scip);
768  if( ncliques == 0 )
769  return SCIP_OKAY;
770 
771  assert(tcliquegraph != NULL);
772 
773  /* calculate size of dense clique table */
774  nbits = 8*sizeof(unsigned int);
775  tcliquegraph->tablewidth = (tcliquegraph->nnodes + nbits-1) / nbits; /* number of ints needed */
776 
777  /* check if dense clique table is too large (calculate as Reals to avoid overflow) */
778  if( (SCIP_Real)tcliquegraph->nnodes * (SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem )
779  return SCIP_OKAY;
780 
781  /* calculate clique entry density */
782  nelems = 0;
783  for( i = 0; i < ncliques; ++i )
784  nelems += SCIPcliqueGetNVars(cliques[i]);
785  density = (SCIP_Real)nelems / ((SCIP_Real)ncliques * (SCIP_Real)tcliquegraph->nnodes);
786  if( density < cliquedensity )
787  return SCIP_OKAY;
788 
789  /* allocate memory */
790  tablesize = tcliquegraph->nnodes * tcliquegraph->tablewidth;
791  SCIPdebugMessage("clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n",
792  tablesize/1024, SCIPgetNCliques(scip), tcliquegraph->nnodes, density);
793 
794  SCIP_CALL( SCIPallocMemoryArray(scip, &tcliquegraph->cliquetable, tablesize) );
795  BMSclearMemoryArray(tcliquegraph->cliquetable, tablesize);
796 
797  /* insert the cliques as complete graphs to the incidence matrix */
798  SCIP_CALL( SCIPallocBufferArray(scip, &varids, tcliquegraph->nnodes) );
799  cliquetable = tcliquegraph->cliquetable;
800  tablewidth = tcliquegraph->tablewidth;
801  for( i = 0; i < ncliques && !SCIPisStopped(scip); ++i )
802  {
803  SCIP_VAR** vars;
804  SCIP_Bool* vals;
805  int nvars;
806  int u;
807  int v;
808 
809  vars = SCIPcliqueGetVars(cliques[i]);
810  vals = SCIPcliqueGetValues(cliques[i]);
811  nvars = SCIPcliqueGetNVars(cliques[i]);
812 #if 0 /**@todo this assert is currently not valid since implicit binary variables in cliques are ignored,
813  * i.e., corresponding nodes and edges are not added to the tclique graph. Enable assert again if
814  * this feature it incorporated.
815  */
816  assert(nvars <= tcliquegraph->nnodes);
817 #endif
818 
819  /* get the node numbers of the variables */
820  for( u = 0; u < nvars && !SCIPisStopped(scip); ++u )
821  {
822  SCIP_VAR* var;
823 
824  if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY )
825  continue;
826 
827  var = (vals[u] ? vars[u] : SCIPvarGetNegatedVar(vars[u]));
828  assert(var != NULL); /* var must exist even if negated, since it is stored in the tcliquegraph */
829  for( v = 0; v < tcliquegraph->nnodes && var != tcliquegraph->vars[v]; ++v )
830  {}
831  assert(v < tcliquegraph->nnodes);
832  varids[u] = v;
833  }
834 
835  /* flag the edges in the incidence matrix (excluding diagonal entries) */
836  for( u = 0; u < nvars-1 && !SCIPisStopped(scip); ++u )
837  {
838  int nu;
839  int rowstart;
840  int colofs;
841  unsigned int colmask;
842 
843  if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY )
844  continue;
845 
846  nu = varids[u];
847  rowstart = nu*tablewidth;
848  colofs = nu/nbits;
849  colmask = 1 << (nu % nbits); /*lint !e701*/
850  for( v = u+1; v < nvars; ++v )
851  {
852  int nv;
853  unsigned int mask;
854 
855  if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_BINARY )
856  continue;
857 
858  nv = varids[v];
859  mask = 1 << (nv % nbits); /*lint !e701*/
860  cliquetable[rowstart+nv/nbits] |= mask;
861  cliquetable[nv*tablewidth+colofs] |= colmask;
862  }
863  }
864  }
865  SCIPfreeBufferArray(scip, &varids);
866 
867  SCIPdebugMessage("clique separator: finished constructing dense clique table\n");
868 
869  return SCIP_OKAY;
870 }
871 
872 /** creates tclique data structure using the implication graph;
873  * only variables that are contained in a 3-clique are added as nodes to the clique graph
874  */
875 static
876 SCIP_RETCODE loadTcliquegraph(
877  SCIP* scip, /**< SCIP data structure */
878  SCIP_SEPADATA* sepadata /**< separator data */
879  )
880 {
881  int* cliquegraphidx[2];
882  int nvars;
883  int i;
884 
885  assert(sepadata != NULL);
886  assert(sepadata->tcliquegraph == NULL);
887 
888  /* there is nothing to do, if no binary variables are present in the problem */
889  nvars = SCIPgetNBinVars(scip);
890  if( nvars == 0 )
891  return SCIP_OKAY;
892 
893  /* get temporary memory for mapping variable/value pairs to clique graph nodes */
894  SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[0], nvars) );
895  SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[1], nvars) );
896  for( i = 0; i < nvars; ++i )
897  {
898  cliquegraphidx[0][i] = -1;
899  cliquegraphidx[1][i] = -1;
900  }
901 
902  /* insert all variable/value pairs that are contained in an existing 3-clique */
903  SCIP_CALL( tcliquegraphAddCliqueVars(scip, &sepadata->tcliquegraph, cliquegraphidx) );
904 
905  /* insert all variable/value pairs that are contained in a 3-clique in the implication graph */
906  SCIP_CALL( tcliquegraphAddImplicsVars(scip, &sepadata->tcliquegraph, cliquegraphidx) );
907 
908  /* insert all variable/value pairs that have implications to two variables of the same existing clique */
909  SCIP_CALL( tcliquegraphAddImplicsCliqueVars(scip, &sepadata->tcliquegraph, cliquegraphidx) );
910 
911  /* add all implications between used variables to the tclique graph */
912  SCIP_CALL( tcliquegraphAddImplics(scip, sepadata->tcliquegraph, cliquegraphidx) );
913 
914  /* it occurs that it might be that some cliques were not yet removed from the global clique array, so SCIPgetNClique
915  * can be greater than 0, even if there is no clique with some variables left */
916  /** @todo clean up empty cliques */
917  if( sepadata->tcliquegraph != NULL )
918  {
919  /* construct the dense clique table */
920  SCIP_CALL( tcliquegraphConstructCliqueTable(scip, sepadata->tcliquegraph, sepadata->cliquetablemem, sepadata->cliquedensity) );
921  }
922 
923  /* free temporary memory */
924  SCIPfreeBufferArray(scip, &cliquegraphidx[1]);
925  SCIPfreeBufferArray(scip, &cliquegraphidx[0]);
926  if( SCIPisStopped(scip) && sepadata->tcliquegraph != NULL )
927  SCIP_CALL( tcliquegraphFree(scip,&sepadata->tcliquegraph) );
928  return SCIP_OKAY;
929 }
930 
931 /** updates the weights in the tclique graph data structure */
932 static
933 void updateTcliquegraph(
934  SCIP* scip, /**< SCIP data structure */
935  SCIP_SEPADATA* sepadata /**< separator data */
936  )
937 {
938  TCLIQUE_GRAPH* tcliquegraph;
939  int i;
940 
941  assert(sepadata != NULL);
942  assert(sepadata->varsolvals != NULL);
943 
944  tcliquegraph = sepadata->tcliquegraph;
945  assert(tcliquegraph != NULL);
946 
947  /* updates weight of all nodes in tclique data structure */
948  for( i = 0; i < tcliquegraph->nnodes; i++ )
949  {
950  int weight;
951 
952  weight = (TCLIQUE_WEIGHT)SCIPfeasFloor(scip, sepadata->varsolvals[i] * sepadata->scaleval);
953  tcliquegraph->weights[i] = MAX(weight, 0);
954  }
955 }
956 
957 
958 /*
959  * TClique Graph Callbacks
960  */
961 
962 /** gets number of nodes in the graph */
963 static
964 TCLIQUE_GETNNODES(tcliqueGetnnodesClique)
965 {
966  assert(tcliquegraph != NULL);
967 
968  return tcliquegraph->nnodes;
969 }
970 
971 /** gets weight of nodes in the graph */
972 static
973 TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique)
974 {
975  assert(tcliquegraph != NULL);
976 
977  return tcliquegraph->weights;
978 }
979 
980 /** returns whether the nodes are member of a common clique */
981 static
982 SCIP_Bool nodesHaveCommonClique(
983  TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
984  int node1, /**< first node */
985  int node2 /**< second node */
986  )
987 {
988  assert(tcliquegraph != NULL);
989 
990  /* return TRUE for equal nodes */
991  if( node1 == node2 )
992  return TRUE;
993 
994  /* check whether the dense clique table was constructed */
995  if( tcliquegraph->cliquetable != NULL )
996  {
997  int nbits;
998  unsigned int mask;
999  int colofs;
1000 
1001  /* check entry in the table */
1002  nbits = 8*sizeof(unsigned int);
1003  mask = (1 << (node2 % nbits)); /*lint !e701*/
1004  colofs = node2 / nbits;
1005  assert(((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0)
1006  == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/nbits] & (1 << (node1 % nbits))) != 0)); /*lint !e701*/
1007  return ((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0);
1008  }
1009  else
1010  {
1011  int* cliqueids;
1012  int i1;
1013  int i2;
1014  int endi1;
1015  int endi2;
1016 
1017  cliqueids = tcliquegraph->cliqueids;
1018  i1 = tcliquegraph->cliqueidsidxs[node1];
1019  endi1 = tcliquegraph->cliqueidsidxs[node1+1];
1020  i2 = tcliquegraph->cliqueidsidxs[node2];
1021  endi2 = tcliquegraph->cliqueidsidxs[node2+1];
1022  while( i1 < endi1 && i2 < endi2 )
1023  {
1024  while( i1 < endi1 && cliqueids[i1] < cliqueids[i2] )
1025  i1++;
1026  if( i1 == endi1 )
1027  break;
1028 
1029  while( i2 < endi2 && cliqueids[i2] < cliqueids[i1] )
1030  i2++;
1031  if( i2 == endi2 )
1032  break;
1033 
1034  if( cliqueids[i1] == cliqueids[i2] )
1035  return TRUE;
1036  }
1037 
1038  return FALSE;
1039  }
1040 }
1041 
1042 /** returns, whether the edge (node1, node2) is in the graph */
1043 static
1044 TCLIQUE_ISEDGE(tcliqueIsedgeClique)
1045 {
1046  int left;
1047  int right;
1048 
1049  assert(tcliquegraph != NULL);
1050  assert(0 <= node1 && node1 < tcliquegraph->nnodes);
1051  assert(0 <= node2 && node2 < tcliquegraph->nnodes);
1052 
1053  /* check if node2 is contained in adjacency list of node1 (list is ordered by adjacent nodes) */
1054  left = tcliquegraph->adjnodesidxs[node1];
1055  right = tcliquegraph->adjnodesidxs[node1+1]-1;
1056  while( left <= right )
1057  {
1058  int middle;
1059  int node;
1060 
1061  middle = (left+right)/2;
1062  node = tcliquegraph->adjnodes[middle];
1063  if( node < node2 )
1064  left = middle+1;
1065  else if( node > node2 )
1066  right = middle-1;
1067  else
1068  return TRUE;
1069  }
1070 
1071  /* check if the nodes are member of a common clique */
1072  return nodesHaveCommonClique(tcliquegraph, node1, node2);
1073 }
1074 
1075 /** selects all nodes from a given set of nodes which are adjacent to a given node
1076  * and returns the number of selected nodes
1077  */
1078 static
1079 TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
1080 {
1081  int* graphadjnodes;
1082  int nadjnodes;
1083  int nodeadjindex;
1084  int nodeadjend;
1085  int i;
1086 
1087  assert(tcliquegraph != NULL);
1088  assert(0 <= node && node < tcliquegraph->nnodes);
1089  assert(nnodes == 0 || nodes != NULL);
1090  assert(adjnodes != NULL);
1091 
1092  nadjnodes = 0;
1093 
1094  /* check for each node in given nodes set, if it is adjacent to the given node or shares a common clique */
1095  graphadjnodes = tcliquegraph->adjnodes;
1096  nodeadjindex = tcliquegraph->adjnodesidxs[node];
1097  nodeadjend = tcliquegraph->adjnodesidxs[node+1];
1098  for( i = 0; i < nnodes; i++ )
1099  {
1100  /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */
1101  assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
1102  assert(i == 0 || nodes[i-1] < nodes[i]);
1103  while( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] < nodes[i] )
1104  nodeadjindex++;
1105  if( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] == nodes[i] )
1106  {
1107  /* current node is adjacent to given node */
1108  adjnodes[nadjnodes] = nodes[i];
1109  nadjnodes++;
1110  }
1111  else
1112  {
1113  /* current node is not adjacent to given node: check if they share a common clique */
1114  if( nodesHaveCommonClique(tcliquegraph, node, nodes[i]) )
1115  {
1116  adjnodes[nadjnodes] = nodes[i];
1117  nadjnodes++;
1118  }
1119  }
1120  }
1121 
1122  return nadjnodes;
1123 }
1124 
1125 /** basic code for new cliques (needed because of error handling) */
1126 static
1127 SCIP_RETCODE newsolCliqueAddRow(
1128  SCIP* scip, /**< SCIP data structure */
1129  SCIP_SEPA* sepa, /**< the cut separator itself */
1130  SCIP_SEPADATA* sepadata, /**< data of separator */
1131  int ncliquenodes, /**< number of nodes in clique */
1132  int* cliquenodes, /**< nodes in clique */
1133  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1134  )
1135 {
1136  SCIP_VAR** vars;
1137  SCIP_ROW* cut;
1138  char cutname[SCIP_MAXSTRLEN];
1139  int i;
1140 
1141  assert( cutoff != NULL );
1142  *cutoff = FALSE;
1143 
1144  vars = sepadata->tcliquegraph->vars;
1145  assert(sepadata->tcliquegraph->nnodes > 0);
1146  assert(vars != NULL);
1147 
1148  /* create the cut (handle retcode since we do not have a backtrace) */
1149  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "clique%"SCIP_LONGINT_FORMAT"_%d", sepadata->ncalls, sepadata->ncuts);
1150  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
1151 
1152  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
1153 
1154  assert(ncliquenodes <= sepadata->tcliquegraph->nnodes);
1155  /*SCIPdebugMessage(" -> clique in graph:");*/
1156  for( i = 0; i < ncliquenodes; ++i )
1157  {
1158  assert(cliquenodes[i] < sepadata->tcliquegraph->nnodes);
1159  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cliquenodes[i]], 1.0) );
1160  /*SCIPdebugPrintf(" [%d]<%s>", cliquenodes[i], SCIPvarGetName(vars[cliquenodes[i]]));*/
1161  }
1162  /*SCIPdebugPrintf("\n");*/
1163  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
1164 
1165  /* set cut rank: for clique cuts we always set to 1 */
1166  SCIProwChgRank(cut, 1);
1167 
1168  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
1169 
1170  SCIP_CALL( SCIPaddCut(scip, sepadata->sol, cut, FALSE, cutoff) );
1171  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
1172 
1173  /* release the row */
1174  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
1175 
1176  return SCIP_OKAY;
1177 }
1178 
1179 /** generates cuts using a clique found by algorithm for maximum weight clique
1180  * and decides whether to stop generating cliques with the algorithm for maximum weight clique
1181  */
1182 static
1183 TCLIQUE_NEWSOL(tcliqueNewsolClique)
1184 {
1185  SCIP_SEPADATA* sepadata;
1186  TCLIQUE_WEIGHT minweightinc;
1187 
1188  assert(acceptsol != NULL);
1189  assert(stopsolving != NULL);
1190 
1191  sepadata = (SCIP_SEPADATA*)tcliquedata;
1192  assert(sepadata != NULL);
1193  assert(sepadata->scip != NULL);
1194  assert(sepadata->sepa != NULL);
1195  assert(sepadata->tcliquegraph != NULL);
1196  assert(sepadata->ncuts >= 0);
1197 
1198  /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */
1199  *acceptsol = FALSE;
1200  *stopsolving = FALSE;
1201 
1202  /* slightly increase the minimal weight for additional cliques */
1203  minweightinc = (cliqueweight - *minweight)/10;
1204  minweightinc = MAX(minweightinc, 1);
1205  *minweight += minweightinc;
1206 
1207  /* adds cut if weight of the clique is greater than 1 */
1208  if( cliqueweight > sepadata->scaleval )
1209  {
1210  SCIP* scip;
1211  SCIP_SEPA* sepa;
1212  SCIP_Real* varsolvals;
1213  SCIP_Real unscaledweight;
1214  SCIP_Bool cutoff;
1215  int i;
1216 
1217  scip = sepadata->scip;
1218  sepa = sepadata->sepa;
1219  varsolvals = sepadata->varsolvals;
1220  assert(varsolvals != NULL);
1221 
1222  /* calculate the weight of the clique in unscaled fractional variable space */
1223  unscaledweight = 0.0;
1224  for( i = 0; i < ncliquenodes; i++ )
1225  unscaledweight += varsolvals[cliquenodes[i]];
1226 
1227  if( SCIPisEfficacious(scip, unscaledweight - 1.0) )
1228  {
1229  SCIP_RETCODE retcode;
1230 
1231  /* explicitly handle return code */
1232  retcode = newsolCliqueAddRow(scip, sepa, sepadata, ncliquenodes, cliquenodes, &cutoff);
1233  if ( retcode == SCIP_OKAY )
1234  {
1235  if ( cutoff )
1236  {
1237  sepadata->cutoff = TRUE;
1238  *acceptsol = FALSE;
1239  *stopsolving = TRUE;
1240  }
1241  else
1242  {
1243  SCIPdebugMessage(" -> found clique cut (act=%g)\n", unscaledweight);
1244  sepadata->ncuts++;
1245 
1246  /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent,
1247  * such that only more violated cuts are generated afterwards
1248  */
1249  if( sepadata->maxsepacuts >= 0 )
1250  {
1251  if( sepadata->ncuts > sepadata->maxsepacuts/2 )
1252  *acceptsol = TRUE;
1253  if( sepadata->ncuts >= sepadata->maxsepacuts )
1254  *stopsolving = TRUE;
1255  }
1256  }
1257  }
1258  else
1259  {
1260  /* in case an internal SCIP error occurred we stop the algorithm and store the error code for later
1261  * evaluation
1262  */
1263  sepadata->retcode = retcode;
1264  *stopsolving = TRUE;
1265  }
1266  }
1267  }
1268 }
1269 
1270 
1271 /*
1272  * main separation method
1273  */
1274 
1275 /** searches and adds clique cuts that separate the given primal solution */
1276 static
1277 SCIP_RETCODE separateCuts(
1278  SCIP* scip, /**< SCIP data structure */
1279  SCIP_SEPA* sepa, /**< the cut separator itself */
1280  SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
1281  SCIP_RESULT* result /**< pointer to store the result of the separation call */
1282  )
1283 { /*lint --e{715}*/
1284  SCIP_SEPADATA* sepadata;
1285  TCLIQUE_GRAPH* tcliquegraph;
1286  int* cliquenodes;
1287  TCLIQUE_WEIGHT cliqueweight;
1288  TCLIQUE_STATUS tcliquestatus;
1289  int ncliquenodes;
1290  int maxtreenodes;
1291  int maxzeroextensions;
1292 
1293  assert(scip != NULL);
1294  assert(*result == SCIP_DIDNOTRUN);
1295 
1296  /* get separator data */
1297  sepadata = SCIPsepaGetData(sepa);
1298  assert(sepadata != NULL);
1299 
1300  sepadata->sol = sol;
1301  sepadata->ncalls = SCIPsepaGetNCalls(sepa);
1302  sepadata->cutoff = FALSE;
1303  sepadata->ncuts = 0;
1304 
1305  /* if we already detected that no implications between binary variables exist, nothing has to be done */
1306  if( sepadata->tcliquegraph == NULL && sepadata->tcliquegraphloaded )
1307  return SCIP_OKAY;
1308 
1309  *result = SCIP_DIDNOTFIND;
1310 
1311  /* load tclique data structure */
1312  if( !sepadata->tcliquegraphloaded )
1313  {
1314  assert(sepadata->tcliquegraph == NULL);
1315 
1316  SCIPdebugMessage("loading implication and clique graph\n");
1317  SCIP_CALL( loadTcliquegraph(scip, sepadata) );
1318  sepadata->tcliquegraphloaded = TRUE;
1319 
1320  if( sepadata->tcliquegraph == NULL )
1321  {
1322  if( SCIPisStopped(scip) )
1323  sepadata->tcliquegraphloaded = FALSE;
1324  /* we did not find any variables that are contained in a clique with at least 3 variables in the
1325  * implication graph or in the clique table -> nothing has to be done
1326  */
1327  else
1328  {
1329  SCIPdebugMessage("no 3-cliques found in implication graph\n");
1330  }
1331 
1332  return SCIP_OKAY;
1333  }
1334  }
1335  tcliquegraph = sepadata->tcliquegraph;
1336  assert(tcliquegraph != NULL);
1337 
1338  /* store LP-solution in sepadata and update weights in tclique data structure */
1339  SCIP_CALL( SCIPallocBufferArray(scip, &sepadata->varsolvals, tcliquegraph->nnodes) );
1340  SCIP_CALL( SCIPgetSolVals(scip, sol, tcliquegraph->nnodes, tcliquegraph->vars, sepadata->varsolvals) );
1341  updateTcliquegraph(scip, sepadata);
1342 
1343  /* get maximal number of tree nodes and maximal zero-extensions */
1344  maxtreenodes = (sepadata->maxtreenodes == -1 ? INT_MAX : sepadata->maxtreenodes);
1345  maxzeroextensions = (sepadata->maxzeroextensions == -1 ? INT_MAX : sepadata->maxzeroextensions);
1346 
1347  SCIPdebugMessage("searching for violated clique cuts\n");
1348 
1349  sepadata->retcode = SCIP_OKAY;
1350 
1351  /* finds maximum weight clique in tclique */
1352  SCIP_CALL( SCIPallocBufferArray(scip, &cliquenodes, tcliquegraph->nnodes) );
1353  tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
1354  tcliquegraph, tcliqueNewsolClique, (TCLIQUE_DATA*)sepadata,
1355  cliquenodes, &ncliquenodes, &cliqueweight, (int)sepadata->scaleval-1, (int)sepadata->scaleval+1,
1356  maxtreenodes, sepadata->backtrackfreq, maxzeroextensions, -1, NULL, &tcliquestatus);
1357 
1358  /* in case an internal error occurred during the maximal clique computation, evaluate that one */
1359  SCIP_CALL( sepadata->retcode );
1360 
1361  SCIPdebugMessage("finished searching clique cuts: found %d cuts\n", sepadata->ncuts);
1362 
1363  /* frees data structures */
1364  SCIPfreeBufferArray(scip, &cliquenodes);
1365  SCIPfreeBufferArray(scip, &sepadata->varsolvals);
1366 
1367  /* adjust result code */
1368  if ( sepadata->cutoff )
1369  *result = SCIP_CUTOFF;
1370  else if( sepadata->ncuts > 0 )
1371  *result = SCIP_SEPARATED;
1372 
1373  /* better reset the sol pointer in sepadata to avoid having an invalid pointer */
1374  sepadata->sol = NULL;
1375 
1376  return SCIP_OKAY;
1377 }
1378 
1379 
1380 /*
1381  * Callback methods of separator
1382  */
1383 
1384 /** copy method for separator plugins (called when SCIP copies plugins) */
1385 static
1386 SCIP_DECL_SEPACOPY(sepaCopyClique)
1387 { /*lint --e{715}*/
1388  assert(scip != NULL);
1389  assert(sepa != NULL);
1390  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
1391 
1392  /* call inclusion method of constraint handler */
1393  SCIP_CALL( SCIPincludeSepaClique(scip) );
1394 
1395  return SCIP_OKAY;
1396 }
1397 
1398 
1399 /** destructor of separator to free user data (called when SCIP is exiting) */
1400 static
1401 SCIP_DECL_SEPAFREE(sepaFreeClique)
1402 { /*lint --e{715}*/
1403  SCIP_SEPADATA* sepadata;
1404 
1405  sepadata = SCIPsepaGetData(sepa);
1406  assert(sepadata != NULL);
1407  assert(sepadata->tcliquegraph == NULL);
1408 
1409  SCIPfreeMemory(scip, &sepadata);
1410  SCIPsepaSetData(sepa, NULL);
1411 
1412  return SCIP_OKAY;
1413 }
1414 
1415 
1416 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */
1417 static
1418 SCIP_DECL_SEPAEXITSOL(sepaExitsolClique)
1419 { /*lint --e{715}*/
1420  SCIP_SEPADATA* sepadata;
1421 
1422  sepadata = SCIPsepaGetData(sepa);
1423  assert(sepadata != NULL);
1424 
1425  /* free tclique data */
1426  if( sepadata->tcliquegraph != NULL )
1427  {
1428  SCIP_CALL( tcliquegraphFree(scip, &sepadata->tcliquegraph) );
1429  }
1430  assert(sepadata->tcliquegraph == NULL);
1431  sepadata->tcliquegraphloaded = FALSE;
1432 
1433  return SCIP_OKAY;
1434 }
1435 
1436 
1437 /** LP solution separation method of separator */
1438 static
1439 SCIP_DECL_SEPAEXECLP(sepaExeclpClique)
1440 {
1441  /*lint --e{715}*/
1442 
1443  *result = SCIP_DIDNOTRUN;
1444 
1445  /* only call separator, if we are not close to terminating */
1446  if( SCIPisStopped(scip) )
1447  return SCIP_OKAY;
1448 
1449  /* only call separator, if an optimal LP solution is at hand */
1450  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1451  return SCIP_OKAY;
1452 
1453  /* only call separator, if there are fractional variables */
1454  if( SCIPgetNLPBranchCands(scip) == 0 )
1455  return SCIP_OKAY;
1456 
1457  /* separate cuts on the LP solution */
1458  SCIP_CALL( separateCuts(scip, sepa, NULL, result) );
1459 
1460  return SCIP_OKAY;
1461 }
1462 
1463 
1464 /** arbitrary primal solution separation method of separator */
1465 static
1466 SCIP_DECL_SEPAEXECSOL(sepaExecsolClique)
1467 {
1468  /*lint --e{715}*/
1469 
1470  *result = SCIP_DIDNOTRUN;
1471 
1472  /* separate cuts on the given primal solution */
1473  SCIP_CALL( separateCuts(scip, sepa, sol, result) );
1474 
1475  return SCIP_OKAY;
1476 }
1477 
1478 
1479 /*
1480  * separator specific interface methods
1481  */
1482 
1483 /** creates the clique separator and includes it in SCIP */
1484 SCIP_RETCODE SCIPincludeSepaClique(
1485  SCIP* scip /**< SCIP data structure */
1486  )
1487 {
1488  SCIP_SEPADATA* sepadata;
1489  SCIP_SEPA* sepa;
1490 
1491  /* create clique separator data */
1492  SCIP_CALL( SCIPallocMemory(scip, &sepadata) );
1493  sepadata->tcliquegraph = NULL;
1494  sepadata->scip = scip;
1495  sepadata->sol = NULL;
1496  sepadata->varsolvals = NULL;
1497  sepadata->ncalls = 0;
1498  sepadata->ncuts = 0;
1499  sepadata->tcliquegraphloaded = FALSE;
1500 
1501  /* include separator */
1502  SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
1503  SEPA_USESSUBSCIP, SEPA_DELAY,
1504  sepaExeclpClique, sepaExecsolClique,
1505  sepadata) );
1506 
1507  assert(sepa != NULL);
1508  sepadata->sepa = sepa;
1509 
1510  /* set non-NULL pointers to callback methods */
1511  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyClique) );
1512  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeClique) );
1513  SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolClique) );
1514 
1515  /* add clique separator parameters */
1516  SCIP_CALL( SCIPaddRealParam(scip,
1517  "separating/clique/scaleval",
1518  "factor for scaling weights",
1519  &sepadata->scaleval, TRUE, DEFAULT_SCALEVAL, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1520  SCIP_CALL( SCIPaddIntParam(scip,
1521  "separating/clique/maxtreenodes",
1522  "maximal number of nodes in branch and bound tree (-1: no limit)",
1523  &sepadata->maxtreenodes, TRUE, DEFAULT_MAXTREENODES, -1, INT_MAX, NULL, NULL) );
1524  SCIP_CALL( SCIPaddIntParam(scip,
1525  "separating/clique/backtrackfreq",
1526  "frequency for premature backtracking up to tree level 1 (0: no backtracking)",
1527  &sepadata->backtrackfreq, TRUE, DEFAULT_BACKTRACKFREQ, 0, INT_MAX, NULL, NULL) );
1528  SCIP_CALL( SCIPaddIntParam(scip,
1529  "separating/clique/maxsepacuts",
1530  "maximal number of clique cuts separated per separation round (-1: no limit)",
1531  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) );
1532  SCIP_CALL( SCIPaddIntParam(scip,
1533  "separating/clique/maxzeroextensions",
1534  "maximal number of zero-valued variables extending the clique (-1: no limit)",
1535  &sepadata->maxzeroextensions, TRUE, DEFAULT_MAXZEROEXTENSIONS, -1, INT_MAX, NULL, NULL) );
1536  SCIP_CALL( SCIPaddRealParam(scip,
1537  "separating/clique/cliquetablemem",
1538  "maximal memory size of dense clique table (in kb)",
1539  &sepadata->cliquetablemem, TRUE, DEFAULT_CLIQUETABLEMEM, 0.0, (SCIP_Real)INT_MAX/1024.0, NULL, NULL) );
1540  SCIP_CALL( SCIPaddRealParam(scip,
1541  "separating/clique/cliquedensity",
1542  "minimal density of cliques to use a dense clique table",
1543  &sepadata->cliquedensity, TRUE, DEFAULT_CLIQUEDENSITY, 0.0, 1.0, NULL, NULL) );
1544 
1545  return SCIP_OKAY;
1546 }
1547