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