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