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