Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_bliss.cpp
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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file compute_symmetry_bliss.cpp
17  * @brief interface for symmetry computations to bliss
18  * @author Marc Pfetsch
19  * @author Thomas Rehn
20  * @author Fabian Wegscheider
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "compute_symmetry.h"
26 
27 /* include bliss graph */
28 #include <bliss/defs.hh>
29 #include <bliss/graph.hh>
30 
31 #include <string.h>
32 #include <vector>
33 #include <list>
34 #include <math.h>
35 
36 #include "scip/expr_var.h"
37 #include "scip/expr_sum.h"
38 #include "scip/expr_pow.h"
39 #include "scip/expr.h"
40 #include "scip/cons_nonlinear.h"
41 #include "scip/cons_linear.h"
42 
43 using std::vector;
44 
45 
46 /** struct for bliss callback */
47 struct BLISS_Data
48 {
49  SCIP* scip; /**< SCIP pointer */
50  int npermvars; /**< number of variables for permutations */
51  int nperms; /**< number of permutations */
52  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
53  int nmaxperms; /**< maximal number of permutations */
54  int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
55 };
56 
57 /* ------------------- map for operator types ------------------- */
58 
59 /** gets the key of the given element */
60 static
61 SCIP_DECL_HASHGETKEY(SYMhashGetKeyOptype)
62 { /*lint --e{715}*/
63  return elem;
64 }
65 
66 /** returns TRUE iff both keys are equal
67  *
68  * Compare the types of two operators according to their name, level and, in case of power, exponent.
69  */
70 static
71 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQOptype)
72 {
73  SYM_OPTYPE* k1;
74  SYM_OPTYPE* k2;
75 
76  k1 = (SYM_OPTYPE*) key1;
77  k2 = (SYM_OPTYPE*) key2;
78 
79  /* first check operator name */
80  if ( SCIPexprGetHdlr(k1->expr) != SCIPexprGetHdlr(k2->expr) )
81  return FALSE;
82 
83  /* for pow expressions, also check exponent (TODO should that happen for signpow as well?) */
84  if ( SCIPisExprPower((SCIP*)userptr, k1->expr )
85  && SCIPgetExponentExprPow(k1->expr) != SCIPgetExponentExprPow(k2->expr) ) /*lint !e777*/
86  return FALSE;
87 
88  /* if still undecided, take level */
89  if ( k1->level != k2->level )
90  return FALSE;
91 
92  return TRUE;
93 }
94 
95 /** returns the hash value of the key */
96 static
97 SCIP_DECL_HASHKEYVAL(SYMhashKeyValOptype)
98 { /*lint --e{715}*/
99  SYM_OPTYPE* k;
100  SCIP_Real exponent;
101 
102  k = (SYM_OPTYPE*) key;
103 
104  if ( SCIPisExprPower((SCIP*)userptr, k->expr) )
105  exponent = SCIPgetExponentExprPow(k->expr);
106  else
107  exponent = 1.0;
108 
109  return SCIPhashThree(SCIPrealHashCode(exponent), k->level,
110  SCIPhashKeyValString(NULL, static_cast<void*>(const_cast<char*>(SCIPexprhdlrGetName(SCIPexprGetHdlr(k->expr))))));
111 }
112 
113 /* ------------------- map for constant types ------------------- */
114 
115 /** gets the key of the given element */
116 static
117 SCIP_DECL_HASHGETKEY(SYMhashGetKeyConsttype)
118 { /*lint --e{715}*/
119  return elem;
120 }
121 
122 /** returns TRUE iff both keys are equal
123  *
124  * Compare two constants according to their values.
125  */
126 static
127 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQConsttype)
128 {
129  SYM_CONSTTYPE* k1;
130  SYM_CONSTTYPE* k2;
131 
132  k1 = (SYM_CONSTTYPE*) key1;
133  k2 = (SYM_CONSTTYPE*) key2;
134 
135  return (SCIP_Bool)(k1->value == k2->value); /*lint !e777*/
136 }
137 
138 /** returns the hash value of the key */
139 static
140 SCIP_DECL_HASHKEYVAL(SYMhashKeyValConsttype)
141 { /*lint --e{715}*/
142  SYM_CONSTTYPE* k;
143 
144  k = (SYM_CONSTTYPE*) key;
145 
146  return SCIPrealHashCode(k->value);
147 }
148 
149 /* ------------------- map for constraint side types ------------------- */
150 
151 /** gets the key of the given element */
152 static
153 SCIP_DECL_HASHGETKEY(SYMhashGetKeyRhstype)
154 { /*lint --e{715}*/
155  return elem;
156 }
157 
158 /** returns TRUE iff both keys are equal
159  *
160  * Compare two constraint sides according to lhs and rhs.
161  */
162 static
163 SCIP_DECL_HASHKEYEQ(SYMhashKeyEQRhstype)
164 {
165  SYM_RHSTYPE* k1;
166  SYM_RHSTYPE* k2;
167 
168  k1 = (SYM_RHSTYPE*) key1;
169  k2 = (SYM_RHSTYPE*) key2;
170 
171  if ( k1->lhs != k2->lhs ) /*lint !e777*/
172  return FALSE;
173 
174  return (SCIP_Bool)(k1->rhs == k2->rhs); /*lint !e777*/
175 }
176 
177 /** returns the hash value of the key */
178 static
179 SCIP_DECL_HASHKEYVAL(SYMhashKeyValRhstype)
180 { /*lint --e{715}*/
181  SYM_RHSTYPE* k;
182 
183  k = (SYM_RHSTYPE*) key;
184 
186 }
187 
188 /** callback function for bliss */
189 static
191  void* user_param, /**< parameter supplied at call to bliss */
192  unsigned int n, /**< size of aut vector */
193  const unsigned int* aut /**< automorphism */
194  )
195 {
196  assert( aut != NULL );
197  assert( user_param != NULL );
198 
199  BLISS_Data* data = static_cast<BLISS_Data*>(user_param);
200  assert( data->scip != NULL );
201  assert( data->npermvars < (int) n );
202  assert( data->maxgenerators >= 0);
203 
204  /* make sure we do not generate more that maxgenerators many permutations, if the limit in bliss is not available */
205  if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
206  return;
207 
208  /* copy first part of automorphism */
209  bool isIdentity = true;
210  int* p = 0;
211  if ( SCIPallocBlockMemoryArray(data->scip, &p, data->npermvars) != SCIP_OKAY )
212  return;
213 
214  for (int j = 0; j < data->npermvars; ++j)
215  {
216  /* convert index of variable-level 0-nodes to variable indices */
217  p[j] = (int) aut[j];
218  if ( p[j] != j )
219  isIdentity = false;
220  }
221 
222  /* ignore trivial generators, i.e. generators that only permute the constraints */
223  if ( isIdentity )
224  {
225  SCIPfreeBlockMemoryArray(data->scip, &p, data->npermvars);
226  return;
227  }
228 
229  /* check whether we should allocate space for perms */
230  if ( data->nmaxperms <= 0 )
231  {
232  if ( data->maxgenerators == 0 )
233  data->nmaxperms = 100; /* seems to cover many cases */
234  else
235  data->nmaxperms = data->maxgenerators;
236 
237  if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
238  return;
239  }
240  else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
241  {
242  int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
243  assert( newsize >= data->nperms );
244  assert( data->maxgenerators == 0 );
245 
246  if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
247  return;
248 
249  data->nmaxperms = newsize;
250  }
251 
252  data->perms[data->nperms++] = p;
253 }
254 
255 /** Creates the nodes in the graph that correspond to variables. Each variable type gets a unique color
256  *
257  * @pre graph should be empty when this is called
258  */
259 static
261  SCIP* scip, /**< SCIP instance */
262  bliss::Graph* G, /**< Graph to be constructed */
263  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix (also contains the relevant variables) */
264  int& nnodes, /**< buffer to store number of nodes in graph */
265  const int& nedges, /**< buffer to store number of edges in graph */
266  int& nusedcolors /**< buffer to store number of used colors */
267  )
268 {
269  assert( scip != NULL );
270  assert( G != NULL );
271  assert( nnodes == 0 );
272  assert( nedges == 0 );
273  assert( nusedcolors == 0 );
274  SCIPdebugMsg(scip, "Creating graph with colored nodes for variables.\n");
275 
276  /* add nodes for variables */
277  for (int v = 0; v < matrixdata->npermvars; ++v)
278  {
279  const int color = matrixdata->permvarcolors[v];
280  assert( 0 <= color && color < matrixdata->nuniquevars );
281 
282 #ifndef NDEBUG
283  int node = (int) G->add_vertex((unsigned) color);
284  assert( node == v );
285 #else
286  (void) G->add_vertex((unsigned) color);
287 #endif
288 
289  ++nnodes;
290  }
291 
292  /* this is not exactly true, since we skip auxvars, but it doesn't matter if some colors are not used at all */
293  nusedcolors = matrixdata->nuniquevars;
294 
295  return SCIP_OKAY;
296 }
297 
298 /** Construct linear part of colored graph for symmetry computations
299  *
300  * Construct graph:
301  * - Each variable gets a different node.
302  * - Each constraint gets a different node.
303  * - Each matrix coefficient gets a different node that is connected to the two nodes
304  * corresponding to the respective constraint and variable.
305  *
306  * Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.
307  *
308  * @pre This method assumes that the nodes corresponding to permutation variables are already in the graph and that
309  * their node number is equal to their index.
310  */
311 static
313  SCIP* scip, /**< SCIP instance */
314  bliss::Graph* G, /**< Graph to be constructed */
315  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
316  int& nnodes, /**< buffer to store number of nodes in graph */
317  int& nedges, /**< buffer to store number of edges in graph */
318  int& nusedcolors, /**< buffer to store number of used colors */
319  SCIP_Bool& success /**< whether the construction was successful */
320  )
321 {
322  assert( nnodes == (int) G->get_nof_vertices() );
323  assert( nusedcolors <= nnodes );
324 
325  SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for linear part.\n");
326 
327  success = TRUE;
328 
329  /* add nodes for rhs of constraints */
330  for (int c = 0; c < matrixdata->nrhscoef; ++c)
331  {
332  const int color = matrixdata->rhscoefcolors[c];
333  assert( 0 <= color && color < matrixdata->nuniquerhs );
334 
335 #ifndef NDEBUG
336  int node = (int) G->add_vertex((unsigned) (nusedcolors + color));
337  assert( node == matrixdata->npermvars + c );
338 #else
339  (void) G->add_vertex((unsigned) (matrixdata->nuniquevars + color));
340 #endif
341 
342  ++nnodes;
343  }
344  assert( (int) G->get_nof_vertices() == matrixdata->npermvars + matrixdata->nrhscoef );
345  nusedcolors += matrixdata->nuniquerhs;
346 
347  /* Grouping of nodes depends on the number of nodes in the bipartite graph class.
348  * If there are more variables than constraints, we group by constraints.
349  * That is, given several variable nodes which are incident to one constraint node by the same color,
350  * we join these variable nodes to the constraint node by only one intermediate node.
351  */
352  const bool groupByConstraints = matrixdata->nrhscoef < matrixdata->npermvars;
353  if ( groupByConstraints )
354  SCIPdebugMsg(scip, "Group intermediate nodes by constraints.\n");
355  else
356  SCIPdebugMsg(scip, "Group intermediate nodes by variables.\n");
357 
358  /* "colored" edges based on all matrix coefficients - loop through ordered matrix coefficients */
359  int ninternodes;
360  if ( groupByConstraints )
361  ninternodes = matrixdata->nrhscoef;
362  else
363  ninternodes = matrixdata->npermvars;
364 
365  int* internodes = NULL;
366  SCIP_CALL( SCIPallocBufferArray(scip, &internodes, ninternodes) ); /*lint !e530*/
367  for (int l = 0; l < ninternodes; ++l)
368  internodes[l] = -1;
369 
370  /* We pass through the matrix coeficients, grouped by color, i.e., different coefficients. If the coeffients appear
371  * in the same row or column, it suffices to only generate a single node (depending on groupByConstraints). We store
372  * this node in the array internodes. In order to avoid reinitialization, we store the node number with increasing
373  * numbers for each color. The smallest number for the current color is stored in firstcolornodenumber. */
374  int oldcolor = -1;
375 #ifndef NDEBUG
376  SCIP_Real oldcoef = SCIP_INVALID;
377 #endif
378  int firstcolornodenumber = -1;
379  for (int j = 0; j < matrixdata->nmatcoef; ++j)
380  {
381  int idx = matrixdata->matidx[j];
382  assert( 0 <= idx && idx < matrixdata->nmatcoef );
383 
384  /* find color corresponding to matrix coefficient */
385  const int color = matrixdata->matcoefcolors[idx];
386  assert( 0 <= color && color < matrixdata->nuniquemat );
387 
388  assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
389  assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
390 
391  const int rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
392  const int varnode = matrixdata->matvaridx[idx];
393  assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
394  assert( rhsnode < (int) G->get_nof_vertices() );
395  assert( varnode < (int) G->get_nof_vertices() );
396 
397  /* if we have only one color, we do not need intermediate nodes */
398  if ( matrixdata->nuniquemat == 1 )
399  {
400  G->add_edge((unsigned) varnode, (unsigned) rhsnode);
401  ++nedges;
402  }
403  else
404  {
405  /* if new group of coefficients has been reached */
406  if ( color != oldcolor )
407  {
408  assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
409  oldcolor = color;
410  firstcolornodenumber = nnodes;
411 #ifndef NDEBUG
412  oldcoef = matrixdata->matcoef[idx];
413 #endif
414  }
415  else
416  assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
417 
418  int varrhsidx;
419  if ( groupByConstraints )
420  varrhsidx = matrixdata->matrhsidx[idx];
421  else
422  varrhsidx = matrixdata->matvaridx[idx];
423  assert( 0 <= varrhsidx && varrhsidx < ninternodes );
424 
425  if ( internodes[varrhsidx] < firstcolornodenumber )
426  {
427  internodes[varrhsidx] = (int) G->add_vertex((unsigned) (nusedcolors + color));
428  ++nnodes;
429  }
430  assert( internodes[varrhsidx] >= matrixdata->npermvars + matrixdata->nrhscoef );
431  assert( internodes[varrhsidx] >= firstcolornodenumber );
432 
433  /* determine whether graph would be too large for bliss (can only handle int) */
434  if ( nnodes >= INT_MAX/2 )
435  {
436  success = FALSE;
437  break;
438  }
439 
440  G->add_edge((unsigned) varnode, (unsigned) internodes[varrhsidx]);
441  G->add_edge((unsigned) rhsnode, (unsigned) internodes[varrhsidx]);
442  nedges += 2;
443  }
444  }
445 
446  nusedcolors += matrixdata->nuniquemat;
447 
448  SCIPfreeBufferArray(scip, &internodes);
449  return SCIP_OKAY;
450 }
451 
452 /** Construct non-linear part of colored graph for symmetry computations
453  *
454  * Construct graph:
455  * - Each node of the expression trees gets a different node.
456  * - Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
457  * - Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.
458  *
459  * @note: In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs
460  * and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different
461  * formulations of the same constraints would not be detected as equivalent, e.g. for
462  * 0 <= x1 + x2 <= 1
463  * 0 <= x3 + x4
464  * x3 + x4 <= 1
465  * there would be no symmetry between (x1,x2) and (x3,x4) detected.
466  *
467  * Each different constraint (sides), sum-expression coefficient, constant and operator type gets a
468  * different color that is attached to the corresponding entries.
469  *
470  * @pre This method assumes that the nodes corresponding to permutation variables are already in the graph and that
471  * their node number is equal to their index.
472  */
473 static
475  SCIP* scip, /**< SCIP instance */
476  bliss::Graph* G, /**< Graph to be constructed */
477  SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
478  int& nnodes, /**< buffer to store number of nodes in graph */
479  int& nedges, /**< buffer to store number of edges in graph */
480  int& nusedcolors, /**< number of used colors ind the graph so far */
481  SCIP_Bool& success /**< whether the construction was successful */
482  )
483 {
484  SCIP_HASHTABLE* optypemap;
485  SCIP_HASHTABLE* consttypemap;
486  SCIP_HASHTABLE* sumcoefmap;
487  SCIP_HASHTABLE* rhstypemap;
488  SYM_OPTYPE* uniqueoparray = NULL;
489  SYM_CONSTTYPE* uniqueconstarray = NULL;
490  SYM_CONSTTYPE* sumcoefarray = NULL;
491  SYM_RHSTYPE* uniquerhsarray = NULL;
492  SCIP_CONSHDLR* conshdlr;
493  SCIP_CONS** conss;
494  int nconss;
495  int nuniqueops = 0;
496  int nuniqueconsts = 0;
497  int nuniquecoefs = 0;
498  int nuniquerhs = 0;
499  int oparraysize = exprdata->nuniqueoperators;
500  int constarraysize = exprdata->nuniqueconstants;
501  int coefarraysize = exprdata->nuniquecoefs;
502  int rhsarraysize;
503 
504  assert( scip != NULL );
505  assert( G != NULL );
506  assert( exprdata != NULL );
507  assert( nnodes == (int) G->get_nof_vertices() );
508  assert( nnodes >= nusedcolors );
509 
510  success = TRUE; /*lint !e838*/
511 
512  conshdlr = SCIPfindConshdlr(scip, "nonlinear");
513  nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
514  if ( nconss == 0 )
515  return SCIP_OKAY;
516 
517  conss = SCIPconshdlrGetConss(conshdlr);
518  rhsarraysize = nconss;
519 
520  SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for non-linear part.\n");
521 
522  /* create maps for optypes, constants, sum coefficients and rhs to indices */
523  SCIP_CALL( SCIPhashtableCreate(&optypemap, SCIPblkmem(scip), oparraysize, SYMhashGetKeyOptype,
524  SYMhashKeyEQOptype, SYMhashKeyValOptype, (void*) scip) );
525  SCIP_CALL( SCIPhashtableCreate(&consttypemap, SCIPblkmem(scip), constarraysize, SYMhashGetKeyConsttype,
526  SYMhashKeyEQConsttype, SYMhashKeyValConsttype, (void*) scip) );
527  SCIP_CALL( SCIPhashtableCreate(&sumcoefmap, SCIPblkmem(scip), coefarraysize, SYMhashGetKeyConsttype,
528  SYMhashKeyEQConsttype, SYMhashKeyValConsttype, (void*) scip) );
529  SCIP_CALL( SCIPhashtableCreate(&rhstypemap, SCIPblkmem(scip), rhsarraysize, SYMhashGetKeyRhstype,
530  SYMhashKeyEQRhstype, SYMhashKeyValRhstype, (void*) scip) );
531 
532  assert( optypemap != NULL );
533  assert( consttypemap != NULL );
534  assert( sumcoefmap != NULL );
535  assert( rhstypemap != NULL );
536 
537  /* allocate space for mappings from optypes, constants, sum coefficients and rhs to colors */
538  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniqueoparray, oparraysize) );
539  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniqueconstarray, constarraysize) );
540  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &sumcoefarray, coefarraysize) );
541  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &uniquerhsarray, rhsarraysize) );
542 
543  SCIP_EXPRITER* it;
544  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
545 
546  /* iterate over all expressions and add the corresponding nodes to the graph */
547  for (int i = 0; i < nconss; ++i)
548  {
549  SCIP_EXPR* rootexpr;
550  vector<int> visitednodes(0);
551  vector<SCIP_Bool> ischildofsum(0);
552  int currentlevel = 0;
553 
554  rootexpr = SCIPgetExprNonlinear(conss[i]);
555 
558 
559  for (SCIP_EXPR* expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
560  {
561  switch( SCIPexpriterGetStageDFS(it) )
562  {
563  /* upon entering an expression, check its type and add nodes and edges if neccessary */
565  {
566  int node = -1;
567  int parentnode = -1;
568  int color = -1;
569 
570  /* for variable expressions, get the corresponding node that is already in the graph */
571  if ( SCIPisExprVar(scip, expr) )
572  {
573  SCIP_VAR* var = SCIPgetVarExprVar(expr);
574 
575  /* check whether the variable is active; if not, then replace the inactive variable by its aggregation
576  * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
577  * expression
578  */
579  if ( SCIPvarIsActive(var) )
580  {
581  node = SCIPvarGetProbindex(var);
582  assert( node < (int) G->get_nof_vertices() );
583  }
584  else
585  {
586  SCIP_VAR** vars = NULL;
587  SCIP_Real* vals = NULL;
588  SCIP_Real constant = 0;
589  int varsize = 1;
590  int requiredsize;
591  int k;
592 
593  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varsize) );
594  SCIP_CALL( SCIPallocBufferArray(scip, &vals, varsize) );
595 
596  vars[0] = var;
597  vals[0] = 1.0;
598 
599  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &varsize, varsize, &constant, &requiredsize, TRUE) );
600 
601  if ( requiredsize > varsize )
602  {
603  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
604  SCIP_CALL( SCIPreallocBufferArray(scip, &vals, requiredsize) );
605 
606  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &varsize, requiredsize, &constant, &requiredsize, TRUE) );
607  assert( requiredsize <= varsize );
608  }
609 
610  parentnode = visitednodes[visitednodes.size() - 1];
611  assert( parentnode < (int) G->get_nof_vertices() );
612 
613  /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
614  for ( k = 0; k < requiredsize; ++k )
615  {
616  SYM_CONSTTYPE* ct;
617  int internode;
618 
619  assert( vars[k] != NULL );
620  assert( vals[k] != 0.0 );
621  assert( nuniquecoefs < coefarraysize );
622 
623  ct = &sumcoefarray[nuniquecoefs];
624  ct->value = vals[k];
625 
626  if ( !SCIPhashtableExists(sumcoefmap, (void *) ct) )
627  {
628  SCIP_CALL( SCIPhashtableInsert(sumcoefmap, (void *) ct) );
629  ct->color = nusedcolors++;
630  color = ct->color;
631  nuniquecoefs++;
632  }
633  else
634  {
635  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
636  }
637 
638  /* add the intermediate node with the corresponding color */
639  internode = (int) G->add_vertex((unsigned) color);
640  ++nnodes;
641 
642  assert( internode < (int) G->get_nof_vertices() );
643 
644  G->add_edge((unsigned) internode, (unsigned) parentnode);
645  ++nedges;
646 
647  /* connect the intermediate node to its corresponding variable node */
648  node = SCIPvarGetProbindex(vars[k]);
649  assert( node < (int) G->get_nof_vertices() );
650 
651  G->add_edge((unsigned) node, (unsigned) internode);
652  ++nedges;
653  }
654 
655  /* add the node for the constant */
656  if ( constant != 0.0 )
657  {
658  SYM_CONSTTYPE* ct;
659 
660  /* check whether we have to resize */
661  if ( nuniqueconsts >= constarraysize )
662  {
663  int newsize = SCIPcalcMemGrowSize(scip, nuniqueconsts+1);
664  assert( newsize >= 0 );
665  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &uniqueconstarray, constarraysize, newsize) );
666  constarraysize = newsize;
667  }
668 
669  assert( nuniqueconsts < constarraysize );
670 
671  ct = &uniqueconstarray[nuniqueconsts];
672  ct->value = constant;
673 
674  if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
675  {
676  SCIP_CALL( SCIPhashtableInsert(consttypemap, (void *) ct) );
677  ct->color = nusedcolors++;
678  color = ct->color;
679  nuniqueconsts++;
680  }
681  else
682  {
683  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
684  }
685 
686  /* add the node with a new color */
687  node = (int) G->add_vertex((unsigned) color);
688  ++nnodes;
689 
690  assert( node < (int) G->get_nof_vertices() );
691 
692  G->add_edge((unsigned) node, (unsigned) parentnode);
693  ++nedges;
694  }
695 
696  SCIPfreeBufferArray(scip, &vals);
697  SCIPfreeBufferArray(scip, &vars);
698 
699  /* add a filler node since it will be removed in the next iteration anyway */
700  visitednodes.push_back(nnodes);
701  ischildofsum.push_back(FALSE);
702  ++currentlevel;
703 
704  break;
705  }
706  }
707  /* for constant expressions, get the color of its type (value) or assign a new one */
708  else if ( SCIPisExprValue(scip, expr) )
709  {
710  SYM_CONSTTYPE* ct;
711 
712  assert( nuniqueconsts < constarraysize );
713 
714  ct = &uniqueconstarray[nuniqueconsts];
715  ct->value = SCIPgetValueExprValue(expr);
716 
717  if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
718  {
719  SCIP_CALL( SCIPhashtableInsert(consttypemap, (void *) ct) );
720  ct->color = nusedcolors++;
721  color = ct->color;
722  nuniqueconsts++;
723  }
724  else
725  {
726  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
727  }
728  }
729  /* for all other expressions, get the color of its operator type or assign a new one */
730  else
731  {
732  SYM_OPTYPE* ot;
733 
734  assert( nuniqueops < oparraysize );
735 
736  ot = &uniqueoparray[nuniqueops];
737 
738  ot->expr = expr;
739  ot->level = currentlevel;
740 
741  if ( !SCIPhashtableExists(optypemap, (void *) ot) )
742  {
743  SCIP_CALL( SCIPhashtableInsert(optypemap, (void *) ot) );
744  ot->color = nusedcolors++;
745  color = ot->color;
746  nuniqueops++;
747  }
748  else
749  {
750  color = ((SYM_OPTYPE*) SCIPhashtableRetrieve(optypemap, (void *) ot))->color;
751  }
752  }
753 
754  /* if this is the root expression, add the constraint side node (will be parent of expression node) */
755  if ( SCIPexpriterGetParentDFS(it) == NULL )
756  {
757  /* add the node corresponding to the constraint */
758  SYM_RHSTYPE* rt;
759  int parentcolor;
760 
761  assert( nuniquerhs < rhsarraysize );
762 
763  rt = &uniquerhsarray[nuniquerhs];
764  rt->lhs = SCIPgetLhsNonlinear(conss[i]);
765  rt->rhs = SCIPgetRhsNonlinear(conss[i]);
766 
767  if ( !SCIPhashtableExists(rhstypemap, (void *) rt) )
768  {
769  SCIP_CALL( SCIPhashtableInsert(rhstypemap, (void *) rt) );
770  rt->color = nusedcolors++;
771  parentcolor = rt->color;
772  nuniquerhs++;
773  }
774  else
775  {
776  parentcolor = ((SYM_RHSTYPE*) SCIPhashtableRetrieve(rhstypemap, (void *) rt))->color;
777  }
778 
779  /* add the constraint side node with the corresponding color */
780  parentnode = (int) G->add_vertex((unsigned) parentcolor);
781  ++nnodes;
782 
783  assert( parentnode < (int) G->get_nof_vertices() );
784  }
785  /* otherwise, get the parentnode stored in visitednodes */
786  else
787  {
788  parentnode = visitednodes[visitednodes.size() - 1];
789  assert( parentnode < (int) G->get_nof_vertices() );
790  }
791 
792  /* in all cases apart from variable expressions, the new node is added with the corresponding color */
793  if ( color != -1 )
794  {
795  node = (int) G->add_vertex((unsigned) color);
796  ++nnodes;
797 
798  assert( node < (int) G->get_nof_vertices() );
799  }
800 
801  /* store the new node so that it can be used as parentnode later */
802  assert( node != -1 );
803  visitednodes.push_back(node);
804  ischildofsum.push_back(FALSE);
805 
806  /* connect the current node with its parent */
807  assert( parentnode != -1 );
808  G->add_edge((unsigned) node, (unsigned) parentnode);
809  ++nedges;
810 
811  /* for sum expression, also add intermediate nodes for the coefficients */
812  if ( SCIPisExprSum(scip, expr) )
813  {
814  SCIP_Real* coefs = SCIPgetCoefsExprSum(expr);
815  int internode;
816 
817  /* iterate over children from last to first, such that visitednodes array is in correct order */
818  for (int j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
819  {
820  SYM_CONSTTYPE* ct;
821 
822  assert( nuniquecoefs < coefarraysize );
823 
824  ct = &sumcoefarray[nuniquecoefs];
825  ct->value = coefs[j];
826 
827  if ( !SCIPhashtableExists(sumcoefmap, (void *) ct) )
828  {
829  SCIP_CALL( SCIPhashtableInsert(sumcoefmap, (void *) ct) );
830  ct->color = nusedcolors++;
831  color = ct->color;
832  nuniquecoefs++;
833  }
834  else
835  {
836  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
837  }
838 
839  /* add the intermediate node with the corresponding color */
840  internode = (int) G->add_vertex((unsigned) color);
841  ++nnodes;
842  visitednodes.push_back(internode);
843  ischildofsum.push_back(TRUE);
844 
845  assert( internode < (int) G->get_nof_vertices() );
846 
847  G->add_edge((unsigned) internode, (unsigned) node);
848  ++nedges;
849  }
850 
851  /* add node for the constant term of the sum expression */
852  SCIP_Real constval = SCIPgetConstantExprSum(expr);
853  if ( constval != 0.0 )
854  {
855  SYM_CONSTTYPE* ct;
856 
857  /* check whether we have to resize */
858  if ( nuniqueconsts >= constarraysize )
859  {
860  int newsize = SCIPcalcMemGrowSize(scip, nuniqueconsts+1);
861  assert( newsize >= 0 );
862  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &uniqueconstarray, constarraysize, newsize) );
863  constarraysize = newsize;
864  }
865 
866  assert( nuniqueconsts < constarraysize );
867 
868  ct = &uniqueconstarray[nuniqueconsts];
869  ct->value = constval;
870 
871  if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
872  {
873  SCIP_CALL( SCIPhashtableInsert(consttypemap, (void *) ct) );
874  ct->color = nusedcolors++;
875  color = ct->color;
876  nuniqueconsts++;
877  }
878  else
879  {
880  color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
881  }
882 
883  /* add the node with a new color */
884  internode = (int) G->add_vertex((unsigned) color);
885  ++nnodes;
886 
887  assert( node < (int) G->get_nof_vertices() );
888 
889  G->add_edge((unsigned) internode, (unsigned) node);
890  ++nedges;
891  }
892  }
893 
894  currentlevel++;
895  break;
896  }
897 
898  /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
900  {
901  visitednodes.pop_back();
902  ischildofsum.pop_back();
903  currentlevel--;
904 
905  /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
906  * used for the coefficients of summands
907  */
908  if ( !ischildofsum.empty() && ischildofsum[ischildofsum.size() - 1] )
909  {
910  visitednodes.pop_back();
911  ischildofsum.pop_back();
912  }
913 
914  break;
915  }
916 
917  default:
918  SCIPABORT(); /* we should never be called in this stage */
919  break;
920  }
921  }
922 
923  assert( currentlevel == 0 );
924  assert( visitednodes.empty() );
925  assert( ischildofsum.empty() );
926 
927  /* determine whether graph would be too large for bliss (can only handle int) */
928  if ( nnodes >= INT_MAX/2 )
929  {
930  success = FALSE; /*lint !e838*/
931  break;
932  }
933  }
934 
935  /* free everything */
936  SCIPfreeExpriter(&it);
937  SCIPfreeBlockMemoryArrayNull(scip, &uniquerhsarray, rhsarraysize);
938  SCIPfreeBlockMemoryArrayNull(scip, &sumcoefarray, coefarraysize);
939  SCIPfreeBlockMemoryArrayNull(scip, &uniqueconstarray, constarraysize);
940  SCIPfreeBlockMemoryArrayNull(scip, &uniqueoparray, oparraysize);
941  SCIPhashtableFree(&rhstypemap);
942  SCIPhashtableFree(&sumcoefmap);
943  SCIPhashtableFree(&consttypemap);
944  SCIPhashtableFree(&optypemap);
945 
946  return SCIP_OKAY;
947 }
948 
949 /** return whether symmetry can be computed */
951 {
952  return TRUE;
953 }
954 
955 char*
957 
959 
960 char*
962 {
963  blissname = new char[100];
964 #ifdef BLISS_PATCH_PRESENT
965  (void) snprintf(blissname, 100, "bliss %sp", bliss::version);
966 #else
967  (void) snprintf(blissname, 100, "bliss %s", bliss::version);
968 #endif
969  return blissname;
970 }
971 
972 
973 /** return name of external program used to compute generators */
974 const char* SYMsymmetryGetName(void)
975 {
976  return blissname;
977 }
978 
979 /** return description of external program used to compute generators */
980 const char* SYMsymmetryGetDesc(void)
981 {
982  return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (www.tcs.hut.fi/Software/bliss/)";
983 }
984 
985 /** compute generators of symmetry group */
987  SCIP* scip, /**< SCIP pointer */
988  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
989  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
990  SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
991  int* nperms, /**< pointer to store number of permutations */
992  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
993  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
994  SCIP_Real* log10groupsize /**< pointer to store size of group */
995  )
996 {
997  assert( scip != NULL );
998  assert( matrixdata != NULL );
999  assert( exprdata != NULL );
1000  assert( nperms != NULL );
1001  assert( nmaxperms != NULL );
1002  assert( perms != NULL );
1003  assert( log10groupsize != NULL );
1004  assert( maxgenerators >= 0 );
1005 
1006  /* init */
1007  *nperms = 0;
1008  *nmaxperms = 0;
1009  *perms = NULL;
1010  *log10groupsize = 0;
1011 
1012  int nnodes = 0;
1013  int nedges = 0;
1014  int nusedcolors = 0;
1015  SCIP_Bool success = FALSE;
1016 
1017  /* create bliss graph */
1018  bliss::Graph G(0);
1019 
1020  /* create nodes corresponding to variables */
1021  SCIP_CALL( createVariableNodes(scip, &G, matrixdata, nnodes, nedges, nusedcolors) );
1022 
1023  assert( nnodes == matrixdata->npermvars );
1024  assert( nusedcolors == matrixdata->nuniquevars );
1025 
1026  /* fill graph with nodes for variables and linear constraints */
1027  SCIP_CALL( fillGraphByLinearConss(scip, &G, matrixdata, nnodes, nedges, nusedcolors, success) );
1028 
1029  if ( !success )
1030  {
1031  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed during linear part.\n");
1032  return SCIP_OKAY;
1033  }
1034 
1035  /* add the nodes for nonlinear constraints to the graph */
1036  SCIP_CALL( fillGraphByNonlinearConss(scip, &G, exprdata, nnodes, nedges, nusedcolors, success) );
1037 
1038  if ( !success )
1039  {
1040  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed during non-linear part.\n");
1041  return SCIP_OKAY;
1042  }
1043 
1044 #ifdef SCIP_OUTPUT
1045  G.write_dot("debug.dot");
1046 #endif
1047 
1048  SCIPdebugMsg(scip, "Symmetry detection graph has %u nodes.\n", G.get_nof_vertices());
1049 
1050  /* compute automorphisms */
1051  bliss::Stats stats;
1052  BLISS_Data data;
1053  data.scip = scip;
1054  data.npermvars = matrixdata->npermvars;
1055  data.nperms = 0;
1056  data.nmaxperms = 0;
1058  data.perms = NULL;
1059 
1060  /* Prefer splitting partition cells corresponding to variables over those corresponding
1061  * to inequalities. This is because we are only interested in the action
1062  * of the automorphism group on the variables, and we need a base for this action */
1063  G.set_splitting_heuristic(bliss::Graph::shs_f);
1064  /* disable component recursion as advised by Tommi Junttila from bliss */
1065  G.set_component_recursion(false);
1066 
1067  /* do not use a node limit, but set generator limit */
1068 #ifdef BLISS_PATCH_PRESENT
1069  G.set_search_limits(0, (unsigned) maxgenerators);
1070 #endif
1071 
1072 #if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
1073  /* lambda function to have access to data and pass it to the blisshook above */
1074  auto reportglue = [&](unsigned int n, const unsigned int* aut) {
1075  blisshook((void*)&data, n, aut);
1076  };
1077 
1078  /* lambda function to have access to stats and terminate the search if maxgenerators are reached */
1079  auto term = [&]() {
1080  return (stats.get_nof_generators() >= (long unsigned int) maxgenerators);
1081  };
1082 
1083  /* start search */
1084  G.find_automorphisms(stats, reportglue, term);
1085 #else
1086  /* start search */
1087  G.find_automorphisms(stats, blisshook, (void*) &data);
1088 #endif
1089 
1090 
1091 #ifdef SCIP_OUTPUT
1092  (void) stats.print(stdout);
1093 #endif
1094 
1095  /* prepare return values */
1096  if ( data.nperms > 0 )
1097  {
1098  *perms = data.perms;
1099  *nperms = data.nperms;
1100  *nmaxperms = data.nmaxperms;
1101  }
1102  else
1103  {
1104  assert( data.perms == NULL );
1105  assert( data.nmaxperms == 0 );
1106  }
1107 
1108  /* determine log10 of symmetry group size */
1109  *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
1110 
1111  return SCIP_OKAY;
1112 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:491
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Real * matcoef
static SCIP_RETCODE fillGraphByNonlinearConss(SCIP *scip, bliss::Graph *G, SYM_EXPRDATA *exprdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)
SCIP_Real lhs
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3798
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:730
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:525
static SCIP_DECL_HASHKEYEQ(SYMhashKeyEQOptype)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1172
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValOptype)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
const char * SYMsymmetryGetName(void)
static SCIP_RETCODE fillGraphByLinearConss(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:87
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition: expr_pow.c:3343
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
const char * SYMsymmetryGetDesc(void)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
char * initStaticBlissName()
#define SCIPhashThree(a, b, c)
Definition: pub_misc.h:512
variable expression handler
#define SCIP_EXPRITER_ENTEREXPR
Definition: type_expr.h:667
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:673
static char * blissname
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2236
interface for symmetry computations
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
SCIP_Real value
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1157
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:407
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:535
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
static SCIP_RETCODE createVariableNodes(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, const int &nedges, int &nusedcolors)
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1432
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyOptype)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
#define NULL
Definition: lpi_spx1.cpp:155
power and signed power expression handlers
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1443
#define SCIP_CALL(x)
Definition: def.h:384
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:510
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1735
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
Definition: graph_load.c:93
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4590
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
SCIP_EXPR * expr
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
SCIP_Real rhs
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:848
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3821
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1465
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2286
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:654
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2314
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:686
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
#define SCIP_Real
Definition: def.h:177
#define SCIP_INVALID
Definition: def.h:197
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:285
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2599
#define SCIP_EXPRITER_LEAVEEXPR
Definition: type_expr.h:670
sum expression handler
#define nnodes
Definition: gastrans.c:65
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:959
#define SCIPABORT()
Definition: def.h:356
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119