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